Граф пересечений

Пример того, как пересекающиеся множества определяют граф.

В теории графов граф пересечений — это граф , который представляет собой образец пересечений семейства множеств . Любой граф может быть представлен как граф пересечений, но некоторые важные специальные классы графов могут быть определены типами множеств, которые используются для формирования их представления пересечений.

Формальное определение

Формально граф пересечений G — это неориентированный граф, образованный из семейства множеств

$S_{i},\,\,\,i=0,1,2,\dots$

создавая одну вершину v _i для каждого набора и _Si соединяя две вершины vi _, и v _j ребром всякий раз, когда соответствующие два набора имеют непустое пересечение, то есть

$E(G)=\{\{v_{i},v_{j}\}\mid i\neq j,S_{i}\cap S_{j}\neq \emptyset \}.$

Все графики являются графами пересечений

Любой неориентированный граф G можно представить как граф пересечений. Для каждой вершины v _i графа G сформируйте множество Si _, состоящее из ребер, инцидентных v _i ; тогда два таких множества имеют непустое пересечение тогда и только тогда, когда соответствующие вершины имеют общее ребро. Следовательно, G множеств Si _. является графом пересечений

Эрдеш, Гудман и Поса (1966) предлагают конструкцию, которая более эффективна в том смысле, что она требует меньшего общего числа элементов во всех множествах Si _{совокупных} . Для него общее число элементов множества не более н ² / 4 , где n — количество вершин в графе. Они приписывают наблюдение Шпильрайна-Марчевского (1945) о том, что все графы являются графами пересечений , но советуют посмотреть также Чулика (1964) . Число пересечений графа — это минимальное общее количество элементов в любом представлении пересечения графа.

Классы графов пересечений

Многие важные семейства графов можно описать как графы пересечений более ограниченных типов семейств множеств, например, множеств, полученных из какой-либо геометрической конфигурации:

• Граф интервалов определяется как граф пересечений интервалов на реальной прямой или связанных подграфов графа путей .
• Граф безразличия можно определить как граф пересечения единичных интервалов на реальной линии.
• Граф дуг окружности определяется как граф пересечений дуг окружности .
• Граф многоугольник -круг определяется как пересечение многоугольников с углами на окружности.
• Одна из характеристик хордального графа — это граф пересечений связных подграфов дерева .
• Граф трапеций определяется как граф пересечений трапеций, образованных двумя параллельными прямыми. Они являются обобщением понятия графа перестановок и, в свою очередь, являются частным случаем семейства дополнений графов сравнимости, известных как графы сосравнимости.
• Граф единичного диска определяется как граф пересечения единичных дисков на плоскости.
• Круговой граф — это граф пересечений множества хорд окружности.
• Теорема об упаковке кругов утверждает, что плоские графы — это в точности графы пересечений семейств замкнутых дисков на плоскости, ограниченной непересекающимися кругами.
• Гипотеза Шейнермана (теперь теорема) утверждает, что каждый плоский граф также может быть представлен как граф пересечений отрезков прямой на плоскости. Однако графы пересечений отрезков прямых также могут быть непланарными, и признание графов пересечений отрезков прямых является полным для экзистенциальной теории действительных чисел ( Schefer 2010 ).
• Линейный граф графа G определяется как граф пересечений ребер G , где мы представляем каждое ребро как множество его двух конечных точек.
• Струнный граф — это граф пересечений кривых на плоскости .
• Граф имеет квадратичность k, если он является графом пересечений многомерных блоков размерности k , но не меньшей размерности.
• Граф клик — это граф пересечений максимальных клик другого графа.
• Блочный граф дерева клик — это граф пересечений двусвязных компонент другого графа.

Шайнерман (1985) охарактеризовал классы пересечений графов , семейства конечных графов, которые можно описать как графы пересечений множеств, взятых из данного семейства множеств. Необходимо и достаточно, чтобы семейство обладало следующими свойствами:

• Каждый индуцированный подграф графа семейства также должен принадлежать семейству.
• Каждый граф, образованный из графа семейства путем замены вершины кликой, также должен принадлежать семейству.
• В семействе существует бесконечная последовательность графов, каждый из которых является индуцированным подграфом следующего графа в последовательности, причем каждый граф в семействе является индуцированным подграфом графа в последовательности.

Если представления графа пересечений имеют дополнительное требование о том, что разные вершины должны быть представлены разными наборами, то свойство расширения клики можно опустить.

Связанные понятия

Теоретико -порядковым аналогом графов пересечений являются порядки включения . Точно так же, как представление пересечения графа помечает каждую вершину набором так, что вершины являются смежными тогда и только тогда, когда их множества имеют непустое пересечение, так и представление включения f множества частично упорядоченного помечает каждый элемент набором так, что для любого x и y в частично упорядоченном множестве, x ≤ y тогда и только тогда, когда f ( x ) ⊆ f ( y ).

См. также

• Контактный граф

Ссылки

• Чулик, К. (1964), «Приложения теории графов к математической логике и лингвистике», Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Прага: Publ. Дом Чехословацкой академии. наук, стр. 13–20, MR   0176940 .
• Эрдеш, Пол ; Гудман, AW; Поза, Луи (1966), «Представление графа посредством пересечений множеств» (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153/CJM-1966-014-3 , MR   0186575 , S2CID   646660 .
• Голумбик, Мартин Чарльз (1980), алгоритмическая теория графов и совершенные графы , Academic Press, ISBN  0-12-289260-7 .
• Макки, Терри А.; МакМоррис, Ф.Р. (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и приложениям, том. 2, Филадельфия: Общество промышленной и прикладной математики, ISBN.  0-89871-430-3 , МР   1672910 .
• Шпильрайн-Марчевский, Э. (1945), “О двух свойствах классов множеств”, Fund. Математика. , 33 : 303–307, doi : 10.4064/fm-33-1-303-307 , MR   0015448 .
• Шефер, Маркус (2010), «Сложность некоторых геометрических и топологических задач» (PDF) , Рисование графиков, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Переработанные статьи , Конспекты лекций по информатике, том. 5849, Springer-Verlag, стр. 334–344, номер doi : 10.1007/978-3-642-11805-0_32 , ISBN.  978-3-642-11804-3 .
• Шайнерман, Эдвард Р. (1985), «Характеристика классов пересечений графов», Discrete Mathematics , 55 (2): 185–193, doi : 10.1016/0012-365X(85)90047-0 , MR   0798535 .

Дальнейшее чтение

• Обзор теории графов пересечений и важных специальных классов графов пересечений см. в McKee & McMorris (1999) .

Внешние ссылки

• Ян Кратохвил, Видеолекция о графах пересечений (июнь 2007 г.)
• Э. Приснер, Путешествие по графству перекрестков