37. Раскраска графов. Планарные графы.

Пусть G=<M,R> - неорграф без петель. Раскраской (вершин) графа G называют такое задание цветов вершинам G, что если [a,b] – ребро, то вершины a и b имеют различные цвета. Хроматическим числом χ(G) графа G называется минимальное число цветов, требующееся для раскраски графа G.

Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин реберного мультиграфа L(G). Для произвольного неориентированного мультиграфа G=<M,U,P> реберным мультиграфом называется тройка L(G)=<U,M,P’>, где , и тогда и только тогда, когда в мультиграфе G вершина u является концом ребер u и v.

Неорграф G называется бихроматическим, если χ(G)=2. Неорграф G=<M,R> называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин {M₁,M₂} концы любого ребра принадлежат разным частям разбиения.

Теорема: Пусть G – неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны:

1. G – бихроматический граф;

2. G – двудольный граф;

3. G не содержит циклов нечетной длины.

Следствие: Если G – лес, то χ(G)≤2.

Теорема: Для любого неорграфа без петель выполняется неравенство χ(G)≤deg(G)+1.

Алгоритм последовательной раскраски:

1. Произвольная вершина a₁ графа G принимает цвет 1.

2. Если вершины a₁,…,a_i раскрашены l цветами 1,2,…,l, l≤2, то новой произвольно взятой вершине a_i+1 припишем миимальный цвет, не использованный при раскраске вершин из множества {a_j|ρ(a_j,a_i+1)=1,j<i}.

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

Рассмотрим операцию подразбиения ребра в графе G=<M,R>. После подразбиения ребра [a,b] из R получается граф G’=<M’,R’>, где , , т.е. ребро [a,b] заменяется на (a,b)-цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер.

Критерий планарности (теорема Понтрягина-Куратовского): Граф G планарен тогда и только тогда, когда G не содержит подграфа, гомеоморфного K₅ или K_3,3 (или подграфов, стягиваемых к K₅ или K_3,3, т.е. получаемых последовательным отождествлением связанных друг с другом вершин).

Теорема: Любой конечный граф может быть расположен в трехмерном пространстве без пересечения ребер.

Если G – планарный граф, то χ(G)≤4.

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

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