Эйлеровы и гамильтоновы графы

Эйлеровымназывается цикл в графе, содержащий все ребра графа.

Эйлеровым графомназывается связный граф, в котором есть эйлеровый цикл. Эйлеровый граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий ( рис. 14 ).

Рис. 14. Эйлеров граф

Теорема 6. Граф G является Эйлеровым тогда и только тогда, когда G – связный граф, имеющие все четные вершины.

Гамильтоновой цепьюназывается простая цепь, содержащая все вершины графа.

Гамильтоновым цикломназывается гамильтоновая цепь, начало и конец которой совпадают.

Графназываетсягамильтоновым,если в нем имеется гамильтонов цикл ( рис.15 ).

Рис. 15. Гамильтонов граф

Граф G называют p – хроматическим, где p – натуральное число, если его вершины можно раскрасить p – различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково.

Наименьшее число р, при котором граф является р - хроматическим, называют хроматическим числом графа и обозначают . Если = 2, то граф называется бихроматическим. Необходимым и достаточным условием в графе циклов нечетной длины.

Например, граф на рис. 16 бихроматический, его вершины “раскрашены” двумя “цветами”, обозначенными 0 и 1.

Рис. 16. Бихроматический граф.

Плоские и планарные графы

Граф G называется планарным ( плоским ), если существует изоморфный ему граф G’, в изображении которого на плоскости ребра пересекаются только в вершинах. Иными словами, у планарного графа никакие два ребра не имеют общих точек, кроме общих вершин. Например, граф на рис. 5 является планарным, а на рис. 7 – нет.

Теорема Эйлера.Связный плоский граф с n вершинами и m ребрами разбивает плоскость на k областей ( включая и внешнюю ), причем

n – m + k = 2.

Граф называется двудольным, если множество его вершин X может быть разделено на два непересекающихся подмножества таким образом, что каждое ребро графа соединяет вершины из двух различных подмножеств.