6.7. Хроматика на графики

6.7.1. Хроматично число

Нека е необходимо да оцветите върховете на графа така, че всеки два съседни върха да бъдат оцветени в различни цветове, като броят на използваните цветове трябва да бъде най-малък.

Това число се нарича хроматично число на графиката, ще го обозначим h ( G ). Ако h (G) =k, тогава графиката се нарича k-

Обърнете внимание, че ако даденият граф е пълен, т.е. всеки два върха са съседни, тогава хроматичното число на такъв граф е n, където n е броят на върховете.

върхове

Има няколко алгоритъма за намиране на точната стойност

хроматично число. Един от тях се основава на метода за намиране на най-малкото покритие.

Тъй като за всяко допустимо оцветяване на графа G, множеството от върхове, оцветени с един и същи цвят, трябва да бъде независимо множество, тогава всяко допустимо оцветяване може да се интерпретира като разделяне на всички върхове на графа G в такива независими множества. Освен това, ако всяко независимо множество се разшири до максимален (чрез добавяне на други върхове към него), тогава оцветяването на G може да се интерпретира като покриване на върховете на G с максимални независими върхове набори (празни подграфи). Очевидно в последния случай някои върхове на графа G могат да принадлежат на повече от едно максимално независимо множество (празен подграф). Това предполага, че може да има различни допустими оцветявания (използвайки същия брой цветове), тъй като връх, принадлежащ на различни максимални множества, може да бъде оцветен във всеки от цветовете, съответстващи на множествата, към които принадлежи.

И така, нека всички максимални независими набори от граф G са конструирани (нека има t такива набора) и нека ( n × t ) матрица M = < m ij >, за което m ij =1, аковръх x i принадлежи на максималното независимо множество, а m ij =0 в противен случай. Ако сега присвоим единична цена на всеки максимален независим набор, тогава проблемът с оцветяването се свежда просто до проблема за намиране на най-малкия брой колони в матрицата M, които покриват всички нейни редове x. Всяка колона от решението