Лемма о рукопожатиях: Сумма степеней всех вершин графа является четным числом и равна удвоенному числу ребер.
Критерий «эйлировости» графа: Связный неориентированный мультиграф тогда и только тогда является эйлеровым, когда степень каждой из его вершин – четное число.
Алгоритм построения эйлерова цикла:
1) Выбрать произвольно некоторую вершину a.
2) Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным).
3) Каждое пройденное ребро вычеркнуть и присвоить ему номер, на единицу больший предыдущего вычеркнутого ребра.
4) Находясь в вершине x, не выбирать ребро, соединяющее x с a, если есть возможность иного выбора.
5) Находясь в вершине x, не выбирать ребро, которое является перешейком (т.е. ребром, при вычеркивании которого граф распадается на две компоненты связности).
6) После того как в графе будут занумерованы все ребра, образуется эйлеров цикл.
Теорема: Если связный граф содержит k вершин нечетной степени, то минимальное число покрывающих его реберно непересекающихся цепей равно k /2.
Доказательство: Набор реберно непересекающихся цепей покрывает граф G, если каждое его ребро входит в одну из этих цепей.
Пусть связный граф G содержит k вершин нечетной степени. По лемме о рукопожатиях число k четно. Рассмотрим граф G ’, полученной добавлением к G новой вершины a и ребер, соединяющих a со всеми вершинами нечетной степени графа G. Граф G ’ будет содержать эйлеров цикл. Если удалить из этого цикла все ребра, инцидентные вершине a, то получится не более k /2 цепей, покрывающих G. С другой стороны, граф, являющийся объединением r реберно непересекающихся цепей имеет не более 2 r верши нечетной степени. Поэтому граф G нельзя покрыть цепями, число которых меньше k /2.
33. Гамильтоновы графы. Постановка задачи коммивояжера.
Граф называется гамильтоновым, если в нем имеется простой цикл (гамильтонов цикл), содержащий каждую вершину этого графа. Простая цепь, содержащая все вершины графа, также называется гамильтоновой.
Пусть G – связный неорграф без петель, имеющий n ≥3 вершин.
Достаточные условия существования гамильтоновых циклов:
1) Если для любых двух различных несмежных вершин a и b графа G выполняется условие dega + degb ≥ n, то существует гамильтонов цикл.
2) Если для любой вершины a графа G выполнено условие dega ≥ n /2, то существует гамильтонов цикл.
Задача коммивояжера:
Район, который должен посетить бродячий торговец, содержит некоторое количество городов, расстояния между которыми известны. Требуется найти кратчайший маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный город.
34. Деревья, леса. Остовы графов. Цикломатическое число, коранг. Алгоритм построения остова минимального веса. Обходы графов по глубине и ширине.
Деревом называется связный неорграф, не содержащий циклов. Любой неорграф без циклов называется ациклическим графом или лесом.
Теорема: Для неорграфа G без петель содержащего n вершин следующие условия эквивалентны:
1) G – дерево
2) G – связный граф, содержащий n-1 ребро
3) G – ациклический граф, содержащий n-1 ребро
4) любые две несовпадающие вершины графа G соединяет единственная простая цепь
5) G – ациклический граф, такой, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл
Пусть G=<M,R> - неорграф. Часть G’=<M’,R’> графа G называется остовом или каркасом графа G, если M=M’ и G’ – лес, который на любой связной компоненте графа G образует дерево.
Теорема: Число ребер произвольного неорграфа G, которое необходимо удалить для получения остова не зависит от последовательности их удаления и равно m-n+c, где m – число ребер, n – число вершин, c – число компонент связности.
Доказательство: Действительно, если i-я компонента связности Ci, графа G содержит ni врешин, то по предыдущей теореме соответствующее дерево Ki остова содержит ni-1 ребро. Следовательно для получения Ki из компоненты Ci нужно удалить mi-(ni-1) ребер. Суммируя удаляемые ребра по всем компонентам связности, получаем, что необходимо удалить m-n+c ребер.
Число υ(G)=m-n+c называется цикломатическим числом или цикломатическим рангом графа G. Число υ*(G)=n-c называется коциклическим рангом или корангом.
Неоргарф G является лесом тогда и только тогда, когда υ(G)=0.
Неорграф G имеет единственный цикл тогда и только тогда, когда υ(G)=1.
Алгоритм построения остова минимального веса:
1) Строим граф T1=<M, u1>, где u1 – ребро минимального веса.
2) Если граф Ti уже построен и i<n-c, где n=|M|, с=с(G), то строим граф Ti+1=Ti+ui+1, где ui+1 – ребро минимального веса среди ребер, не входящих в Ti и не составляющих циклов с Ti.
Обход графа по глубине и ширине:
Пусть G =< M , R > связный неорграф, T – некоторый остов графа, a – некоторая фиксированная вершина, корень дерева T. Разместим вершины из M по этажам таким образом, чтобы корень a находился в верхнем этаже, смежные с ним вершины занимали этаж на единицу ниже, смежные с отмеченными вершинами еще на единицу ниже и тд. Получаем e ( a )+1 этаж, где e ( a) – эксцентриситет вершины a.
При обходе графа по глубине после очередной рассмотренной вершины выбирается смежная с ней вершины следующего этажа. Если очередная рассмотренная вершина висячая и ее достижение не дает решения задачи, то возвращаемся до ближайшей вершины степени ≥3 и просматриваем вершины другого, еще не пройденного маршрута.
При обходе графа по ширине просмотр вершин дерева ведется по этажам, переход к вершинам следующего этажа происходит только после просмотра всех вершин данного этажа.
35. Упорядоченные и бинарные деревья. Соответствия между ними.
Определим по индукции понятие упорядоченного дерева:
1) пустое множество и список ( a ), где a – некоторый элемент, является упорядоченным деревом;
2) если T 1 , T 2 ,…, Tn – непустые упорядоченные деревья, a – некоторый новый элемент, то список T =( a , T 1 ,…, Tn ) образует упорядоченное дерево. При этом элемент a называется корнем упорядоченного дерева T;
3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2.