Хроматическое число

Пусть задан граф без петель. Разобьём множество его вершин на n непере­секающихся подмножеств:

Х₁, Х₂,..., Х_n =UХ_i

Для любого х_i, х_jÎХ [х_i∩х_j=Æ], так что любые две вершины из Х принадле­жат разным подмножествам, т.е., чтобы рёбра графа G(X,U) соединяли вершины из разных подмножеств. Отметим все вершины индексами 1,2,...,к, т.е. раскрасим все вершины n-цветами, причём вершины внутри каждого помечают одним ин­дексом или раскрашивают одним цветом.

Пусть имеется граф, вершины которого окрашены соответственно:

- синий

- красный

- зелёный

Хроматическое число – наимень­шее возможное число подмножеств, по­лучаемое в результате такого разбиения вершин графа, при этом оно обозначается k(G), а граф k – хроматическим.

Бихроматическим или двудольным гра­фом – называется граф, для которого множество вершин Х можно разбить на два непересекающихся подмножества х₁∩х₂=Æ, где для любого х_i,х_jÎХ [х_iÎХ₁ и х_jÎХ₂ и (х_i,х_j)= u_jÎU, х_iÎХ₂ или х_jÎХ₁].

Такие графы называются графами Кенинга. Если граф – дерево, то он является бихрома­тическим.

- Гамильтонов граф – цикл включает все вершины графа

- Эйлеров граф – граф включает все рёбра графа

28. Алгоритм раскраски графа методом поэлементной дизъюнкции.