Проблема размера — диаметра (HjkQlybg jg[byjg — ;ngbymjg)

Перейти к навигации Перейти к поиску

Проблема размера — диаметра — задача поиска наибольшего возможного графа (в терминах размера множества его вершин ) диаметра такого, что наибольшая степень любой вершины в графе не превосходит [1]. Размер графа ограничен сверху границей Мура. Для и только граф Петерсена, граф Хоффмана — Синглтона и, возможно, граф с диаметром и степенью достигают границу Мура. В общем случае наибольшие графы со значениями степень/диаметр имеют размер, много меньший границы Мура.

Изучается также задача поиска наибольшего возможного орграфа, вместо степени графа в этом случае используется полустепень исхода[2].

Пусть  — максимально возможное число вершин графа со степенью, не превосходящей , и диаметром , тогда , где является границей Мура:

Эта граница достигается в очень редких случаях, так что изучение пошло в направлении, насколько близко существуют графы к границе Мура.

Величина называется дефектом графа (здесь  — число вершин в графе). Говорят, что граф имеет малый дефект, если [3]. Есть гипотеза, что для степеней не существует -графов с дефектом 2. О графах с дефектом, большим 2, известно мало[4].

Для асимптотического поведения заметим, что .

Для параметра была высказана гипотеза, что для всех ; известно, что и что .

Если дан связный граф-хозяин[уточнить] , верхняя граница степени и верхняя граница диаметра , ищется наибольший подграф графа с максимальной степенью, не превосходящей и диаметром, не превосходящим . Эта задача называется MaxDDBS, и она содержит проблему размера — диаметра в качестве частного случая (а именно, если взять достаточно большой полный граф в качестве графа-хозяина). Задача является NP-трудной.

Примечания

[править | править код]
  1. Молодцов, 2004, с. 109.
  2. Miller, 2010, с. 341.
  3. Miller, 2010, с. 337.
  4. Miller, 2010, с. 338.

Литература

[править | править код]