16. Цепи и циклы (Полу)эйлеровы графы Необходимые и достаточные условия (полу)эйлеровости графа
К списку вопросов
Маршрут графа - конечная последовательность ребер вида
(V0, V1), (V1, V2), ..., (Vn-1, Vn). V0=> V1 =>V2=> …=> V m-1=> Vm,
где V0 – начальная вершина маршрута, Vm –конечная.
Длиной маршрута называется число ребер в нем.
Маршрут называется цепью, если все его ребра различны; простой цепью - если все его вершины различны.
Цепь называется замкнутой (простой замкнутой), если V0 = Vn. Замкнутая простая цепь, хоть одно ребро - цикл.
Граф называется связным, если для любых двух его вершин существует простая цепь из одной вершины в другую; несвязным в противном случае.
Любой граф можно разбить на не пересекающиеся связные подграфы, называемые компонентами связности. Граф несвязный, если число компонентов >1.
m- число ребер графа G(простой).
n- число вершин
n-1 (число ребер графа без цикла)? m ? n*(n-1)/2 (число ребер полного графа)
Наименьшее множество ребер, после удаления которых связный граф перестает быть таковым, называется разрезом.
Если этот разрез состоит из одного ребра, то он называется мостом.
После удаления разреза граф распадается на 2 компонента в мост.
Разрез: (l3, l6, l7, l8).
Эйлеровы графы. в 1736 Леонард Эйлер опубликовал задачу “Задача о Кенигсбергских мостах”.
Задача о Кенигсбергских мостах.
Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города соединены 7 мостами.
По воскресеньям граждане совершают прогулки по городу. Вопрос заключается в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту.
Замкнутая цепь, содержащая все ребра графа, называется Эйлеровой линией; а граф, обладающий такой линией, называют Эйлеровым графом.
Если снять ограничение на замкнутость цепи, то граф называется полу-Эйлеровым.
Теорема о необходимом и достаточном условии Эйлеровости графа:
- Связный граф является Эйлеровым тогда и только тогда, когда степень каждой его вершины четная.
- Полу-Эйлеровый граф должен иметь не более двух вершин с нечетными степенями.
К списку вопросов
