Лучшие вопросы
Таймлайн
Чат
Перспективы
Граф пересечений
граф, представляющий схему пересечений семейства множеств Из Википедии, свободной энциклопедии
Remove ads
В теории графов графом пересечений называется граф, представляющий[англ.] схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.

Обзор теории графов пересечений и важных специальных классов графов пересечений смотрите в книге МакКи и МакМорриса[1].
Remove ads
Формальное определение
Суммиров вкратце
Перспектива
Граф пересечений — это неориентированный граф, образованный из семейства множеств
путём создания вершины для каждого множества и соединения двух вершин и ребром, если соответствующие два множества имеют непустое пересечение, то есть
- .
Remove ads
Все графы являются графами пересечений
Любой неориентированный граф G можно представить как граф пересечений — для любой вершины графа G образуем множество , состоящее из рёбер, инцидентных . Два таких множества имеют непустое пересечение тогда и только тогда, когда соответствующие вершины принадлежат одному ребру. Эрдёш, Гудман и Поза[2] показали более эффективное построение (которое требует меньше элементов во всех множествах ), в котором общее число элементов в множествах не превосходит , где n — число вершин в графе. Он приписывают наблюдение, что все графы являются графами пересечений, Марчевскому[3], но также рекомендуют посмотреть работы Чулика[4]. Число пересечений графа — это минимальное число элементов в представлениях графа, как графа пересечений.
Remove ads
Классы графов пересечений
Суммиров вкратце
Перспектива
Много важных семейств графов можно описать как графы пересечений ограниченных типов множеств, например, множеств, полученных из некоторых геометрических конфигураций:
- Интервальный граф определяется как граф пересечений интервалов на прямой, или связных подграфов-путей.
- Граф дуг окружности определяется как граф пересечений дуг окружности.
- Граф многоугольников на окружности определяется как граф пересечений многоугольников с вершинами, лежащими на окружности.
- Одна из характеристик хордальных графов — это то, что они являются графами пересечений связных подграфов дерева.
- Трапецеидальный граф определяется как граф пересечений трапеций, образованных двумя параллельными прямыми. Они являются обобщением понятия графа перестановки, которые, в свою очередь, являются специальным случаем семейства дополнений графов сравнимости, известных как графы косравнимости.
- Граф единичных кругов определяется как граф пересечений единичных кругов на плоскости.
- Теорема об упаковке кругов утверждает, что планарные графы — это в точности графы пересечений семейств замкнутых непересекающихся (разрешено касание) дисков на плоскости.
- Гипотеза Шейнермана (теперь — теорема) утверждает, что любой планарный граф можно представить в виде графа пересечений отрезков на плоскости. Однако графы пересечений отрезков на прямой могут быть непланарными, и распознавание графов пересечений отрезков на прямой является полным[англ.] для теории существования вещественных чисел[5].
- Рёберный граф графа G определяется как граф пересечений рёбер графа G, где каждое ребро рассматривается как множество из двух его конечных вершин.
- Струнный граф — это граф пересечений кривых на плоскости.
- Граф имеет рамочность k, если он является графом пересечений многомерных прямоугольников размерности k, но не меньших размерностей.
Вариации и обобщения
- Теоретическими аналогами порядка графов пересечений служат порядки вложенности[англ.]. Точно таким же образом, каким представление графа пересечений помечает каждую вершину множеством инцидентных ей рёбер, имеющих непустое пересечение, представление порядка вложенности f частично упорядоченного множества помечает каждый элемент таким множеством, что для любого x и y в нём тогда и только тогда, когда .
- Нерв покрытия
Remove ads
Примечания
Литература
Ссылки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads