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

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

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

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

.

Всі графи є графами перетинів Будь-який неорієнтований граф G можна подати як граф перетинів — для будь-якої вершини графа G утворимо множину , що складається з ребер, інцидентних . Дві таких множини мають непорожній переріз тоді і лише тоді, коли відповідні вершини належать одному ребру. Ердеш, і показали більш ефективну побудову (яка вимагає менше елементів у всіх множинах ), в якій загальна кількість елементів у множинах не перевершує , де n — число вершин у графі. За їх твердженням, виявленням, що всі графи є графами перетинів, вони завдячують , але також згадують і роботи Чулика. Число перетинів графа — це мінімальне число елементів у поданнях графа, як графа перетинів.

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

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

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

Теоретичними аналогами порядку графів перетинів є . Точно так само, як подання графа перетинів позначає кожну вершину множиною інцидентних їй ребер, що мають непорожній перетин, подання порядку вкладеності f частково впорядкованої множини позначає кожен елемент такою множиною, що для будь-якого x і y в ній тоді і тільки тоді, коли.

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

Примітки

Література

Посилання Jan Kratochvíl, A video lecture on intersection graphs (June 2007) E. Prisner, A Journey through Intersection Graph County