Спирина, М.С. Дискретная математика

G G' a 6 Рис. 2.8. Планарные графы: a — первоначальный; б — изображенный иначе На (рис. 2.8, а) граф G является планарным, так как его мож­ но изобразить иначе ( G ' на рис. 2.8, б). При таком изображении плоскость разбивается на области 5 ,, S2, S2, S4, которые могут быть раскрашены в разные цвета. Видно, что п =4, т = 6 , г = 4, и справедлива формула Эйлера п - т + г =4 - 6 + 4 =2. путем путь Эйлеровым графа называется , —- . который содер- ЦИКЛОМ цикл жит все ребра графа только один раз. Граф, обладающий эйлеро­ вым циклом, называется эйлеровым . Плоские эйлеровы графы можно изобразить «одним росчерком пера», причем процесс изоб­ ражения начинается и заканчивается в одной вершине. Такой граф называют также уникурсальным. Т еорем а 2 .6 . Граф G является эйлеровым тогда и только тогда, когда G — связный граф, имеющий все четные вершины. На рис. 2.9 изображен пример эйлерова графа. Граф G9 н а рис. 2.6, а не будет эйлеровым, так как не все его вершины явля­ ются четными. путем путь Гамильтоновым графа G называется > проходя- циклим цикл щий через каждую его вершину только один раз. Граф, содержа­ щий гамильтонов цикл, называется гамильтоновым. Рис. 2.9. Изображение эйлерова графа Рис. 2.10. Изображение гамильтоновых путей 77