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

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

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

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

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

путём создания вершины ${\displaystyle v_{i}}$ для каждого множества ${\displaystyle S_{i}}$ и соединения двух вершин ${\displaystyle v_{i}}$ и ${\displaystyle v_{j}}$ ребром, если соответствующие два множества имеют непустое пересечение, то есть

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

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

Любой неориентированный граф G можно представить как граф пересечений — для любой вершины ${\displaystyle v_{i}}$ графа G образуем множество ${\displaystyle S_{i}}$ , состоящее из рёбер, инцидентных ${\displaystyle v_{i}}$ . Два таких множества имеют непустое пересечение тогда и только тогда, когда соответствующие вершины принадлежат одному ребру. Эрдёш, Гудман и Поза показали более эффективное построение (которое требует меньше элементов во всех множествах ${\displaystyle S_{i}}$ ), в котором общее число элементов в множествах не превосходит ${\displaystyle n^{2}/4}$ , где n — число вершин в графе. Он приписывают наблюдение, что все графы являются графами пересечений, Марчевскому , но также рекомендуют посмотреть работы Чулика . Число пересечений графа — это минимальное число элементов в представлениях графа, как графа пересечений.

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

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

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

Вариации и обобщения

• Теоретическими аналогами порядка графов пересечений служат . Точно таким же образом, каким представление графа пересечений помечает каждую вершину множеством инцидентных ей рёбер, имеющих непустое пересечение, представление порядка вложенности f частично упорядоченного множества помечает каждый элемент таким множеством, что для любого x и y в нём ${\displaystyle x\leq y}$ тогда и только тогда, когда ${\displaystyle f(x)\subseteq f(y)}$ .
• Нерв покрытия

Примечания

Литература

• K. Čulík. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). — Prague: Publ. House Czechoslovak Acad. Sci., 1964. — С. 13—20.
• Paul Erdős, A. W. Goodman, Louis Pósa. The representation of a graph by set intersections // Canadian Journal of Mathematics. — 1966. — Т. 18 . — С. 106—112 . — doi : .
• Martin Charles Golumbic. . — Academic Press, 1980. — ISBN 0-12-289260-7 .
• Topics in Intersection Graph Theory. — Philadelphia: Society for Industrial and Applied Mathematics, 1999. — Т. 2. — (SIAM Monographs on Discrete Mathematics and Applications). — ISBN 0-89871-430-3 .
• E. Szpilrajn-Marczewski. Sur deux propriétés des classes d'ensembles // Fund. Math. . — 1945. — Т. 33 . — С. 303—307 .
• Marcus Schaefer. . — Springer-Verlag, 2010. — Vol. 5849. — С. 334—344. — (Lecture Notes in Computer Science). — ISBN 978-3-642-11804-3 . — doi : .

Ссылки

• Jan Kratochvíl, от 17 февраля 2020 на Wayback Machine
• E. Prisner, от 24 апреля 2021 на Wayback Machine