Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

У теорії графів інтервальна розмірність графа це інваріант графа введений Фредом С Робертсом у 1969 році Граф перетинів

Інтервальна розмірність графа

Інтервальна розмірність графа

У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році.

image
Граф перетинів прямокутників з інтервальною розмірністю два

Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини.

Приклади

На рисунку показано граф із шістьма вершинами і подання цього графа у вигляді графа перетинів (звичайних двовимірних) прямокутників. Цей граф можна подати у вигляді графа перетинів прямокутників меншої розмірності (в даному випадку — відрізків), так що інтервальна розмірність графа дорівнює двом.

Робертс показав, що граф з 2n вершинами, утворений видаленням досконалого парування з повного графа з 2n вершинами, має інтервальну розмірність рівно n — будь-яку пару нез'єднаних вершин слід подати у вигляді гіперпрямокутників, які мають бути розділені у відмінному від іншої пари вимірі. Подання цього графа у вигляді гіперпрямокутників з розмірністю рівно n можна знайти потовщенням кожної з 2n граней n-вимірного гіперкуба до гіперпрямокутника. Тому такі графи почали називати графами Робертса, хоча вони відоміші як графи вечірки і їх можна трактувати також як графи Турана T(2n,n).

Зв'язок з іншими класами графів

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

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

Алгоритмічні результати

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

Однак знаходження таких подань може виявитися складним — перевірка, чи не перевершує інтервальна розмірність заданого графа деякої наперед заданої величини K, є NP-повною задачею, навіть для K = 2. Чандран, Френсіс і Сівадасан описали алгоритми знаходження подань довільних графів у вигляді графа перетинів гіперпрямокутників з розмірністю в межах логарифмічного множника найбільшого степеня графа. Цей результат дає верхню межу інтервальної розмірності графа.

Попри труднощі для природних параметрів, інтервальна розмірність графа є [en], якщо параметризацію проводити за числом вершинного покриття вхідного графа.

