Пример того, как пересекающиеся множества определяют граф.
В теории графов граф пересечений — это граф , который представляет собой образец пересечений семейства множеств . Любой граф может быть представлен как граф пересечений, но некоторые важные специальные классы графов могут быть определены типами множеств, которые используются для формирования их представления пересечений.
Формальное определение
Формально граф пересечений G — это неориентированный граф , образованный из семейства множеств
создавая одну вершину v i для каждого набора Si и соединяя две вершины vi и v j ребром всякий раз, когда соответствующие два набора имеют непустое пересечение , то есть,
Все графы являются графами пересечений.
Любой неориентированный граф G можно представить как граф пересечений. Для каждой вершины v i графа G сформируйте множество Si , состоящее из ребер, инцидентных v i ; тогда два таких множества имеют непустое пересечение тогда и только тогда, когда соответствующие вершины имеют общее ребро. Следовательно, G является графом пересечений множеств Si .
Эрдеш, Гудман и Поса ( 1966 ) предлагают конструкцию, которая более эффективна в том смысле, что она требует меньшего общего числа элементов во всех совокупности Si . Для него общее число элементов множества не более№ 2/4, где n — количество вершин в графе. Они доверяют наблюдению Шпильрайна-Марчевского (1945) о том, что все графы являются графами пересечений, но советуют посмотреть также Чулика (1964). Число пересечений графа — это минимальное общее количество элементов в любом представлении пересечения графа.
Классы графов пересечений
Многие важные семейства графов можно описать как графы пересечений более ограниченных типов семейств множеств, например, множеств, полученных из какой-либо геометрической конфигурации:
Граф интервалов определяется как граф пересечений интервалов на реальной прямой или связанных подграфов графа путей .
Граф безразличия можно определить как граф пересечения единичных интервалов на реальной линии.
Граф трапеций определяется как граф пересечений трапеций, образованных двумя параллельными прямыми. Они являются обобщением понятия графа перестановок и, в свою очередь, являются частным случаем семейства дополнений графов сравнимости , известных как графы сосравнимости.
Круговой граф — это граф пересечений множества хорд окружности.
Теорема об упаковке кругов утверждает, что плоские графы — это в точности графы пересечений семейств замкнутых дисков на плоскости, ограниченной непересекающимися кругами.
Гипотеза Шейнермана (теперь теорема) утверждает, что каждый плоский граф также может быть представлен как граф пересечения отрезков прямой на плоскости. Однако графы пересечений отрезков прямых также могут быть неплоскими, и признание графов пересечений отрезков прямых является полным для экзистенциальной теории действительных чисел (Шефер 2010).
Линейный граф графа G определяется как граф пересечений ребер G , где мы представляем каждое ребро как набор его двух конечных точек.
Блочный граф дерева клик — это граф пересечений двусвязных компонент другого графа.
Шайнерман (1985) охарактеризовал классы пересечений графов , семейства конечных графов, которые можно описать как графы пересечений множеств, взятых из данного семейства множеств. Необходимо и достаточно, чтобы семейство обладало следующими свойствами:
Каждый граф, образованный из графа семейства заменой вершины кликой, также должен принадлежать семейству.
В семействе существует бесконечная последовательность графов, каждый из которых является индуцированным подграфом следующего графа в последовательности, причем каждый граф в семействе является индуцированным подграфом графа в последовательности.
Если представления графа пересечений имеют дополнительное требование о том, что разные вершины должны быть представлены разными наборами, то свойство расширения клики можно опустить.
Связанные понятия
Теоретико -порядковым аналогом графов пересечений являются порядки включения . Точно так же, как представление пересечения графа помечает каждую вершину набором так, что вершины являются смежными тогда и только тогда, когда их множества имеют непустое пересечение, так и представление включения f частично упорядоченного множества помечает каждый элемент набором так, что для любого x и y в частично упорядоченном множестве, x ≤ y тогда и только тогда, когда f ( x ) ⊆ f ( y ).
Чулик, К. (1964), «Приложения теории графов к математической логике и лингвистике», Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Прага: Publ. Дом Чехословацкой академии. наук, стр. 13–20, МР 0176940..
Эрдеш, Пол ; Гудман, AW; Поза, Луи (1966), «Представление графа посредством пересечений множеств» (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153/CJM-1966-014-3, MR 0186575, S2CID 646660.
Макки, Терри А.; МакМоррис, Ф.Р. (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и приложениям, том. 2, Филадельфия: Общество промышленной и прикладной математики, ISBN.0-89871-430-3, МР 1672910.
Шпильрайн-Марчевский, Э. (1945), "Sur deux proprietés desclassd'ensembles", Fund. Математика. , 33 : 303–307, doi : 10.4064/fm-33-1-303-307 , MR 0015448.
