Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В математической области теории графов , то число пересечений графа G = ( V , E ) является наименьшим числом элементов в представлении G в качестве графа пересечений из конечных множеств . Эквивалентно, это наименьшее число клик , необходимых для покрытия всех ребер G . [1] [2]

Графики пересечений [ править ]

Пусть F - семейство множеств (допускающее повторение множеств в F ); то граф пересечений из F представляет собой неориентированный граф , который имеет вершину для каждого члена F и ребра между каждыми двумя членами , которые имеют непустое пересечение. Таким образом, каждый граф можно представить как граф пересечений. [3] Число пересечения графа - это наименьшее число k такое, что существует представление этого типа, для которого объединение F имеет k элементов. [1]Проблема нахождения представления пересечения графа с заданным числом элементов известна как проблема базиса графа пересечений . [4]

Крышки края клики [ править ]

График с пересечением номер четыре. Четыре закрашенных области обозначают клики, покрывающие все ребра графа.

Альтернативное определение числа пересечений графа G является то , что это наименьшее число клик в G ( полные подграфы из G ) , которые вместе покрывают все из ребер G . [1] [5] Набор клик с этим свойством известен как краевое покрытие клики или краевое покрытие клики , и по этой причине число пересечений также иногда называют числом краевого покрытия клики . [6]

Равенство числа пересечений и числа краевых кликовых покрытий доказать несложно. В одном направлении предположим, что G - граф пересечений семейства F множеств, объединение которого U имеет k элементов. Тогда для любого элемента x из U подмножество вершин G, соответствующих множествам, содержащим x, образует клику: любые две вершины в этом подмножестве смежны, поскольку их множества имеют непустое пересечение, содержащее x . Далее, каждое ребро в Gсодержатся в одном из этих кликов, поскольку ребро соответствует непустому пересечению и пересечениям не пусто , если она содержит по меньшей мере один элемент из U . Таким образом, ребра G могут быть покрыты K кликами, по одному на элемент U . С другой стороны, если граф G может быть покрыт k кликами, то каждая вершина G может быть представлена ​​набором клик, содержащих эту вершину. [5]

Верхняя граница [ править ]

Тривиально граф с m ребрами имеет число пересечений не более m , поскольку каждое ребро образует клику, и эти клики вместе покрывают все ребра. [7]

Это также верно , что каждый граф с п вершинами имеет число пересечений не более чем п 2 /4 . Сильнее, края каждого п графа -vertex можно разбить на не более чем п 2 /4 клик, все из которых являются либо одиночными ребрами или треугольниками. [2] [5] Это обобщает теорему Mantel в том , что граф без треугольников имеют не более п 2 /4 ребер, ибо в виде треугольника , свободный от графика только оптимальная клика край крышка имеет одну верхушки за край и , следовательно , число пересечений равняется количество ребер. [2]

Еще плотнее границы возможно , когда число ребер строго больше , чем п 2 /4 . Пусть p - количество пар вершин, которые не соединены ребром в данном графе G , и пусть t - единственное целое число, для которого ( t - 1) t ≤ p < t ( t + 1) . Тогда число пересечений G не превосходит p + t . [2] [8]

Графики , которые являются дополнением из разреженного графа имеют малые числа пересечений: число пересечений любого п -vertex граф G не более 2 е 2 ( г + 1) 2 Ln п , где е является основанием натурального логарифма и г максимальная степень комплемента графа G . [9]

Вычислительная сложность [ править ]

Проверка того, имеет ли данный граф G число пересечений не более заданного числа k, является NP-полной . [4] [10] [11] Следовательно, вычислить число пересечений данного графа также NP-сложно.

Однако проблема вычисления числа пересечений решаема с фиксированным параметром : то есть существует функция f такая, что, когда число пересечения равно k , время для ее вычисления составляет не более чем произведение f ( k ) и многочлен от  n . Это может быть показано путем наблюдения , что существует не более 2 K различных замкнутые окрестностив графе - две вершины, принадлежащие одному и тому же набору клик, имеют одну и ту же окрестность - и что граф, образованный путем выбора одной вершины для каждого замкнутого соседа, имеет то же число пересечений, что и исходный граф. Следовательно, за полиномиальное время ввод может быть уменьшен до меньшего ядра с не более чем 2 k вершинами; Применение экспоненциальной процедуры поиска с возвратом во времени к этому ядру приводит к функции f, которая является двойной экспоненциальной по  k . [12] Двухэкспоненциальная зависимость от k не может быть сведена к одноэкспоненциальной с помощью кернелизации полиномиального размера, если толькополиномиальная иерархия разрушается, [13] и если гипотеза об экспоненциальном времени верна, то требуется двухэкспоненциальная зависимость, независимо от того, используется ли ядро. [14]

Известны также более эффективные алгоритмы для некоторых специальных классов графов. Число пересечений интервального графа всегда равно количеству его максимальных клик , которое может быть вычислено за полиномиальное время. [15] [16] В более общем смысле, в хордовых графах число пересечений может быть вычислено с помощью алгоритма, который учитывает вершины в порядке исключения графа и который для каждой вершины v образует клику для v и ее более поздних соседей. если хотя бы одно из ребер, инцидентных v , не покрыто какой-либо предыдущей кликой. [16]

См. Также [ править ]

  • Двудольная размерность , наименьшее количество бикликов, необходимых для покрытия всех ребер графа.
  • Clique cover , NP-сложная задача поиска небольшого числа клик, покрывающих все вершины графа.

Ссылки [ править ]

  1. ^ a b c Гросс, Джонатан Л .; Йеллен, Джей (2006), Теория графов и ее приложения , CRC Press, стр. 440, ISBN 978-1-58488-505-4.
  2. ^ a b c d Робертс, Фред С. (1985), "Приложения краевых покрытий кликами", Дискретная прикладная математика , 10 (1): 93–109, DOI : 10.1016 / 0166-218X (85) 90061-7 , Руководство по ремонту 0770871  CS1 maint: обескураженный параметр ( ссылка ).
  3. ^ Szpilrajn-Марчевский , E. (1945), "Sur Deux propriétés де классов d'Ансамбли", Фонд. Математика. , 33 : 303-307, DOI : 10,4064 / FM-33-1-303-307 , МР 0015448 .
  4. ^ a b Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, Проблема GT59.
  5. ^ a b c Эрдеш, Пол ; Гудман, AW; Posa, Луи (1966), "Представление графа множества пересечений" (PDF) , Канадский журнал математика , 18 (1): 106-112, CiteSeerX 10.1.1.210.6950 , DOI : 10,4153 / CJM-1966- 014-3 , MR 0186575    CS1 maint: обескураженный параметр ( ссылка ).
  6. ^ Майкл, TS; Куинт, Томас (2006), «Сферичность, кубичность и краевые кликовые покрытия графов», Дискретная прикладная математика , 154 (8): 1309–1313, DOI : 10.1016 / j.dam.2006.01.004.
  7. ^ Балакришнан, В.К. (1997), Очерк теории Шаума и проблемы теории графов , McGraw-Hill Professional, стр. 40, ISBN 978-0-07-005489-9.
  8. ^ Ловас, Л. (1968), «О покрытии графов», в Erdős, P .; Катона, Г. (ред.), Труды коллоквиума, состоявшегося в Тихани, Венгрия, 1966 г. , Academic Press, стр. 231–236 CS1 maint: обескураженный параметр ( ссылка ). Цитируется Робертсом (1985) .
  9. ^ Алон, Нога (1986), "Сопроводительные графики по минимальному числу отношений эквивалентности" (PDF) , Combinatorica , 6 (3): 201-206, DOI : 10.1007 / bf02579381 CS1 maint: обескураженный параметр ( ссылка ).
  10. ^ Орлин, Дж. (1977), "Довольство в теории графов: покрытие графов кликами", Proc. Кон. Нед. Акад. Влажный. , Серия А, 80 (5): 406-424, DOI : 10,1016 / 1385-7258 (77) 90055-5 CS1 maint: обескураженный параметр ( ссылка ). Цитируется Робертсом (1985) .
  11. ^ Коу, LT; Stockmeyer, LJ ; Вонг, CK (1978), «Покрытие края кликов в отношении ключевых слов конфликтов и графы пересечений», коммуникации АСМА , 21 (2): 135-139, DOI : 10,1145 / 359340,359346.
  12. ^ Грамм, Йенс; Го, Цзюн; Хюффнер, Фальк; Нидермайер, Rolf (2009), "редукция данных и точные алгоритмы для кликовым покрова" (PDF) , Журнал экспериментальной Algorithmics , 13 (2): 2-15, DOI : 10,1145 / 1412228,1412236 .
  13. ^ Сиган, Марек; Крач, Стефан; Пилипчук, Марцин; Пилипчук, Михал; Валстрём, Магнус (2012), «Покрытие клики и разделение графов: новые результаты несжимаемости», в Czumaj, Artur; Мельхорн, Курт ; Питт, Эндрю; и другие. (ред.), Автоматы, языки и программирование: 39-й международный коллоквиум, ICALP 2012, Уорик, Великобритания, 9-13 июля 2012 г., Proceedings, Part I , Lecture Notes in Computer Science, 7391 , pp. 254–265, arXiv : 1111.0570 , DOI : 10.1007 / 978-3-642-31594-7_22 , ISBN 978-3-642-31593-0.
  14. ^ Сиган, Марек; Пилипчук, Марцин; Пилипчук, Михал (2013), «Известные алгоритмы EDGE CLIQUE COVER, вероятно, оптимальны», Proc. 24-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2013) , 45 , стр. 67–83, arXiv : 1203.1754 , doi : 10.1137 / 130947076.
  15. ^ Опсут, RJ; Робертс, Ф. С. (1981), «О техническом обслуживании автопарка, мобильной радиочастоте, назначении задач и проблемах фазирования трафика», в Chartrand, G .; Alavi, Y .; Голдсмит, DL; Лесняк-Фостер, Л .; Лик Д.Р. (ред.), Теория и приложения графов , Нью-Йорк: Wiley, стр. 479–492.. Цитируется Робертсом (1985) .
  16. ^ а б Шайнерман, Эдвард Р .; Trenk, Энн Н. (1999), "О дробного числа пересечений графа", графов и комбинаторика , 15 (3): 341-351, DOI : 10.1007 / s003730050068.

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Число пересечения» . MathWorld .