Структуры и алгоритмы компьютерной обработки данных (стр. 11 )

Для применения этого критерия к поиску шарниров введем на множестве вершин функцию , связанную с DFS-деревом: значением является наименьший из глубинных номеров вершин, смежных с потомками вершины . Если вершина является сыном вершины , то (так как вершина является потомком самой себя и смежна с вершиной ). Из теоремы 2 следует, что вершина , отличная от , является шарниром тогда и только тогда, когда у нее имеется сын такой, что .

Функцию можно определить рекурсивно - если мы знаем ее значения для всех сыновей вершины и глубинные номера всех вершин, смежных с и не являющихся ее сыновьями, то есть минимум из всех этих величин, то есть

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

Procedure

for do if then ComputeLow() else

Лекция 3. Эйлеровы и гамильтоновы циклы.

Маршруты, пути, циклы

Маршрут в графе - это последовательность вершин , такая, что для каждого вершины и соединены ребром. Эти ребер называются ребрами маршрута. Говорят, что маршрут проходит через них, а число называют длиной маршрута. Говорят, что маршрут соединяет вершины и , они называются соответственно началом и концом маршрута, вершины называются промежуточными. Маршрут называется замкнутым, если .

Путь - это маршрут, в котором все ребра различны. Путь называется простым, если и все вершины в нем различны.

Цикл - это замкнутый путь. Цикл называется простым, если все вершины попарно различны.

В графе на рисунке 3.1 последовательность вершин

- не маршрут; - маршрут, но не путь; - путь, но не простой; - замкнутый маршрут, но не цикл; - цикл, но не простой; - простой цикл.

Рис. 3.1.

Установим некоторые простые свойства маршрутов.

Теорема 1. В любом маршруте, соединяющем две различные вершины, содержится простой путь, соединяющий те же вершины. В любом цикле, проходящем через некоторое ребро, содержится простой цикл, проходящий через это ребро.

Доказательство.

Пусть - маршрут. Если все его вершины различны, то это уже простой путь. В противном случае, пусть , . Тогда последовательность , полученная из этого маршрута удалением отрезка последовательности от до , тоже является маршрутом. Новый маршрут соединяет те же вершины и имеет меньшую длину. Продолжая действовать таким образом, после конечного числа "спрямлений" получим простой путь, соединяющий и . Второе утверждение теоремы доказывается аналогично.

Отметим, что в формулировке теоремы 1 нельзя заменить слово "цикл" словами "замкнутый маршрут". Действительно, если - ребро графа, то последовательность - замкнутый маршрут, проходящий через это ребро, но никакого цикла в нем нет.

Теорема 2. Если в графе степень каждой вершины не меньше , то в нем есть цикл.

Доказательство.

Найдем в графе простой путь наибольшей длины. Пусть это . Вершина смежна с , а так как ее степень не меньше двух, то она смежна еще хотя бы с одной вершиной, скажем, с . Если бы была отлична от всех вершин пути, то последовательность была бы простым путем большей длины. Следовательно, - это одна из вершин пути, , причем . Но тогда - цикл.

Связность и компоненты

Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины. Заметим, что ввиду теоремы 1 можно в этом определении заменить слово "маршрут" словами "простой путь".

Для произвольного графа определим на множестве вершин отношение соединимости: вершина соединима с вершиной , если существует соединяющий их маршрут. Легко видеть, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются областями связности, а порождаемые ими подграфы - компонентами связности графа. В связном графе имеется только одна компонента связности - весь граф. Компоненты связности можно определить также как максимальные по включению связные подграфы данного графа.