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

Граф, представляющий пересечения между заданными множествами

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

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

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

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

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

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

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

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

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

Erdős, Goodman & Pósa (1966) предлагают конструкцию, которая более эффективна, в том смысле, что она требует меньшего общего числа элементов во всех множествах S _i вместе взятых. Для нее общее число элементов множества не превышает ⁠н ²/4⁠ , где n — число вершин в графе. Они приписывают наблюдение, что все графы являются графами пересечений, Шпильрайну-Марчевскому (1945), но говорят, что см. также Чулика (1964). Число пересечений графа — это минимальное общее число элементов в любом представлении пересечений графа.

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

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

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

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

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

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

Связанные концепции

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

Смотрите также

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

Ссылки

• Чулик, К. (1964), «Применение теории графов к математической логике и лингвистике», Теория графов и ее приложения (Труды симпозиума в Смоленице, 1963) , Прага: Изд-во Чехословацкой академии наук, стр. 13–20, MR  0176940.
• Эрдёш, Пол ; Гудман, AW; Поса, Луис (1966), «Представление графа пересечениями множеств» (PDF) , Канадский журнал математики , 18 (1): 106–112, doi :10.4153/CJM-1966-014-3, MR  0186575, S2CID  646660.
• Golumbic, Martin Charles (1980), Алгоритмическая теория графов и совершенные графы , Academic Press, ISBN 0-12-289260-7.
• Макки, Терри А.; Макморрис, Ф. Р. (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.
• Шефер, Маркус (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), «Характеристика классов пересечений графов», Дискретная математика , 55 (2): 185–193, doi :10.1016/0012-365X(85)90047-0, MR  0798535.

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

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

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

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