У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOW1MMll3TDBKdmVHbGphWFI1TG5OMlp5OHpNREJ3ZUMxQ2IzaHBZMmwwZVM1emRtY3VjRzVuLnBuZw==.png)
Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини.
Приклади
На рисунку показано граф із шістьма вершинами і подання цього графа у вигляді графа перетинів (звичайних двовимірних) прямокутників. Цей граф можна подати у вигляді графа перетинів прямокутників меншої розмірності (в даному випадку — відрізків), так що інтервальна розмірність графа дорівнює двом.
Робертс показав, що граф з 2n вершинами, утворений видаленням досконалого парування з повного графа з 2n вершинами, має інтервальну розмірність рівно n — будь-яку пару нез'єднаних вершин слід подати у вигляді гіперпрямокутників, які мають бути розділені у відмінному від іншої пари вимірі. Подання цього графа у вигляді гіперпрямокутників з розмірністю рівно n можна знайти потовщенням кожної з 2n граней n-вимірного гіперкуба до гіперпрямокутника. Тому такі графи почали називати графами Робертса, хоча вони відоміші як графи вечірки і їх можна трактувати також як графи Турана T(2n,n).
Зв'язок з іншими класами графів
Граф має інтервальну розмірність не більше одиниці тоді і тільки тоді, коли він є інтервальним графом. Інтервальна розмірність довільного графа G — це найменше число інтервальних графів з тією ж множиною вершин (що і G), таких, що перетин множин ребер інтервальних графів дає G. Інтервальна розмірність будь-якого зовніпланарного графа не перевищує двох, а будь-якого планарного графа — трьох.
Якщо двочастковий граф має інтервальну розмірність два, його можна подати у вигляді графа перетинів паралельних осям відрізків на площині.
Алгоритмічні результати
Багато задач на графах можна розв'язати або апроксимувати ефективніше на графах з обмеженою інтервальною розмірністю. Наприклад, задачу про найбільшу кліку для графів з обмеженою інтервальною розмірністю можна розв'язати за поліноміальний час. Для деяких інших задач на графах ефективний розв'язок або апроксимацію можна знайти, якщо існує подання у вигляді перетину гіпербагатогранників малої розмірності.
Однак знаходження таких подань може виявитися складним — перевірка, чи не перевершує інтервальна розмірність заданого графа деякої наперед заданої величини K, є NP-повною задачею, навіть для K = 2. Чандран, Френсіс і Сівадасан описали алгоритми знаходження подань довільних графів у вигляді графа перетинів гіперпрямокутників з розмірністю в межах логарифмічного множника найбільшого степеня графа. Цей результат дає верхню межу інтервальної розмірності графа.
Попри труднощі для природних параметрів, інтервальна розмірність графа є [en], якщо параметризацію проводити за числом вершинного покриття вхідного графа.
Примітки
- Roberts, 1969.
- Наприклад, див. статті Чандрана, Френсіса і Сівадасана (Chandran, Francis, Sivadasan, (2010)), Чандрана і Сівадасана Chandran, Sivadasan, (2007).
- Scheinerman, 1984.
- Thomassen, 1986.
- Bellantoni, Hartman, Przytycka, Whitesides, 1993.
- Чандран, Френсіс і Сівадасан (Chandran, Francis, Sivadasan, (2010)) зауважили, що це випливає з факту, що ці графи мають поліноміальне число максимальних клік. Явне подання у вигляді перетину гіперпрямокутників не вимагає перерахування всіх максимальних клік.
- Див., наприклад, статті Agarwal, van Kreveld, Suri, (1998) і Berman, DasGupta, Muthukrishnan, Ramaswami, (2001) щодо апроксимації найбільшої незалежної множини для графів перетинів прямокутників, і Chlebík, Chlebíková, (2005) з обговоренням складності апроксимації цих задач для більших розмірностей.
- Коззенс (Cozzens, (1981)) показав, що обчислення інтервальної розмірності графа є NP-повною задачею. Яннакакіс (Yannakakis, (1982)) показав, що навіть перевірка, чи не перевищує інтервальна розмірність величини 3, є NP-складною. Нарешті, Краточвіл (Kratochvíl, (1994)) показав, що розпізнавання інтервальної розмірності = 2 є NP-складною задачею.
- Chandran, Francis, Sivadasan, 2010.
- Adiga, Chitnis, Saurabh, 2010.
Література
- Abhijin Adiga, Rajesh Chitnis, Saket Saurabh. Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I. — 2010. — Т. 6506. — С. 366–377. — (Lecture Notes in Computer Science) — DOI:[недоступне посилання з червня 2018]
- Pankaj K. Agarwal, Marc van Kreveld, Subhash Suri. Label placement by maximum independent set in rectangles // . — 1998. — Т. 11, вип. 3–4 (17 червня). — С. 209–218. — DOI: .
- Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Teresa Przytycka, Sue Whitesides. Grid intersection graphs and boxicity // . — 1993. — Т. 114, вип. 1–3 (17 червня). — С. 41–49. — DOI: .
- Piotr Berman, B. DasGupta, S. Muthukrishnan, S. Ramaswami. Efficient approximation algorithms for tiling and packing problems with rectangles // J. Algorithms. — 2001. — Т. 41, вип. 2 (17 червня). — С. 443–47. — DOI: .
- L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan. Geometric representation of graphs in low dimension using axis parallel boxes // Algorithmica. — 2010. — Т. 56, вип. 2 (17 червня). — С. 129–140. — arXiv:cs.DM/0605013. — DOI: .
- L. Sunil Chandran, Naveen Sivadasan. Boxicity and treewidth // . — 2007. — Т. 97, вип. 5 (17 червня). — С. 733–744. — (). — arXiv:math.CO/0505544. — DOI: .
- Miroslav Chlebík, Janka Chlebíková. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2005. — С. 267–276.
- M. B. Cozzens. Higher and Multidimensional Analogues of Interval Graphs. — Rutgers University, 1981. — (Ph.D. thesis)
- Jan Kratochvíl. A special planar satisfiability problem and a consequence of its NP–completeness // Discrete Applied Mathematics. — 1994. — Т. 52, вип. 3 (17 червня). — С. 233–252. — DOI: .
- M. Quest, G. Wegner. Characterization of the graphs with boxicity ≤ 2 // Discrete Mathematics. — 1990. — Т. 81, вип. 2 (17 червня). — С. 187–192. — DOI: .
- F. S. Roberts. Recent Progress in Combinatorics / W. T. Tutte. — Academic Press, 1969. — С. 301–310. — .
- E. R. Scheinerman. Intersection Classes and Multiple Intersection Parameters. — Princeton University, 1984. — (Ph. D thesis)
- Carsten Thomassen. Interval representations of planar graphs // Journal of Combinatorial Theory, Series B. — 1986. — Т. 40 (17 червня). — С. 9–20. — DOI: .
- Mihalis Yannakakis. The complexity of the partial order dimension problem // SIAM Journal on Algebraic and Discrete Methods. — 1982. — Т. 3, вип. 3 (17 червня). — С. 351–358. — DOI: .
- Diptendu Bhowmick, L. Sunil Chandran, Abhijin Adiga. Boxicity and Poset Dimension // SIAM Journal on Discrete Mathematics. — 2011. — Т. 25, вип. 4 (17 червня). — С. 1687—1698. — DOI: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет