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

Опр1: Пусть -граф, тогда раскраской этого графа называется окрашивание вершин графа, такое, что никакие 2 смежные вершины не имеют одинаковый цвет, пусть - это кол-во способов раскраски графа в цветов, таких что никакие 2 смежные вершины не имеют один цвет. Для фиксированного графа , - полиномиальная ф-ия от , называемая хроматическим многочленом графа. Опр2: Хроматическое число графа это наименьшее число цветов, исп. для раскраски графа, т.е. наим. полож. . Теорема Хивуда: произв. планарный граф можно раскрасить исп. только 5 цветов. Док-во: пусть - связ. планарный граф, исп. индукцию по кол-ву вершин. Если 1 вершина (т.е. 5 и меньше), то граф раскрашивается в 5 цветов. Предположим, что при раскр. произв. графа с вершинами, исп. 5 цветов. Пусть - граф с вершиной ,тогда у этого графа есть вершина степени 5 и менее, пуст эта вершина , пусть - подграф графа в котором удалена вершина и инцинд. ей ребра. Поскольку в вершин, то по индукции его можно раскрасить в 5 цветов, если степень , то в графе она смежна вершинам, её можно раскрасить цветом, отлич. от смежных вершин. Т.о. раскраска завершена. Пусть степень , тогда она смежна с 5ю вершинами , если какие-нибудь из них имеют одинаковый цвет, то для их раскраш. исп. 4 цвета и можно исп. оставшийся для . Завершена раскраска. Если раскрашены в 5 цветов, тогда пусть цвет, и т.д. Пусть для определенности расположены вокруг . Начиная с графа построим , как подграф след. образом: мн-во вершин состоит из и всех вершин , которые могут быть связаны с путями, проходящими через вершины с цветом 1 и 3. Пусть по построению не сод. Вершины раскраш. в 1 или 3 цвет, которые бы и явл. смеж. с вершинами из поэтому в можно поменять местами, не меняя цвета отсав. Вершин, тогда будут одного цвета и по полученному ранее результату - раскрашен. Если , то путь , который проход. только через вершину окрашенную цветом 1 или 3 , раз этот путь , тогда путь будет цикл. В первом случае будет внутри цикла, во втором внутри, т.о. можно раскр. В 5 цветов. Алгоритм раскраски: 1) произвольная вершина графа принимает цвет №1 2) если вершины раскр. цветами, то новой любой вершине припишем миним. цвет не исп. при раскраске вершин из мн-ва смежных к данной. Реберная раскраска графов: Граф называется -раскрашиваемым, если его ребра можно раскрасить в цветов т.о., что никакие 2смежных ребра не окажутся одного цвета. Если граф реберно раскрашиваем, но не явл. , то - наз. хроматическим индексом или реберно-хроматическим числом графа . При этом исп. запись . Если наиб. из степеней графа равна , то .