Связность графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
графе G разделяющим множеством называется такое множество ребер, удаление которого увеличивает число компонент вG. Разрезом в G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. Заметим, что в результате удаления ребер, принадлежащих разрезу, число компонент в G увеличивается ровно на единицу.
5. Эйлеровы графы
Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось 1 только один раз.
2 3
Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый эйлеров граф будет полуэйлеровым. На Рис. 1, 2 и 3 изображены соответственно не эйлеров, полуэйлеров и эйлеров графы. Заметим, что предположение о связности графа G введено только ради удобства, так как оно позволяет не рассматривать тривиальный случай графа, содержащего несколько изолированных вершин.
Название эйлеров возникло в связи с тем, что Эйлер первым решил знаменитую задачу о кёнигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на Рис. 4, эйлерову цепь (не имеет!).Сразу же возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым?
Лемма 6А. Если степень каждой вершины графа G не меньше двух, то G содержит цикл.
Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v - произвольная вершина графа G; построим по индукции маршрут v> v1> v2>…, выбирая вершину v1 смежной вершине v, а для i ? 1 - выбирая vi+1 смежной vi и отличной от vi-1(существование такой вершины vi+1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов придем к вершине, которая уже была выбрана раньше. Предположим, что ад - первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями vk, и является требуемым циклом.
Рис 4
Теорема 6В. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четную степень.
Доказательство. => Предположим, что Р является эйлеровой цепью в графе G. Тогда при всяком прохождении цепи Р через любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в Р ровно один раз, то каждая вершина должна иметь четную степень.
<= Проведем доказательство индукцией по числу ребер в G. В силу связности G, степень каждой вершины не меньше двух, а отсюда, по предыдущей лемме, заключаем, что граф G содержит цикл C. Если С проходит через каждое ребро графа G, то доказательство завершено; если нет, то, удаляя из G ребра, принадлежащие циклу С, получим новый (быть может, и несвязный) граф H. Число ребер в Н меньше, чем в G, и любая вершина в H по-прежнему имеет четную степень. Согласно индуктивному предположению, в каждой компоненте графа Н существует эйлерова цепь. В силу связности графа G, каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идем по ребрам цикла С до тех пор, пока не встретим неизолированную вершину графа H, затем следуем по эйлеровой цепи той компоненты в H, которая содержит указанную вершину; далее продолжаем путь по ребрам цикла С, пока не встретим вершину, принадлежащую другой компоненте графа H, и т. д.; заканчивается процесс тогда, когда попадаем обратно в начальную вершину (см. Рис. 5).
Рис 5
Следствие 6С. Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы. //
Следствие 6В. Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени. //
Заметим, что если полуэйлеров граф содержит ровно две вершины с нечетными степенями, то в любой полуэйлеровой цепи (смысл этого понятия очевиден) одна из этих вершин обязательно будет начальной, а другая - конечной. По лемме о рукопожатиях граф не может иметь только одну вершину нечетной степени.
Завершая рассмотрение эйлеровых графов, дадим алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри.
Теорема 6Е. Пусть G - эйлеров граф; тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила: (i) стираем ребра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются; (ii) на каждом этапе идем по мосту только тогда, когда нет других возможностей.
Доказательство. Предположим, что достигли некоторой вершины v; тогда если v ? u, то оставшийся подграф Н связен и содержит ровно две вершины нечетной степени, а именно u и v. Согласно следствию 6D, граф H содержит полуэйлерову цепь Р из v и u. Поскольку удаление первого ребра цепи Р не нарушает связности графа H, отсюда следует, что описанное в теореме построение возможно на каждом этапе. Если же v = u, то доказательство остается тем же самым до тех пор, пока есть еще ребра, инцидентные вершине u.
Осталось только показать, что данная процедура всегда приводит к полной эйлеровой цепи. Но это очевидно, так как в G не может быть ребер, оставшихся непройденными после использования последнего ребра, ин?/p>