Задача 1. Считая данные графы планарными, выяснить, сколько граней получится после преобразования их в плоские:
1) 2)
Задача 2. Выяснить, являются ли данные графы плоскими (планарными).
1) 2)
Задача 3. Выяснить, обладают ли данные графы эйлеровой цепью.
| v1 |
| v2 |
| v2 |
| 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 цветную раскраску вершин, называется хроматическим числом графа и обозначается hB.
Алгоритм решения задачи о раскраске вершин графа
Шаг 1. Вычислить степени всех вершин. Расположить вершины в порядке убывания степеней. Присвоить n=1.
Шаг 2. Окрасить первую неокрашенную вершину в цвет №n.
Шаг 3. Окрасить в цвет № n все вершины, которые не смежны вершинам, уже окрашенным в цвет № n.
Шаг 4. Если все вершины окрашены, то hB=n – искомое хроматическое число.
Иначе n:n+1 и переходим к шагу 2.
Правильная раскраска ребер графа – такая, что никакие два инцидентных ребра графа (имеющих общую вершину) не окрашены в одинаковые цвета.
Минимальное число цветов, необходимое для правильной раскраски ребер графа, называется хроматическим индексом графа hр.
Алгоритм решения задачи о раскраске ребер графа
Шаг 1. Вычислить степени всех вершин. Расположить вершины в порядке убывания степеней. Выбрать вершину с максимальной степенью n.
Шаг 2. Окрасить все ребра, инцидентные этой вершине в n различных цветов.
Шаг 3. Переходим к следующей вершине по списку. Окрашиваем ее ребра.
И так далее.
Процесс продолжается до тех пор, пока не окрасим ребра, инцидентные последней вершине в списке. Если все ребра окрашены, то hр (количество красок) – хроматический индекс.
Справедлива следующая теорема.
Теорема Брукса. Если максимальная степень вершины в графе d, то хроматическое число hB£d+1.
Теорема Визинга. Если максимальная степень вершин в графе d, то хроматический индекс d£ hр£d+1.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1. Чему равно хроматическое число графа?
| v6 |
| v5 |
| v4 |
| v3 |
| v2 |
| v1 |
Решение. Воспользуемся алгоритмом раскраски вершин графа.
1. degv1=4; degv2=4; degv3=3; degv4=2; degv5=5; degv6=2, где degvi – степень i-й вершины. И начнем раскраску с вершины с наибольшей степенью.
2. Окрасим вершину v5 в цвет № 1.
3. Окрасим в цвет №1 все вершины, не смежные с вершиной v5. Таких вершин нет.
4. Выберем следующую вершину с наибольшей степенью из оставшихся. Это или вершина v1 или v2. Возьмем, например, вершину v1 и окрасим ее в цвет №2.
5. Окрасим вершины, не смежные вершине v1 и уже окрашенные в цвет №2. Это вершина v3 или v4. Возьмем, например, вершину v3 и окрасим в цвет №2.
6. Выберем следующую вершину с наибольшей степенью из оставшихся. Такой вершиной является вершина v2. Окрасим ее в цвет №3.
7. Окрасим в цвет №3 вершины, не смежные с вершиной v2 и уже окрашенные в цвет №3. Это вершины v4 и v6.
8. Больше вершин не осталось, а значит, хроматическое число графа hВ=3.
