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-я компонента связности C_i, графа G содержит n_i врешин, то по предыдущей теореме соответствующее дерево K_i остова содержит n_i-1 ребро. Следовательно для получения K_i из компоненты C_i нужно удалить m_i-(n_i-1) ребер. Суммируя удаляемые ребра по всем компонентам связности, получаем, что необходимо удалить m-n+c ребер.

Число υ(G)=m-n+c называется цикломатическим числом или цикломатическим рангом графа G. Число υ^*(G)=n-c называется коциклическим рангом или корангом.

Неоргарф G является лесом тогда и только тогда, когда υ(G)=0.

Неорграф G имеет единственный цикл тогда и только тогда, когда υ(G)=1.

Алгоритм построения остова минимального веса:

1. Строим граф T₁=<M, u₁>, где u₁ – ребро минимального веса.

2. Если граф T_i уже построен и i<n-c, где n=|M|, с=с(G), то строим граф T_i+1=T_i+u_i+1, где u_i+1 – ребро минимального веса среди ребер, не входящих в T_i и не составляющих циклов с T_i.

Обход графа по глубине и ширине:

Пусть G=<M,R> связный неорграф, T – некоторый остов графа, a – некоторая фиксированная вершина, корень дерева T. Разместим вершины из M по этажам таким образом, чтобы корень a находился в верхнем этаже, смежные с ним вершины занимали этаж на единицу ниже, смежные с отмеченными вершинами еще на единицу ниже и тд. Получаем e(a)+1 этаж, где e(a) – эксцентриситет вершины a.

При обходе графа по глубине после очередной рассмотренной вершины выбирается смежная с ней вершины следующего этажа. Если очередная рассмотренная вершина висячая и ее достижение не дает решения задачи, то возвращаемся до ближайшей вершины степени ≥3 и просматриваем вершины другого, еще не пройденного маршрута.

При обходе графа по ширине просмотр вершин дерева ведется по этажам, переход к вершинам следующего этажа происходит только после просмотра всех вершин данного этажа.