графика оцветяване
Боята може двата края на графиката и върховете. Първо докосване на проблема с оцветяването на върховете. в същото време ние вярваме, че графиката не е фокусиран и не е мултиграф.
Задача. Оцветете върховете, така че всеки два съседни върха са боядисани в различни цветове, с броя на използваните цветове трябва да е най-ниска. Този брой се нарича хроматичната (цвят) брой на графика, който ще бъде означен с = а (G) (ако G - графиката). Ако номер К а. графиката е к-правдоподобен.
Grundy функция е функция на върховете на графика, показваща пикове на снимачната площадка, а ако XI на връх боядисан в цвят номер к. на Grundy функция H (XI) = к.
Ясно е, че за хроматичната броя на графика е единствената, но Grundy функции могат да бъдат много. Разбира се, да се намери най-малко една функция Grande - което означава да се намери един от възможните "най-добрите" оцветителите (като оцветяване може да бъде много).
Имайте предвид, че ако графиката е пълна, т.е. всякакви два върха са съседни, хроматичната броя на графиката е равна на, където п -... Броят на върховете.
За по-нататъшно нужда следното определение.
Набор от върховете се нарича максимално независим набор (MNS), ако има такива два върха на този набор не са съседни и не могат да бъдат включени в този комплект е запазена друг връх до това състояние. Имайте предвид, че присъствието НОН в графиката е съвсем проста: да вземе произволен връх, а след това да намеря най-добре, а не в непосредствена близост до него, и след това да се намери на върха, който не е свързан към избраните възли и т.н. Естествено, МНС в тази графа може да бъде много и те са .. може да съдържа различен брой върхове.
Сега ние описваме един алгоритъм за намиране на най-доброто боядисване на върха. Да предположим, че има графика G. намерите в него всеки MHC, който е обозначен с S1. и всички възли, които са в МНС, боядисани в цвят № 1. Освен това, се отстранява от тази графика всички възли, които са в МНС (с перки), и отново да се намери нов графика МНС, означен S2. Тези нови пикове подчертани в цвят № 2, след премахване на върха от графиката, заедно със съответните ребра и отново определят MHC, която се обозначава с цвят № 3, и така нататък. Е. Може да бъде показано, че се стигне до най-оцветяване за всеки метод на тази процедура, и да намерят някаква функция Grundy и хроматичната броя на графиката.
Пример. Брой (. Фигура 9) има максимум 3 независими системи на върха, и. Ясно е, че за произволен брой процедури за намиране на наситеността на цвета в тази графика, ние получаваме числото 3.
Теорема Ако максималната степен на върховете в графиката е равна г. хроматичната броя на графиката е не по-голяма от R + 1. В този случай, хроматичната броя на графиката е равен на R + 1 само в два случая: първо, ако графиката е пълно, и от друга страна, ако R = 2 и където активният верига съдържа Брой нечетен дължина (например графика е показано на Фигура 10, максималната степен на върховете -. 2 и хроматичната брой - 3). Във всички останали случаи, хроматичната броя на графиката не надвишава максималната степен.
Забележка. Прогноза за хроматичната номер, даден от тази теорема е доста груб. Особено визуално изглежда в примера на дърво (Sec. 14), за които степента на върха може да бъде произволно голям и хроматичната брой е 2.
Обсъдени бяха въпроси са свързани с добре познатия четиризвезден цвят теорема. За да го формулира, се нуждаем от още няколко дефиниции.
Графиката се нарича планарна ако е изготвен на самолета, както и всички ребра 2 могат да се пресичат само в горната част.
Графиките са изоморфни. ако съществува номерация на върховете в тези графики, че те имат същата близост матрица (в действителност изоморфни графики - графики е същото, различаващи се само друго изображение).
Графиката се нарича планарна. ако е изоморфни на равнината графика. По този начин, планарна графиката може да се направи в равнината като равнина. Фиг. 11 показва две изоморфни (същото) графика, с първата от тях равнина, а другият е плосък.
Трябва да се отбележи най-известният тълкуването на проблема с четири цвят. Нека има географска карта. Възможно ли е, като се използват само четири цвята, за да представляват картата така, че съседните страни (които имат обща граница) са боядисани в различен цвят? Ясно е, че в съответните графиката върховете са на страната и съседните върхове са съседните страни. Ясно е, че в резултат на графиката е равнинен, а след 1976 г. Отговорът на този въпрос е положителен.
Имайте предвид, че на теория графика често поставя въпроса на ръба оцветяване на графики. Какъв е минималният брой цветове (този брой се понякога се нарича един ръб-хроматичната), което трябва да се боя ръбовете на графиката, така че всеки две съседни ръбове (т.е.. Д. 2 ръбове с общ връх) ще бъдат боядисани в различен цвят? За край хроматичната брой графика държи много по-точна оценка не просто хроматичната броя, а именно следното е вярно до известна степен изненадващо, теорема.
Vizinga теорема. Ако графика максимална степен се равнява на р. номер край хроматичната е равна или R. или R 1.
Имайте предвид, че все още няма "добри" критерии за графики къде точно край хроматичната брой е равен на р. и когато R + 1.
Очевидно е, че най-простият алгоритъм за намиране край хроматичната номер (и съответните ръбове на оцветяване) е следната: в графиката изграждане на така наречената двойна графика: ръбове на графиката съответстват на върховете на нов (двойно) на графиката, и ако двете ребра имат общ връх, те са съседни и в двойна графиката са свързани с предимство. След това най-добрият цвят горната част на графиката и двойна, отидете на "старите" граф, получаваме (евентуално) най-добрите ребрата оцветителите на графики.
В заключение, оцветяване на ръба често се използва в строителството на различни устройства, където от кабела по един връх задължително (за удобство) имат различни цветове.
Свързани статии