- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
8.5 Отыскание фундаментального множества циклов в графе
Если к стягивающему дереву <V, T> графа G = <V, E> мы добавим произвольную хорду e∈E\T, то возникший при этом подграф C = <V, T∪{e}> содержит в точности один цикл (под циклом мы здесь будем понимать элементарный цикл). Обозначим этот цикл через Ce. Множество C = {Ce : e∈E \ T} называют фундаментальным множеством циклов графа G (относительно стягивающего дерева <V, T>). Название "фундаментальное" связано с тем, что каждый цикл графа G можно достаточно просто получить из циклов множества G.
Нахождение фундаментального множества циклов имеет прикладное значение, например, при анализе электрических цепей. А именно, каждому фундаментальному циклу в графе, соответствующему данной электрической цепи, мы можем поставить в соответствие закон Кирхгофа для напряжений: сумма падения напря-
жений вдоль цикла равна 0. Нахождение фундаментального множества циклов позволяет выделить в математическом описании цепи независимые уравнения.
Опишем теперь простой алгоритм нахождения множества фундаментальных циклов. Алгоритм основан на поиске в глубину и имеет структуру, аналогичную рекурсивному алгоритму нахождения стягивающего дерева.
Каждая новая вершина, встречающаяся в процессе поиска, помещается в стек, представленный таблицей СТЕК, и удаляется из стека после использования. Очевидно, что стек всегда содержит последовательность вершин от рассматриваемой в данный момент вершины v к корню.
Поэтому, если анализируемое нами ребро {v, и} замыкает цикл (т.е. WGN[v] > WGN[u] > 0 b и не находится непосредственно под верхним элементом стека), то вершина и находится в стеке и цикл, замыкаемый ребром {v, и}, представлен группой элементов стека, начиная с v и кончая вершиной и.
1 PROCEDURE цикл(у);
{переменные d, пит, СТЕК, СПИСОК, WGN - глобальные}
2 BEGIN d := d+1; СТЕК[d] := v; пит := num+1; WGN[ ] := пит;
3 FOR иеСПИСОК[у] DO
IF WGN[u] = 0 THEN цикл(г)
ELSE IF (и Ф СТЕК[d-l]) and (WGN[v] > WGN[u])
THEN {ребро {v, и} замыкает новый цикл}
выписать цикл с вершинами
СТЕК[d], СТЕК[d-l], ..., СТЕК[с], где СТЕК[с] = и
8 d := d-1 {использованная вершина v удаляется из стека}
9 END (цикл}; Основная программа:
1 BEGIN
FOR veV DO WGN[r] := 0; num := 0; {инициализация}
d := 0; СТЕК[0] := 0; {d - число элементов в стеке}
FOR reV DO
5 IF WGN[r] = 0 THEN цикл(у)
6 END.
Оценим вычислительную сложность алгоритма. Отметим, что общее число шагов, не считая вычисления циклов, как и во всех алгоритмах, основанных на поиске в глубину, имеет порядок 0(n+m). К этому следует добавить суммарную длину всех циклов. Эта длина не превосходит (m-n+1), что дает общую сложность алгоритма 0(шп+п) (или O(nm), если отбросить вырожденный случай т=0).
8.6 Эйлеровы пути в графе
Эйлеров путь в графе - произвольный путь, проходящий через каждое ребро графа ровно один раз, т.е. такой путь Vj,..., Vm+\, что каждое ребро ееЕ появляется один раз как \Vj,V-+j} для некоторого i. Если
Vj = Vm+\, то такой путь называется эйлеровым циклом.
Необходимое и достаточное условие существования эйлерова пути: эйлеров путь в графе существует тогда и только тогда, когда граф связан и содержит не более чем две вершины нечетной степени.
Если в графе нет вершин нечетной степени, то каждый эйлеров путь является эйлеровым циклом.
Пусть G = <V, Е> - связный граф, представленный списками СПИСОК[г], ve V. Алгоритм нахождения эйлерова цикла в графе построим следующим образом. Используем два стека: СТЕК1 и СТЕК2.
Выбираем произвольную вершину графа Vq и строим последовательно путь из этой вершины. Вершины
этого пути помещаем в СТЕК1, а ребра удаляем из графа. Эти действия продолжаем до тех пор, пока оказывается, что путь удлинить, включив в него новую вершину, уже нельзя. Т.е. СПИСОК[у] = 0. Отметим, что тогда должно быть V = Vq , иначе это бы означало, что вершина v - нечетной степени. Таким образом из нашего графа был удален цикл, а вершины этого цикла находятся в стеке СТЕК1. При этом в графе, модифицированном таким образом, степень произвольной вершины остается четной. Вершина V = v0 переносится теперь из стека
СТЕК1 в стек СТЕК2, а процесс повторяется, начиная с вершины, верхней в СТЕК1 (если ее список не пустой). Теперь снова в СТЕК1 помещается некоторый цикл, проходящий через эту вершину, и т.д. Процесс продолжается до тех пор, пока СТЕК1 не станет пустым.
Очевидно, что вершины, помещенные в СТЕК2, образуют некоторый путь, причем вершина v переносится в СТЕК2 только тогда, когда СПИСОК[у] = 0, т.е. когда все ребра, инцидентные этой вершине, представлены в СТЕКеl (парами соседних вершин). Отсюда следует, что по окончании алгоритма СТЕК2 содержит эйлеров цикл.
Алгоритм:
BEGIN
СТЕК1 := 0; СТЕК2 := 0;
v := произвольная вершина графа;
СТЕК1 <= v;
WHILE СТЕК1 /0DO BEGIN
v := top(СТЕКl); {v - верхний элемент СТЕК1}
IF СПИСОКу] Ф 0
THEN BEGIN
u := первую вершину списка СПИСОК[у];
СТЕК1 <= u;
СПИСОК^] := СПИСОК^] \ { u }; {удалить ребро}
СПИСОКи] := СПИСОКи] \ { v }; {{ v, и } из графа}
v :=и;
END
ELSE { СПИСОКу] = 0}
BEGIN
v <= СТЕКl;
СТЕК2 <= v;
19 END
END
END
Мы предполагаем здесь, что каждый из списков инцидентности СПИСОКу], veV, реализован таким образом, что каждая вершина в этом списке содержит указатели на предыдущую и последующую вершины, а вершина и в списке СПИСОКу] содержит указатель на вершину v в списке СПИСОКи]. Это дает возможность удалить ребро {v, и} за число шагов, ограниченное константой. Тогда можно оценить вычислительную сложность алгоритма следующим образом.
Каждая итерация главного цикла (строка 5) либо помещает вершину в СТЕК1 и удаляет ребро из графа, либо переносит вершину из СТЕК1 в СТЕК2. Т.е. число итераций этого цикла О(т). Число же шагов в каждой итерации ограничено константой. Поэтому можно считать, что общая сложность алгоритма О(т). Алгоритм считается оптимальным. Пример.
1
4
7
Эйлеров цикл, найденный с помощью нашего алгоритма: 1, 2, 3, 4, 5, 6, 7, 2, 8, 6, 9, 7, 8, 5, 3, 1
9