Перегляд вихідного коду сторінки Інтервальний граф

{{вичитати}}
[[Файл:Interval graph.svg|thumb|300px|Сім інтервалів на прямій і відповідний інтервальний граф із сімома вершинами.]]
'''Інтервальний граф'''&nbsp;— [[Граф перетинів|граф перетинів]] [[Мультимножина|мультимножини]] [[Інтервал (математика)|інтервалів]] на прямій. Має по одній [[Вершина (теорія графів)|вершині]] для кожного інтервалу в множині й по [[Граф (математика)|ребру]] між кожною парою вершин, якщо відповідні інтервали перетинаються.

== Визначення ==

Нехай <math>\{I_1, I_2, ..., I_n\} \subset P(R)</math>&nbsp;— множина інтервалів.

Відповідний інтервальний граф&nbsp;— це G= (V, E), де
* <math>V = \{I_1, I_2,..., I_n\}</math> і
* <math>\{I_\alpha, I_\beta\} \in E</math> тоді й тільки тоді, коли <math>I_\alpha \cap I_\beta \ne \emptyset</math>.

З цієї побудови можна отримати загальні властивості інтервальних графів. Так, граф ''G'' є інтервальним тоді й тільки тоді, коли найбільші [[Кліка (теорія графів)|кліки]] графу ''G'' можуть бути впорядковані <math>M_1, M_2,..., M_k</math> так, що для будь-якого <math>v \in M_i \cap M_k</math>, де <math>i < k</math>, виконується також <math>v \in M_j</math> для будь-якого <math>M_j, i \le j \le k</math>{{sfn|Fishburn|1985}}.

== Ефективні алгоритми розпізнавання ==

Визначити, чи є граф <math>G = (V, E)</math> інтервальним можна за час <math>O(|V|+|E|)</math> шляхом впорядкування найбільших [[Кліка (теорія графів)|клік]] графу ''G''.

Початковий алгоритм розпізнавання за лінійний час Бута і Люкера {{harv|Booth, Lueker|1976}} ґрунтується на складній структурі [[PQ-дерево|PQ-дерев]], але Хабіб, МакКонел, Пауль і В'єно {{harv|Habib, McConnell, Paul, Viennot|2000}} показали, як розв'язати задачу простіше, використовуючи [[лексикографічний пошук у ширину]] і ґрунтуючись на факті, що граф є інтервальним тоді й тільки тоді, коли він [[Хордальний граф|хордальний]] і його [[Доповнення графа|доповнення]]&nbsp;— [[Граф порівнянності|граф порівняння]]{{sfn|Fishburn|1985}}{{sfn|Golumbic|1980}}.

== Пов'язані сім'ї графів ==

Інтервальні графи є [[Хордальний граф|хордальними]], і, як наслідок, [[Досконалий граф|досконалими]]{{sfn|Fishburn|1985}}{{sfn|Golumbic|1980}}. Їх доповнення належать до класу [[Граф порівнянності|графів порівняння]]{{sfn|Gilmore, Hoffman|1964}}, і відношення порівняння&nbsp;— це [[Інтервальний порядок|інтервальний порядок]]{{sfn|Fishburn|1985}}.

Інтервальні графи, які мають інтервальне представлення, в якому будь-які два інтервали або не перетинаються, або вкладені, є [[Тривіальний досконалий граф|тривіальними досконалими графами]].

'''Правильні інтервальні графи'''&nbsp;— це інтервальні графи, які мають інтервальне представлення, в якому жоден інтервал не є [[Підмножина|власною підмножиною]] жодного іншого інтервалу. '''Одиничні інтервальні графи'''&nbsp;— це інтервальні графи, які мають інтервальне представлення, в якому кожен інтервал має одиничну довжину. Будь-який правильний інтервальний граф [[Граф без клешень|не має клешень]]. Але обернене твердження не є правильним&nbsp;— граф без клешень не обов'язково є правильним інтервальним графом<ref>{{harvnb|Faudree, Flandrin, Ryjáček|1997|p=89}}</ref>. Якщо набір сегментів є [[Множина|множиною]], тобто повторення сегментів не є дозволеним, то граф є одиничним інтервальним графом тоді й тільки тоді, коли він є правильним інтервальним графом{{sfn|Roberts|1969}}.