Примітки

  1. Roberts, 1969.
  2. Наприклад, див. статті Чандрана, Френсіса і Сівадасана (Chandran, Francis, Sivadasan, (2010)), Чандрана і Сівадасана Chandran, Sivadasan, (2007).
  3. Scheinerman, 1984.
  4. Thomassen, 1986.
  5. Bellantoni, Hartman, Przytycka, Whitesides, 1993.
  6. Чандран, Френсіс і Сівадасан (Chandran, Francis, Sivadasan, (2010)) зауважили, що це випливає з факту, що ці графи мають поліноміальне число максимальних клік. Явне подання у вигляді перетину гіперпрямокутників не вимагає перерахування всіх максимальних клік.
  7. Див., наприклад, статті Agarwal, van Kreveld, Suri, (1998) і Berman, DasGupta, Muthukrishnan, Ramaswami, (2001) щодо апроксимації найбільшої незалежної множини для графів перетинів прямокутників, і Chlebík, Chlebíková, (2005) з обговоренням складності апроксимації цих задач для більших розмірностей.
  8. Коззенс (Cozzens, (1981)) показав, що обчислення інтервальної розмірності графа є NP-повною задачею. Яннакакіс (Yannakakis, (1982)) показав, що навіть перевірка, чи не перевищує інтервальна розмірність величини 3, є NP-складною. Нарешті, Краточвіл (Kratochvíl, (1994)) показав, що розпізнавання інтервальної розмірності = 2 є NP-складною задачею.
  9. Chandran, Francis, Sivadasan, 2010.
  10. 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:10.1007/978-3-642-17517-6_33.[недоступне посилання з червня 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:10.1016/S0925-7721(98)00028-5.
  • Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Teresa Przytycka, Sue Whitesides. Grid intersection graphs and boxicity // . — 1993. — Т. 114, вип. 1–3 (17 червня). — С. 41–49. — DOI:10.1016/0012-365X(93)90354-V.
  • 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:10.1006/jagm.2001.1188.
  • 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:10.1007/s00453-008-9163-5.
  • L. Sunil Chandran, Naveen Sivadasan. Boxicity and treewidth // . — 2007. — Т. 97, вип. 5 (17 червня). — С. 733–744. — (). — arXiv:math.CO/0505544. — DOI:10.1016/j.jctb.2006.12.004.
  • 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:10.1016/0166-218X(94)90143-0.
  • M. Quest, G. Wegner. Characterization of the graphs with boxicity ≤ 2 // Discrete Mathematics. — 1990. — Т. 81, вип. 2 (17 червня). — С. 187–192. — DOI:10.1016/0012-365X(90)90151-7.
  • 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:10.1016/0095-8956(86)90061-4.
  • Mihalis Yannakakis. The complexity of the partial order dimension problem // SIAM Journal on Algebraic and Discrete Methods. — 1982. — Т. 3, вип. 3 (17 червня). — С. 351–358. — DOI:10.1137/0603036.
  • Diptendu Bhowmick, L. Sunil Chandran, Abhijin Adiga. Boxicity and Poset Dimension // SIAM Journal on Discrete Mathematics. — 2011. — Т. 25, вип. 4 (17 червня). — С. 1687—1698. — DOI:10.1137/100786290.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

U teoriyi grafiv intervalna rozmirnist grafa ce invariant grafa vvedenij Fredom S Robertsom u 1969 roci Graf peretiniv pryamokutnikiv z intervalnoyu rozmirnistyu dva Intervalna rozmirnist grafa ce minimalna rozmirnist v yakij zadanij graf mozhna podati u viglyadi grafa peretiniv giperpryamokutnikiv tobto bagatovimirnih pryamokutnih paralelepipediv z paralelnimi osyam rebrami Tobto maye isnuvati vidpovidnist odin do odnogo mizh vershinami grafa ta mnozhinoyu giperpryamokutnikiv takih sho pryamokutniki peretinayutsya todi j lishe todi koli isnuye rebro yake z yednuye vidpovidni vershini PrikladiNa risunku pokazano graf iz shistma vershinami i podannya cogo grafa u viglyadi grafa peretiniv zvichajnih dvovimirnih pryamokutnikiv Cej graf mozhna podati u viglyadi grafa peretiniv pryamokutnikiv menshoyi rozmirnosti v danomu vipadku vidrizkiv tak sho intervalna rozmirnist grafa dorivnyuye dvom Roberts pokazav sho graf z 2n vershinami utvorenij vidalennyam doskonalogo paruvannya z povnogo grafa z 2n vershinami maye intervalnu rozmirnist rivno n bud yaku paru nez yednanih vershin slid podati u viglyadi giperpryamokutnikiv yaki mayut buti rozdileni u vidminnomu vid inshoyi pari vimiri Podannya cogo grafa u viglyadi giperpryamokutnikiv z rozmirnistyu rivno n mozhna znajti potovshennyam kozhnoyi z 2n granej n vimirnogo giperkuba do giperpryamokutnika Tomu taki grafi pochali nazivati grafami Robertsa hocha voni vidomishi yak grafi vechirki i yih mozhna traktuvati takozh yak grafi Turana T 2n n Zv yazok z inshimi klasami grafivGraf maye intervalnu rozmirnist ne bilshe odinici todi i tilki todi koli vin ye intervalnim grafom Intervalna rozmirnist dovilnogo grafa G ce najmenshe chislo intervalnih grafiv z tiyeyu zh mnozhinoyu vershin sho i G takih sho peretin mnozhin reber intervalnih grafiv daye G Intervalna rozmirnist bud yakogo zovniplanarnogo grafa ne perevishuye dvoh a bud yakogo planarnogo grafa troh Yaksho dvochastkovij graf maye intervalnu rozmirnist dva jogo mozhna podati u viglyadi grafa peretiniv paralelnih osyam vidrizkiv na ploshini Algoritmichni rezultatiBagato zadach na grafah mozhna rozv yazati abo aproksimuvati efektivnishe na grafah z obmezhenoyu intervalnoyu rozmirnistyu Napriklad zadachu pro najbilshu kliku dlya grafiv z obmezhenoyu intervalnoyu rozmirnistyu mozhna rozv yazati za polinomialnij chas Dlya deyakih inshih zadach na grafah efektivnij rozv yazok abo aproksimaciyu mozhna znajti yaksho isnuye podannya u viglyadi peretinu giperbagatogrannikiv maloyi rozmirnosti Odnak znahodzhennya takih podan mozhe viyavitisya skladnim perevirka chi ne perevershuye intervalna rozmirnist zadanogo grafa deyakoyi napered zadanoyi velichini K ye NP povnoyu zadacheyu navit dlya K 2 Chandran Frensis i Sivadasan opisali algoritmi znahodzhennya podan dovilnih grafiv u viglyadi grafa peretiniv giperpryamokutnikiv z rozmirnistyu v mezhah logarifmichnogo mnozhnika najbilshogo stepenya grafa Cej rezultat daye verhnyu mezhu intervalnoyi rozmirnosti grafa Popri trudnoshi dlya prirodnih parametriv intervalna rozmirnist grafa ye en yaksho parametrizaciyu provoditi za chislom vershinnogo pokrittya vhidnogo grafa PrimitkiRoberts 1969 Napriklad div statti Chandrana Frensisa i Sivadasana Chandran Francis Sivadasan 2010 Chandrana i Sivadasana Chandran Sivadasan 2007 Scheinerman 1984 Thomassen 1986 Bellantoni Hartman Przytycka Whitesides 1993 Chandran Frensis i Sivadasan Chandran Francis Sivadasan 2010 zauvazhili sho ce viplivaye z faktu sho ci grafi mayut polinomialne chislo maksimalnih klik Yavne podannya u viglyadi peretinu giperpryamokutnikiv ne vimagaye pererahuvannya vsih maksimalnih klik Div napriklad statti Agarwal van Kreveld Suri 1998 i Berman DasGupta Muthukrishnan Ramaswami 2001 shodo aproksimaciyi najbilshoyi nezalezhnoyi mnozhini dlya grafiv peretiniv pryamokutnikiv i Chlebik Chlebikova 2005 z obgovorennyam skladnosti aproksimaciyi cih zadach dlya bilshih rozmirnostej Kozzens Cozzens 1981 pokazav sho obchislennya intervalnoyi rozmirnosti grafa ye NP povnoyu zadacheyu Yannakakis Yannakakis 1982 pokazav sho navit perevirka chi ne perevishuye intervalna rozmirnist velichini 3 ye NP skladnoyu Nareshti Kratochvil Kratochvil 1994 pokazav sho rozpiznavannya intervalnoyi rozmirnosti 2 ye NP skladnoyu zadacheyu Chandran Francis Sivadasan 2010 Adiga Chitnis Saurabh 2010 LiteraturaAbhijin Adiga Rajesh Chitnis Saket Saurabh Algorithms and Computation 21st International Symposium ISAAC 2010 Jeju Island Korea December 15 17 2010 Proceedings Part I 2010 T 6506 S 366 377 Lecture Notes in Computer Science DOI 10 1007 978 3 642 17517 6 33 nedostupne posilannya z chervnya 2018 Pankaj K Agarwal Marc van Kreveld Subhash Suri Label placement by maximum independent set in rectangles 1998 T 11 vip 3 4 17 chervnya S 209 218 DOI 10 1016 S0925 7721 98 00028 5 Stephen J Bellantoni Irith Ben Arroyo Hartman Teresa Przytycka Sue Whitesides Grid intersection graphs and boxicity 1993 T 114 vip 1 3 17 chervnya S 41 49 DOI 10 1016 0012 365X 93 90354 V Piotr Berman B DasGupta S Muthukrishnan S Ramaswami Efficient approximation algorithms for tiling and packing problems with rectangles J Algorithms 2001 T 41 vip 2 17 chervnya S 443 47 DOI 10 1006 jagm 2001 1188 L Sunil Chandran Mathew C Francis Naveen Sivadasan Geometric representation of graphs in low dimension using axis parallel boxes Algorithmica 2010 T 56 vip 2 17 chervnya S 129 140 arXiv cs DM 0605013 DOI 10 1007 s00453 008 9163 5 L Sunil Chandran Naveen Sivadasan Boxicity and treewidth 2007 T 97 vip 5 17 chervnya S 733 744 arXiv math CO 0505544 DOI 10 1016 j jctb 2006 12 004 Miroslav Chlebik Janka Chlebikova Proceedings of the Sixteenth Annual ACM SIAM Symposium on Discrete Algorithms 2005 S 267 276 M B Cozzens Higher and Multidimensional Analogues of Interval Graphs Rutgers University 1981 Ph D thesis Jan Kratochvil A special planar satisfiability problem and a consequence of its NP completeness Discrete Applied Mathematics 1994 T 52 vip 3 17 chervnya S 233 252 DOI 10 1016 0166 218X 94 90143 0 M Quest G Wegner Characterization of the graphs with boxicity 2 Discrete Mathematics 1990 T 81 vip 2 17 chervnya S 187 192 DOI 10 1016 0012 365X 90 90151 7 F S Roberts Recent Progress in Combinatorics W T Tutte Academic Press 1969 S 301 310 ISBN 978 0 12 705150 5 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 T 40 17 chervnya S 9 20 DOI 10 1016 0095 8956 86 90061 4 Mihalis Yannakakis The complexity of the partial order dimension problem SIAM Journal on Algebraic and Discrete Methods 1982 T 3 vip 3 17 chervnya S 351 358 DOI 10 1137 0603036 Diptendu Bhowmick L Sunil Chandran Abhijin Adiga Boxicity and Poset Dimension SIAM Journal on Discrete Mathematics 2011 T 25 vip 4 17 chervnya S 1687 1698 DOI 10 1137 100786290

Дата публікації:
Топ