В теорії графів графом перетинів називається граф, [en] схему (перетинів) сімейства множин. Будь-який граф можна подати як граф перетинів, але деякі важливі спеціальні класи можна визначити за допомогою типів множин, що використовуються для подання у вигляді перетинів множин.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTlsTDJVNUwwbHVkR1Z5YzJWamRHbHZibDluY21Gd2FDNW5hV1k9LmdpZg==.gif)
Огляд теорії графів перетинів і важливих спеціальних класів графів перетинів наведено в книзі Маккі і Макморріса.
Формальне визначення
Граф перетинів — це неорієнтований граф, утворений з сімейства множин
створенням вершини для кожної множини
і з'єднанням двох вершин
і
ребром, якщо відповідні дві множини мають непорожній переріз, тобто
.
Всі графи є графами перетинів
Будь-який неорієнтований граф G можна подати як граф перетинів — для будь-якої вершини графа G утворимо множину
, що складається з ребер, інцидентних
. Дві таких множини мають непорожній переріз (тоді і лише тоді), коли відповідні вершини належать одному ребру. (Ердеш), [en] і [en] показали більш ефективну побудову (яка вимагає менше елементів у всіх множинах
), в якій загальна кількість елементів у множинах не перевершує
, де n — число вершин у графі. За їх твердженням, виявленням, що всі графи є графами перетинів, вони завдячують [ru], але також згадують і роботи Чулика. (Число перетинів графа) — це мінімальне число елементів у поданнях графа, як графа перетинів.
Класи графів перетинів
Багато важливих сімейств графів можна описати як графи перетинів обмежених типів множин, наприклад, множин, отриманих з деяких геометричних конфігурацій:
- (Інтервальний граф) визначається як граф перетинів інтервалів на прямій, або зв'язних підграфів — (шляхів).
- (Граф дуг кола) визначається як граф перетинів (дуг кола).
- (Коловий граф) визначається як граф перетинів множини (хорд кола).
- визначається як граф перетинів многокутників з вершинами, що лежать на колі.
- Одна з характеристик (хордальних графів) — це те, що вони є графами перетинів зв'язних підграфів (дерева).
- визначається як граф перетинів трапецій, утворених двома паралельними прямими. Він є узагальненням поняття (графа перестановки), який, у свою чергу, є окремим випадком сімейства доповнень (графів порівнянності), відомих як графи копорівнянності.
- (Граф одиничних кіл) визначається як граф перетинів (одиничних кіл) на площині.
- стверджує, що планарні графи — це точно графи перетинів сімейств замкнутих дисків на площині, що не перетинаються (дозволено дотик).
- (Гіпотеза Шейнермана) (тепер — теорема) стверджує, що будь-який планарний граф можна подати у вигляді графа перетинів (відрізків) на площині. Однак графи перетинів відрізків на прямій можуть бути непланарними, і розпізнавання графів перетинів відрізків на прямій є [en] для [en] .
- (Реберний граф) графа G визначається як граф перетинів ребер графа G, де кожне ребро розглядається як множина з двох його кінцевих вершин.
- (Струнний граф) — це граф перетинів (кривих на площині).
- Граф має (рамковість) k, якщо він є графом перетинів багатовимірних (прямокутників) розмірності k, але не менших розмірностей.
Варіації та узагальнення
- Теоретичними аналогами (порядку) графів перетинів є [en] . Точно так само, як подання графа перетинів позначає кожну вершину множиною інцидентних їй ребер, що мають непорожній перетин, подання порядку вкладеності f (частково впорядкованої множини) позначає кожен елемент такою множиною, що для будь-якого x і 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, вип. 1 (4 червня). — С. 106—112. — DOI: . — (MR)0186575. з джерела 16 квітня 2021. Процитовано 4 листопада 2020.
- Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — .
- Topics in Intersection Graph Theory. — Philadelphia : Society for Industrial and Applied Mathematics, 1999. — Т. 2. — (SIAM Monographs on Discrete Mathematics and Applications) — .
- E. Szpilrajn-Marczewski. Sur deux propriétés des classes d'ensembles // . — 1945. — Т. 33 (4 червня). — С. 303—307. — (MR)0015448.
- Marcus Schaefer. [1] — Springer-Verlag, 2010. — Т. 5849. — С. 334—344. — (Lecture Notes in Computer Science) — . — DOI: з джерела 26 червня 2021
Посилання
- Jan Kratochvíl, A video lecture on intersection graphs (June 2007) [ 17 лютого 2020 у Wayback Machine.]
- E. Prisner, A Journey through Intersection Graph County [ 24 квітня 2021 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет