Граф перетинів

В теорії графів графом перетинів називається граф, Шаблон:Не перекладено схему перетинів сімейства множин. Будь-який граф можна подати як граф перетинів, але деякі важливі спеціальні класи можна визначити за допомогою типів множин, що використовуються для подання у вигляді перетинів множин.

Огляд теорії графів перетинів і важливих спеціальних класів графів перетинів наведено в книзі Маккі і МакморрісаШаблон:Sfn.

Формальне визначення

Граф перетинів — це неорієнтований граф, утворений з сімейства множин

$S_i,i=0,1,2,...$

створенням вершини $v_i$ для кожної множини $S_i$ і з'єднанням двох вершин $v_i$ і $v_j$ ребром, якщо відповідні дві множини мають непорожній переріз, тобто

$E(G)=\{\{v_i,v_j\}|S_i\cap S_j\ne \mathrm{\varnothing }\}$.

Всі графи є графами перетинів

Будь-який неорієнтований граф G можна подати як граф перетинів — для будь-якої вершини $v_i$ графа G утворимо множину $S_i$, що складається з ребер, інцидентних $v_i$. Дві таких множини мають непорожній переріз тоді і лише тоді, коли відповідні вершини належать одному ребру. Ердеш, Шаблон:Нп і Шаблон:НпШаблон:Sfn показали більш ефективну побудову (яка вимагає менше елементів у всіх множинах $S_i$), в якій загальна кількість елементів у множинах не перевершує $n^2/4$, де n — число вершин у графі. За їх твердженням, виявленням, що всі графи є графами перетинів, вони завдячують Шаблон:НпШаблон:Sfn, але також згадують і роботи ЧуликаШаблон:Sfn. Число перетинів графа — це мінімальне число елементів у поданнях графа, як графа перетинів.

Класи графів перетинів

Багато важливих сімейств графів можна описати як графи перетинів обмежених типів множин, наприклад, множин, отриманих з деяких геометричних конфігурацій:

• Інтервальний граф визначається як граф перетинів інтервалів на прямій, або зв'язних підграфів — шляхів.
• Граф дуг кола визначається як граф перетинів дуг кола.
• Коловий граф визначається як граф перетинів множини хорд кола.
• Граф многокутників на колі визначається як граф перетинів многокутників з вершинами, що лежать на колі.
• Одна з характеристик хордальних графів — це те, що вони є графами перетинів зв'язних підграфів дерева.
• Трапецеїдальний граф визначається як граф перетинів трапецій, утворених двома паралельними прямими. Він є узагальненням поняття графа перестановки, який, у свою чергу, є окремим випадком сімейства доповнень графів порівнянності, відомих як графи копорівнянності.
• Граф одиничних кіл визначається як граф перетинів одиничних кіл на площині.
• Теорема про пакування кіл стверджує, що планарні графи — це точно графи перетинів сімейств замкнутих дисків на площині, що не перетинаються (дозволено дотик).
• Гіпотеза Шейнермана (тепер — теорема) стверджує, що будь-який планарний граф можна подати у вигляді графа перетинів відрізків на площині. Однак графи перетинів відрізків на прямій можуть бути непланарними, і розпізнавання графів перетинів відрізків на прямій є Шаблон:Не перекладено для Шаблон:Не перекладено Шаблон:Sfn .
• Реберний граф графа G визначається як граф перетинів ребер графа G, де кожне ребро розглядається як множина з двох його кінцевих вершин.
• Струнний граф — це граф перетинів кривих на площині.
• Граф має рамковість k, якщо він є графом перетинів багатовимірних прямокутників розмірності k, але не менших розмірностей.

Варіації та узагальнення

• Теоретичними аналогами порядку графів перетинів є Шаблон:Не перекладено . Точно так само, як подання графа перетинів позначає кожну вершину множиною інцидентних їй ребер, що мають непорожній перетин, подання порядку вкладеності f частково впорядкованої множини позначає кожен елемент такою множиною, що для будь-якого x і y в ній $x\le y$ тоді і тільки тоді, коли$f(x)\subseteq f(y)$.

Див. також

• Число перетинів графа
• Нерв покриття

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга

Посилання

• Jan Kratochvíl, A video lecture on intersection graphs (June 2007) Шаблон:Webarchive
• E. Prisner, A Journey through Intersection Graph County Шаблон:Webarchive