ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ. Задача 1. Считая данные графы планарными, выяснить, сколько граней получится после преобразования их в плоские:

Задача 1. Считая данные графы планарными, выяснить, сколько граней получится после преобразования их в плоские:

1) 2)

Задача 2. Выяснить, являются ли данные графы плоскими (планарными).

1) 2)

Задача 3. Выяснить, обладают ли данные графы эйлеровой цепью.

v₁

v₂

1) 2)

v₅

v₄

v₃

v₁

v₅

v₃

v₄

/ AwBQSwMEFAAGAAgAAAAhALKwO5beAAAACQEAAA8AAABkcnMvZG93bnJldi54bWxMj8FOwzAQRO9I /IO1SNyok6oJJcSpUCW4cKEBpHJz4yUOxHZku2n692xO5bgzo9k35WYyPRvRh85ZAekiAYa2caqz rYCP9+e7NbAQpVWydxYFnDHAprq+KmWh3MnucKxjy6jEhkIK0DEOBeeh0WhkWLgBLXnfzhsZ6fQt V16eqNz0fJkkOTeys/RBywG3Gpvf+mgE7NKvvX6Vvh55lr+8/ZzTbT59CnF7Mz09Aos4xUsYZnxC h4qYDu5oVWC9gOX9AyVJTzJgs5+taMphFtIV8Krk/xdUfwAAAP//AwBQSwECLQAUAAYACAAAACEA toM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQA BgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVsc1BLAQItABQA BgAIAAAAIQAxc6vpHAIAAEwEAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9jLnhtbFBLAQIt ABQABgAIAAAAIQCysDuW3gAAAAkBAAAPAAAAAAAAAAAAAAAAAHYEAABkcnMvZG93bnJldi54bWxQ SwUGAAAAAAQABADzAAAAgQUAAAAA " strokecolor="black [3040]">

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

И характеристический индекс графа

Многие задачи о графах формулируются в терминах цветов, красок. Граф допускает правильную n-цветную раскраску вершин, если его вершины можно раскрасить n разными красками так, чтобы никакие две смежные вершины не имели m одинаковый цвет. минимальное число n, при котором граф G допускает n цветную раскраску вершин, называется хроматическим числом графа и обозначается h_B.

Алгоритм решения задачи о раскраске вершин графа

Шаг 1. Вычислить степени всех вершин. Расположить вершины в порядке убывания степеней. Присвоить n=1.

Шаг 2. Окрасить первую неокрашенную вершину в цвет №n.

Шаг 3. Окрасить в цвет № n все вершины, которые не смежны вершинам, уже окрашенным в цвет № n.

Шаг 4. Если все вершины окрашены, то h_B=n – искомое хроматическое число.

Иначе n:n+1 и переходим к шагу 2.

Правильная раскраска ребер графа – такая, что никакие два инцидентных ребра графа (имеющих общую вершину) не окрашены в одинаковые цвета.

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

Алгоритм решения задачи о раскраске ребер графа

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

Шаг 2. Окрасить все ребра, инцидентные этой вершине в n различных цветов.

Шаг 3. Переходим к следующей вершине по списку. Окрашиваем ее ребра.

И так далее.

Процесс продолжается до тех пор, пока не окрасим ребра, инцидентные последней вершине в списке. Если все ребра окрашены, то h_р (количество красок) – хроматический индекс.

Справедлива следующая теорема.

Теорема Брукса. Если максимальная степень вершины в графе d, то хроматическое число h_B£d+1.

Теорема Визинга. Если максимальная степень вершин в графе d, то хроматический индекс d£ h_р£d+1.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1. Чему равно хроматическое число графа?

v₆

v₅

v₄

v₃

v₂

v₁

Решение. Воспользуемся алгоритмом раскраски вершин графа.

1. degv₁=4; degv₂=4; degv₃=3; degv₄=2; degv₅=5; degv₆=2, где degv_i – степень i-й вершины. И начнем раскраску с вершины с наибольшей степенью.

2. Окрасим вершину v₅ в цвет № 1.

3. Окрасим в цвет №1 все вершины, не смежные с вершиной v₅. Таких вершин нет.

4. Выберем следующую вершину с наибольшей степенью из оставшихся. Это или вершина v₁ или v₂. Возьмем, например, вершину v₁ и окрасим ее в цвет №2.

5. Окрасим вершины, не смежные вершине v₁ и уже окрашенные в цвет №2. Это вершина v₃ или v₄. Возьмем, например, вершину v₃ и окрасим в цвет №2.

6. Выберем следующую вершину с наибольшей степенью из оставшихся. Такой вершиной является вершина v₂. Окрасим ее в цвет №3.

7. Окрасим в цвет №3 вершины, не смежные с вершиной v₂ и уже окрашенные в цвет №3. Это вершины v₄ и v₆.

8. Больше вершин не осталось, а значит, хроматическое число графа h_В=3.