Графи перетинів [[Дуга кола|дуг]] [[Коло|кола]] утворюють [[Граф дуг кола|графи дуг кола]]&nbsp;— клас графів, який містить інтервальні графи. [[Трапецеїдальний граф|Трапецеїдальні графи]], перетин трапецій, всі паралельні сторони яких лежать на двох паралельних прямих, є узагальненням інтервальних графів.

[[Шляхова ширина графа|Шляхова ширина]] інтервального графа на одиницю менша, ніж розмір максимальної кліки (або, що є еквівалентним, на одиницю менша, ніж його хроматичне число), а шляхова ширина будь-якого графа ''G'' дорівнює найменшій шляховій ширині інтервального графа, який містить ''G'' як підграф.

Споріднені інтервальні [[Граф без трикутників|графи без трикутників]]&nbsp;— це те ж, що і [[Гусениця (теорія графів)|гусеничне дерево]]{{sfn|Eckhoff|1993}}.

== Застосування ==
Математичну теорію інтервальних графів створено з урахуванням застосувань дослідниками з математичного відділу [[RAND|корпорації RAND]], в яку входили такі молоді дослідники, як [[Пітер Фішберн]], студенти [[Алан Такер]] і [[Джоел Коуен]], а також лідери, такі як [[Делберт Рей Фалкерсон]] і (частий гість) [[Віктор Клі]]<ref>
{{harvnb|Cohen|1978}} [http://books.google.se/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false ix-10]</ref>.

Коуен застосував інтервальні графи у [[Математична модель|математичних моделях]] [[Популяція|популяцій]], особливо [[Ланцюг живлення|харчових ланцюгів]]<ref>
{{harvnb|Cohen|1978}} [http://books.google.se/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false 12-33]</ref>.

Інші застосування включають [[Генетика|генетику]], [[Біоінформатика|біоінформатику]] та [[Інформатика|інформатику]]. Пошук множини відрізків, які представляють інтервальний граф, може використовуватися як методика збірки неперервних послідовностей в [[Дезоксирибонуклеїнова кислота|ДНК]]{{sfn|Zhang та ін.|1994}}. Інтервальні графи використовуються в підстановці задач на [[розміщення ресурсів]], у [[Дослідження операцій|дослідженнях операцій]] і [[Планувальник операційної системи|плануванні виконання задач]]. Кожний відрізок представляє запит на ресурс на певний період часу. Задача знаходження [[Задача про незалежну множину|незалежної множини максимальної ваги]] графу представляє задачу пошуку кращої підмножини запитів, які можна виконати без конфліктів{{sfn|Bar-Noy, Bar-Yehuda, Freund, Naor|2001}}.

== Див. також ==
* [[Граф Мейнеля]]

== Примітки ==
{{reflist}}

== Література ==
* {{стаття
 | автор = Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber
 | заголовок = A unified approach to approximating resource allocation and scheduling
 | видання = Journal of the ACM
 | рік = 2001
 | том = 48
 | випуск = 5
 | сторінки = 1069—1090
 | url = http://portal.acm.org/citation.cfm?id=335410&coll=portal&dl=ACM
 | doi = 10.1145/502102.502107
 | ref= Bar-Noy, Bar-Yehuda, Freund, Naor, 
}}
* {{стаття
 | автор = Hans L. Bodlaender
 | doi = 10.1016/S0304-3975(97)00228-4
 | випуск = 1—2
 | видання = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | сторінки = 1—45
 | заголовок = A partial ''k''-arboretum of graphs with bounded treewidth
 | том = 209
 | рік = 1998}}
* {{стаття
 | автор = K. S. Booth, G. S. Lueker
 | заголовок = Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
 | видання = J. Comput. System Sci
 | том = 13
 | сторінки = 335—379
 | рік = 1976
 | doi = 10.1016/S0022-0000(76)80045-1
 | випуск = 3
 | ref=Booth, Lueker
}}
* {{cite book
| year = 1978
| last = Joel E. Cohen
| title =Food webs and niche space
| series=Monographs in Population Biology
| volume =11
| location=Princeton, NJ
| publisher=[http://press.princeton.edu/titles/324.html  Princeton University Press]
| pages=xv+1–190
|ref=harv
|isbn=978-0-691-08202-8
}}
* {{стаття
 | автор = Eckhoff | first = Jürgen
 | doi = 10.1002/jgt.3190170112
 | випуск = 1
 | видання = Journal of Graph Theory
 | сторінки = 117—127
 | заголовок = Extremal interval graphs
 | том = 17
 | рік = 1993}}
* {{стаття
 | автор = Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček
 | doi = 10.1016/S0012-365X(96)00045-3
 | випуск = 1—3
 | видання = Discrete Mathematics
 | сторінки = 87—147
 | заголовок = Claw-free graphs — A survey
 | том = 164
 | рік = 1997
 | mr = 1432221
 | ref=Faudree, Flandrin, Ryjáček
}}
* {{книга
|автор =Peter C. Fishburn
|рік = 1985
|заголовок =Interval orders and interval graphs: A study of partially ordered sets
|серія =Wiley-Interscience Series in Discrete Mathematics
|місто =New York|publisher=John Wiley & Sons
|ref=Fishburn
}}
* {{стаття
 | автор = D. R. Fulkerson, O. A. Gross
 | заголовок = Incidence matrices and interval graphs
 | видання= Pacific Journal of Mathematics
 | том = 15
 | сторінки = 835—855
 | рік = 1965}}
* {{стаття
 | автор = P. C. Gilmore, A. J. Hoffman
 | заголовок = A characterization of comparability graphs and of interval graphs
 | видання= Can. J. Math
 | том = 16
 | сторінки = 539—548
 | рік = 1964
 | doi = 10.4153/CJM-1964-055-5
 | ref= Gilmore, Hoffman
}}.
* {{стаття
 | автор = Martin Charles Golumbic
 | заголовок = Algorithmic Graph Theory and Perfect Graphs
 | видання = Academic Press
 | рік = 1980
 | isbn = 0-12-289260-7
}}
* {{стаття
 | автор = Martin Charles Golumbic, Ron Shamir
 | заголовок = Complexity and algorithms for reasoning about time: a graph-theoretic approach
 | видання = J. Assoc. Comput. Mach
 | том = 40
 | сторінки = 1108—1133
 | рік = 1993
 | ref= Golumbic, Shamir
}}.
* {{стаття
 | автор = Michel Habib, Ross McConnell, Christophe Paul, Laurent Viennot
 | заголовок = Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing
 | видання = Theor. Comput. Sci.
 | том = 234
 | сторінки = 59—84
 | рік = 2000
 | url = http://www.cs.colostate.edu/~rmm/lexbfs.ps
 | doi = 10.1016/S0304-3975(97)00241-7
 | ref= Habib, McConnell, Paul, Viennot
}}
* {{книга
 | автор = F.S. Roberts
 | вклад = Indifference graphs
 | заголовок = Proof Techniques in Graph Theory
 | сторінки = 139—146
 | рік = 1969
 | видання = Academic Press, New York
 | url = http://www.sciencedirect.com/science/article/pii/S0012365X07000696
 | ref= Roberts
}}
* {{стаття
 | автор = Peisen Zhang, Eric A. Schon, Stuart G. Fischer, Eftihia Cayanis, Janie Weiss,  Susan Kistler, Philip E. Bourne
 | заголовок = An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA
 | видання = Bioinformatics
 | том = 10
 | випуск= 3
 | рік= 1994
 | сторінки = 309—317
 | doi =  10.1093/bioinformatics/10.3.309
 | ref= Zhang и др.
}}

== Посилання ==
* {{cite web | url=http://www.graphclasses.org/classes/gc_234.html | title=interval graph | work=[http://www.graphclasses.org/index.html Information System on Graph Classes and their Inclusions] | accessdate=19 листопада 2016 | archive-date=7 листопада 2016 | archive-url=https://web.archive.org/web/20161107122808/http://graphclasses.org/classes/gc_234.html }}
* {{mathworld | urlname = IntervalGraph | заглавие = Interval graph}}

[[Категорія:Графи перетинів]]
[[Категорія:Геометричні графи]]