Монопланарни граф — разлика између измена
Нова страница: У тополошкој теорији графова, монопланарни граф је граф који може бити нацртан у еуклидској… |
(нема разлике)
|
Верзија на датум 27. мај 2013. у 21:38
У тополошкој теорији графова, монопланарни граф је граф који може бити нацртан у еуклидској равни тако да једна грана може имати највише једно пресецање, и то са само једном граном графа.
Бојење
Монопланарне графове први је проучавао Ringel (1965), који је доказао да они могу бити обојени са највише седам боја[1]. Касније је показано да је тачан број боја потребних за бојење ових графова, у најгорем случају, шест[2].Пример комплетног графа К6, који је монопланаран, показује да монопланарни графови понекад захтевају 6 боја за бојење. Ипак, доказ да је 6 боја увек довољно је знатно компликованији.
Рингелова мотивација је био покушај да реши варијацију тоталног бојења за планарне графове, код које се чворови и површи планарног графа боје тако да никоја два суседна чвора, никоја две суседне површи нити чвор и површ суседна њему, немају исту боју. Ово се, свакако може извршити помоћу 8 боја имплементирајући теорему о 4 боје на дати граф и његов дуални граф одвојено, користећи два дисјунктна скупа од по 4 боје. Ипак, мање боја се може добити формирајући помоћни граф који има чвор за сваки чвор или површ датог планарног графа, и у коме су два чвора суседна кадгод они представљају два суседна чвора или површи датог графа. Бојење помоћног графа одговара чвор-површ бојењу оригиналног графа. Добијени помоћни граф је монопланаран, из чега следи да Рингелов проблем чвор-површ бојења може бити решен и са 6 боја.[2] Граф K6' не може бити формиран као помоћни граф на овај начин, али се ипак проблем чвор-површ бојења понекад може решити са 6 боја; на пример, ако је планарни граф који треба обојити троугаона призма, онда њених 11 чворова и површи захтева 6 боја, зато што се трима од њих не може дати једна боја.
Референце
- ^ 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.
- ^ а б 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.