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

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

(18.5)

так, чтобы любые две смежные вершины принадлежали разным подмножествам, т.е. чтобы рёбра графа соединяли вершины из разных подмножеств

(18.6)

Отметим все вершины индексами (т.е. раскрасим вершины цветами), причём вершины внутри каждого подмножества помечают одним индексом (раскрашивают одним цветом). Подмножества формируют таким образом, чтобы концы любого ребра графа имели различные индексы.

Наименьшее возможное число подмножеств, получаемое в результате такого разбиения вершин графа , называют хроматическим числом графа , граф называют - хроматическим,а выражения (18.5) и (18.6)- хроматическим разложением .

Особое значение имеет частный вид - хроматического графа - бихроматический или двудольный граф, для которого множество вершин можно разбить на два непересекающихся подмножества и так, чтобы никакое ребро не соединяло бы вершины одного и того же подмножества, т.е.

(18.7)

Такие графы называют графами Кёнига и обозначают .

Критерий бихроматичности произвольного графа формулируется теоремой Кёнига, согласно которой обыкновенный граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечётной длины.

Если граф - дерево, т.е. в нём полностью отсутствуют циклы (существуют лишь циклы нулевой длины), то он является бихроматическим графом и может быть представлен в виде двудольного графа (рис. 18.1).

Граф Кёнига называют полным, если каждая вершина смежна с каждой вершиной и наоборот.

Рис. 18.1. Пример двудольного графа

Пример. Рассмотрим пример бихроматического графа , у которого

Рис. 18.2. Бихроматический граф

При добавлении к этому графу рёбер , , , и получим полный бихроматический граф. Очевидно, что подмножество множества вершин можно раскрасить в один цвет, а - в другой.

Число рёбер полного бихроматического графа

При составлении целого ряда алгоритмов проектирования РЭС используют операцию удаления некоторых вершин и рёбер графа. При этом особое значение приобретает понятие критического графа.

Граф называют критическим, если удаление любой вершины с инцидентными ей рёбрами уменьшает хроматическое число графа.

Критическим - хроматическим графом является одна вершина; критическим 2 - хроматическим - две вершины, соединённые ребром; критическим - хроматическим - простой цикл нечётной длины, так как при удалении из него любой вершины с инцидентными ей рёбрами получим двудольный граф. Очевидно, что полный граф всегда является критическим, причём его хроматическое число равно

В отличие от цикломатического числа определение хроматического числа осуществляется с помощью сравнительно сложных алгоритмов, в основу большинства которых положены методы целочисленного линейного программирования.

Оценка хроматического числа через число вершин графа имеет вид:

В этом выражении нижняя граница соответствует пустым, а верхняя - полным графам.

На практике для простых связных графов оценить величину можно следующим образом.

Сначала выбираем вершину с минимальной локальной степенью и пометим (раскрасим) её, затем произведём хроматическую раскраску вершин, смежных с данной, и так далее.

Например, для графа на рис. 18.2, б сначала выбираем вершину для которой , и раскрасим её в красный цвет. Тогда вершину можно раскрасить в синий цвет, а вершины и - в красный (они не смежны с ). Вершины и можно раскрасить в синий цвет, а оставшиеся вершины - в жёлтый. На раскраску вершин графа пошло три краски .

Знание хроматического числа графа позволяет в ряде случаев упростить алгоритмы, используемые на этапе конструкторского проектирования РЭС.

Пример. Рассмотрим задачу оценки числа слоёв многослойной печатной платы. Пусть, граф интерпретирует фрагмент коммутационного поля платы, где х - множество областей контактных площадок конструктивных элементов, внутри которых проведение проводников запрещено, a - множество трасс платы.

Построим граф пересечений , в котором вершинами являются отдельные компоненты связности (электрические цепи) графа , причём смежны, если соответствующие им компоненты связности и перекрывают друг друга.

При этом хроматическое число графа определит верхнюю границу числа коммутационных слоев рассматриваемого фрагмента платы (в нашем примере ). В этом случае цепи, соответствующие вершинам одного цвета графа , можно располагать в одном слое печатной платы.

Дата добавления: 2013-12-13