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

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

1) 2)

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

1) 2)

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

v1

v2

v2

1) 2)

v5

v4

v3

v1

v5

v3

v4

3)

/ 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. Чему равно хроматическое число графа?

v6

v5

v4

v3

v2

v1

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

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.