График пересечения - Intersection graph

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

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

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

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

S i, i = 0, 1, 2, ...

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

E (G) = {{v i, v j} | i \neq j, S i \cap S j \neq}.

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

Любой неориентированный граф G может быть представлена в виде графа пересечений: для каждой вершины V _I из G , образуют множество S _я , состоящий из ребер, инцидентных V _я ; то два таких множества имеют непустое пересечение тогда и только тогда, когда соответствующие вершины имеют общее ребро. Эрдеш, Гудман и Поза (1966) предлагают более эффективную конструкцию (то есть требует меньшего общего количества элементов во всех совокупностях S _i ), в которой общее количество элементов множества не превышает n ² / 4, где n - количество вершин в графе. Они приписывают Шпильрайн-Марчевскому (1945) наблюдение, что все графы являются графами пересечений , но говорят, что видели также Чулика (1964) . Число пересечений графа - это минимальное общее количество элементов в любом представлении пересечения графа.

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

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

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

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

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

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

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

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

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

График контактов

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

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

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

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

Languages

In other projects