Пример 2.14

На рис. 2.26 приведен граф Питерсена, который гомеоморфный графу K₅ (граф K₅ может быть получен из графа Питерсена 5 -кратным применением операции стягивания ребра). Следовательно, согласно теореме 2.14 он не является планарным.

2.6. Раскраска графов

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

Ø Раскраска вершин

Ø Верхняя и нижняя оценка хроматического числа

Ø Раскрашивание планарных графов

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

В приложениях графов к решению практических задач часто возникает необходимость разбиения множества вершин (ребер) на классы с помощью задания на этом множестве некоторого отношения эквивалентности.

Правильной раскраской вершин графаG = (V, E) в g цветов называется разбиение { V₁, V₂, …, V_g } множества V такое, что для любого i = 1, 2, …, g вершины, принадлежащие подмножеству V_i, попарно несмежные и окрашены в i -й цвет.

Раскраска называется неправильной, если в одно множество разбиения попадают смежные вершины.

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

Замечание. Всякий подграф правильно раскрашенного графа правильно раскрашен.

Граф k - раскрашиваем, если его можно правильно раскрасить не более, чем в k цветов.

Пусть g_i (G) – количество правильных раскрасок вершин графа G в i цветов.

Хроматическим числом g (G) графа G называется наименьшее из чисел g из всех возможных правильных его раскрасок, т.е.

g (G) = min { i | g_i (G) ¹ 0 }

Хроматическое число графа относится к классу трудно вычислимых инвариантов заданного графа.

Раскраска вершин

Граф G с хроматическим числом g (G) = 2 называется бихроматическим.

Теорема 2.15. Граф G – двудольный тогда и только тогда, когда он бихроматический граф.

---

Дата добавления: 2015-07-20