Монопланарни граф

С Википедије, слободне енциклопедије

У тополошкој теорији графова, монопланарни граф је граф који може бити нацртан у еуклидској равни тако да једна грана може имати највише једно пресецање, и то са само једном граном графа.

Бојење[уреди | уреди извор]

Монопланарне графове први је проучавао Ringel 1965, који је доказао да они могу бити обојени са највише седам боја[1]. Касније је показано да је тачан број боја потребних за бојење ових графова, у најгорем случају, шест[2]. Пример комплетног графа К6, који је монопланаран, показује да монопланарни графови понекад захтевају 6 боја за бојење. Ипак, доказ да је 6 боја увек довољно је знатно компликованији.

Бојење чворова и површи овог графа захтева 6 боја

Рингелова мотивација је био покушај да реши варијацију тоталног бојења за планарне графове, код које се чворови и површи планарног графа боје тако да никоја два суседна чвора, никоја две суседне површи нити чвор и површ суседна њему, немају исту боју. Ово се, свакако може извршити помоћу 8 боја имплементирајући теорему о 4 боје на дати граф и његов дуални граф одвојено, користећи два дисјунктна скупа од по 4 боје. Ипак, мање боја се може добити формирајући помоћни граф који има чвор за сваки чвор или површ датог планарног графа, и у коме су два чвора суседна кадгод они представљају два суседна чвора или површи датог графа. Бојење помоћног графа одговара чвор-површ бојењу оригиналног графа. Добијени помоћни граф је монопланаран, из чега следи да Рингелов проблем чвор-површ бојења може бити решен и са 6 боја.[2] Граф K6' не може бити формиран као помоћни граф на овај начин, али се ипак проблем чвор-површ бојења понекад може решити са 6 боја; на пример, ако је планарни граф који треба обојити троугаона призма, онда њених 11 чворова и површи захтева 6 боја, зато што се не може трима од њих дати једна боја.[3]

Густина грана[уреди | уреди извор]

Сваки монопланарни граф са n чворова има највише 4n − 8 грана.[4] Ова чињеница се може искористити да покаже да комплетан граф К7 са 7 чворова није монопланаран, зато што овај граф има 21 грану и у том случају 4n − 8 = 20 < 21.[5] Монопланарни граф са 4n − 8 грана може бити формиран помоћу планарног графа, нацртан на тај начин да је свака површ четвороугаона, додајући две пресечне дијагонале у сваки четвороугао. Ипак, за разлику од планарних графова, постоји максимални монопланарни граф (графови којима се не може додати грана а да се задржи монопланарност) који има знатно мање грана од 4n − 8.[6]

Комплентни мултипартитивни графови[уреди | уреди извор]

1-planar drawing of the cocktail party graph K2,2,2,2

Потпуна класификација монопланарних комплетних графова, комплетних бипартитивних графова, и још општије- комплетних мултипартитивних графова је позната. Сваки бипартитивни граф форме K2,n је монопланаран, као и сваки комплетни трипартитивни граф форме K1,1,n. Поред ових небројених примера, једини комплетни мултипартитивни монопланарни графови су K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2, и њихови подграфови. Минимални немонопланарни комплетни мултипартитивни графови су K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3. На пример, комплетан бипартитивни граф K3,6 је монопланаран зато што је подграф графа K1,1,1,6, али K3,7 није монопланаран.[5]

Рачунарска сложеност[уреди | уреди извор]

Тестирати да ли је дати граф монопланаран је НП-комплетан проблем, и остаје НП-комплетан чак и за графове добијене додавањем гране планарном графу.[7] У супротности са Феријевом теоремом за планарне графове, не може се сваки монопланарни граф нацртати буквално доцртавањем појединачних грана; ипак, тестирање да ли се монопланарни цртеж кориговати на овај начин може бити урађено у полиномијалном времену.[8]


Генерализација и повезани концепти[уреди | уреди извор]

Монопланарни графови су проширени до к-планарних графова, графова код којих је свака грана пресечена највише к пута. К-планарни графови са n чворова имају највише O(n√k) грана.[9]

Непланарни графови могу такође бити параметризовани помоћу њиховог броја укрштања, минималног броја парова грана које се укрштају у графу. Граф са бројем укрштања к је неминовно к-планаран, али обрнуто не мора да важи. На пример, Хивудов граф има број укрштања 3, али није неминовно да ће сва 3 укрштања бити на једној грани, тако да је тај граф монопланаран, и може бити нацртан на начин да се симултано оптимизује укупан број пресецања и број пресецања по грани.

Референце[уреди | уреди извор]

  1. ^ Ringel, Gerhard (1965), „Ein Sechsfarbenproblem auf der Kugel”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (на језику: German), 29: 107—117, MR 0187232, doi:10.1007/BF02996313 
  2. ^ а б Borodin, O. V. (1984), „Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs”, Metody Diskretnogo Analiza (41): 12—26,108, MR 832128 
  3. ^ Albertson, Michael O.; Mohar, Bojan (2006), „Coloring vertices and faces of locally planar graphs” (PDF), Graphs and Combinatorics, 22 (3): 289—295, MR 2264852, doi:10.1007/s00373-006-0653-4 
  4. ^ Schumacher, H. (1986), „Zur Struktur 1-planarer Graphen”, Mathematische Nachrichten (на језику: German), 125: 291—300, MR 847368 .
  5. ^ а б Czap, Július; Hudák, Dávid (2012), „1-planarity of complete multipartite graphs”, Discrete Applied Mathematics, 160 (4-5): 505—512, MR 2876333, doi:10.1016/j.dam.2011.11.014 
  6. ^ Brandenburg, Franz Josef; Eppstein, David; Gleißner, Andreas; Goodrich, Michael T.; Hanauer, Kathrin; Reislhuber, Josef (2013), „On the density of maximal 1-planar graphs”, Ур.: Didimo, Walter; Patrignani, Maurizio, Proc. 20th Int. Symp. Graph Drawing 
  7. ^ Cabello, Sergio; Mohar, Bojan (2012), Adding one edge to planar graphs makes crossing number and 1-planarity hard, arXiv:1203.5944 Слободан приступ . Expanded version of a paper from the 17th ACM Symposium on Computational Geometry, 2010.
  8. ^ Hong, Seok-Hee; Eades, Peter; Liotta, Giuseppe; Poon, Sheung-Hung (2012), „Fáry's theorem for 1-planar graphs”, Ур.: Gudmundsson, Joachim; Mestre, Julián; Viglas, Taso, Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012, Proceedings, Lecture Notes in Computer Science, 7434, Springer, стр. 335—346, doi:10.1007/978-3-642-32241-9_29 
  9. ^ Pach, János; Tóth, Géza (1997), „Graphs drawn with few crossings per edge”, Combinatorica, 17 (3): 427—439, MR 1606052, doi:10.1007/BF01215922 
Преузето из „https://sr.wikipedia.org/w/index.php?title=Монопланарни_граф&oldid=26943615”