Графы — определения, деревья, хранение и поиск в глубину
Графом \(G\) называется пара множеств \(G = (V, E\) , где \(V(G)\) — непустое конечное множество элементов, называемых вершинами графа, а \(E\) — множество пар элементов из \(V\) (необязательно различных), называемых ребрами графа. \(E = \<(u , v)\ | u, v \in V\>\) — множество ребер графа \(G\) , состоящее из пар вершин \((u, v)\) . Ребро \((u, v)\) соединяет вершины \(u\) и \(v\) .
Граф — это набор вершин (точек) и соединяющих их отрезков (рёбер).
Примеры графа
Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах \(N\) — количество вершин, а \(M\) — ребер. Количество ребер, исходящее из вершины называют степенью вершины \(d(v)\) . Для вершины \(a\) ребро \((a, b)\) называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).
Теоретическое задание
Назовите степень 1-ой и 6-ой вершины и какие ребра инциденты им.
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
Теоретическое задание
Сколько может быть рёбер в простом графе в \(N\) вершинами?
Теоретическое задание
Найдите цикл размера 4 и петлю в этом непростом графе.
Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.
Хранение графа в программе
Чаще всего в задачах по программмированию вершины графа — это числа от \(0\) до \(N-1\) , чтобы удобно было обращаться к ним как к индексам в разных массивах.
Также чаще всего вам дают считать граф как просто список всех рёбер в нем (но не всегда, конечно). Как оптимально считать и сохранить граф? Есть 3 способа.
Для графа существуют несколько основных способов хранения:
- Матрица смежности. Давайте хранить двумерную матрицу \(A_
\) , где для данного графа G верно, что если \(A_ \) = 1, то две вершины \(i\) и \(j\) являются смежными, иначе вершины \(i\) и \(j\) смежными не являются.
Мы храним для каждой из \(N\) вершин информацию, есть ли ребро в другие вершины, то есть суммарно мы храним \(N^2\) ячеек, а следовательно асимптотика по памяти — \(O(N^2)\) .
- Список смежности. Давайте для каждой из \(N\) вершин хранить все смежные с ней, для этого нам потребуется любая динамическая структура, например vector в с++.
Здесь асимптотика по памяти и времени считывания — \(O(N + M)\) , так как мы храним для каждой вершины, куда есть ребра, то есть \(2 M\) ребер, а также суммарно \(N\) векторов.
Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка.
- Список рёбер. Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход.
Заметьте, что все эти способы обощаются на случай ориентированных графов — при этом матрица смежности становится неориетированной: если есть ребро из вершины \(i\) в вершину \(j\) , то сделаем \(A_
Практическое задание
Для окончательного закрепления темы советую решить первые 2 задачи.
Деревья
Дерево — это связный неориентированный граф без циклов.
Пример дерева
- У дерева с хотя бы 2 вершинами всегда есть висячая вершина — вершина степени 1.
Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины — ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) — ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.
- У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.
Действительно, если предыдущий алгоритм начать из висячей вершины, то мы уткнемся в другую висячую вершину.
- У дерева с \(N\) вершинами всегда ровно \(N-1\) ребро.
Давайте отрезать от дерева его висячие вершины — при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока \(N > 1\) . В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.
- Между любыми двумя вершинами в дереве есть ровно один простой путь.
Действительно, если их два, то в графе есть цикл. Быть ноль их не может — ведь граф связный.
- Дерево — это минимальный по числу рёбер связный граф на \(N\) вершинах.
Действительно, если есть связный граф, в котором меньше, чем \(N-1\) ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве \(N-1\) ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.
DFS (Алгоритм обхода графа в глубину)
Обход в глубину — простой, но многофункциональный алгоритм обхода графа по ребрам. Самое главное, что он может — это проверить, какие вершины достижимы из данной.
При обходе графа мы используем вспомогательный массив used, в котором храним 1, если вершина была посещена или 0 иначе. В начале мы считаем, что все вершины не использовались, затем мы выбираем одну вершину, помечаем ее посещенной и запускаемся рекурсивно из всех ее соседей, тогда мы посетим все вершины, которые достижимы из данной, если же остались вершины с used = 0 значит они недостижимы.
Красивая визуализация: https://visualgo.net/en/dfsbfs
Давайте оценим сложность алгоритма. Так как мы проверяем, что вершина еще не использовалась, то всего мы пройдет каждую вершину 1 раз, но при этом и ребро между двумя вершинами, мы рассматриваем только когда рассматривается один конец, то есть мы просмотрим каждое ребро не более одного раза, суммарно получаем оценку \(O(N + M)\) .
Практическое задание
Задачи 3-5 в контесте.
Поиск компонент связности графа
Путем в графе называется последовательность вершин \(v_i \in ��\) , \(i = 1. k\) таких, что две последовательные вершины в пути соединены ребром, \(k\) — длина пути. Граф называется связным, если для любых двух его вершин существует путь между ними. Граф всегда можно разбить на непересекающиеся связные подмножества (возможно одно), между которыми рёбер нет, они называются компонентами связности.
Поиск в глубину dfs будет обходить ту компоненту связности, из вершины которой, он был вызван. Поэтому для поиска компонент связности можно каждый раз вызываться из любой непосещенной вершины и тогда в результате мы посетим все вершины, а следовательно и найдем все компоненты связности.
Практическое задание
На данную тему задачи 6 и 10 в контесте.
Остовное дерево
Остованым деревом в связном графе называется любое подмножество ребер, которое является деревом на всех вершинах. То есть любой способ выкинуть несколько ребер так, чтобы осталось дерево на N вершинах и N-1 ребро выделяет в графе остовное дерево.
Обход графа удобно использовать для выделения этого остовного дерева — если выделить каждое ребро, по которому мы прошли в обходе, то получится остовное дерево. Действительно, мы обойдем все вершины, и при этом никогда не пойдем в вершину, в которой уже были, поэтому циклов там не будет. Так что достаточно после прохода по любому ребру добавлять его в ответ.
Практическое задание
7 задача в контесте на выделение остовного дерева в графе.
Раскраска графа в два цвета
Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.
С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины — достаточно выделить каждую.
Практическое задание
8 задача в контесте на раскраску графа в два цвета
Поиск циклов в графе
Циклом в графе \(G\) называется ненулевой путь, ведущий из вершины \(v\) в саму себя. Граф называют ацикличным, если в нем нет циклов.
В обычном dfs мы используем два цвета (1 — вершина посещена, 0 — не посещена), если же нам надо найти цикл, то давайте хранить 3 цвета:
- 0 — вершина не просмотрена
- 1 — мы входили DFS-ом в эту вершину, но еще не вышли (а значит из нее есть путь до текущей),
- 2 — мы входили DFS-ом в эту вершину
Заметим, что цикл будет тогда и только тогда, когда мы пытаемся войти в вершину с цветом 1.
В неориентированном графе также надо дополнительно рассмотреть случай, когда мы идем в предка — это циклом все-таки не считается, для этого нужно отдельно добавить второй аргумент prev, где хранить предыдущую вершину в dfs, и никогда не идти в неё.
Анализ алгоритма
Неориентированный граф, состоящий из n вершин, будет деревом, если он связный и содержит n – 1 ребро. Запускаем поиск в глубину из первой вершины. Если существует обратное ребро, то граф имеет цикл и не является деревом. Одновременно в переменной с подсчитываем количество посещенных вершин в процессе поиска. Если по окончанию поиска в глубину оно не равно n, то граф не является связным.
Граф, приведенный в примере, является деревом.
Матрицу смежности графа храним в массиве m.
int m[MAX][MAX], used[MAX];
Функция dfs реализует поиск в глубину из вершины v. При этом в вершину v мы попали из вершины prev (prev = -1 если v – корень дерева поиска в глубину). В переменной с подсчитываем количество пройденных вершин в процессе поиска.
void dfs( int v, int prev)
Ребро (v, i) будет обратным и образовывать цикл, если i ≠ prev и при этом вершина i уже была пройдена раньше (used[ i] = 1).
for (i = 0; i < n; i++)
if (used[i]) flag = 1; else dfs(i,v);
Основная часть программы. Читаем входные данные.
memset(used,0, sizeof (used));
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
Запускаем поиск в глубину из нулевой вершины. Поскольку она является корнем дерева поиска, то не имеет родителя. В качестве второго аргумента передаем функции dfs значение -1.
Граф не будет деревом, если существует обратное ребро (flag = 1) или граф не является связным (количество посещенных вершин c при поиске в глубину не равно n).
if (flag || (c != n)) printf( "NO\n" ); else printf( "YES\n" );
Если граф является деревом, то:
3. Граф не содержит циклов
Выполнение первых двух условий достаточно для того, чтобы граф являлся деревом.
int i, j, n, c, Edges;
int g[ MAX ][ MAX ], used[ MAX ];
for ( int i = 1; i <= n; i++)
memset(used, 0, sizeof (used));
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
Java реализация
import java.util.*;
public class Main
static int c = 0;
static int m [][], used [];
static void dfs( int v )
used [ v ] = 1; c ++;
for ( int i = 0; i < m . length ; i ++)
if ( m [ v ][ i ]== 1 && used [ i ] == 0) dfs( i );
public static void main(String[] args ) //throws IOException
Является ли граф деревом [закрыт]
Хотите улучшить этот вопрос? Переформулируйте вопрос так, чтобы на него можно было дать ответ, основанный на фактах и цитатах.
Закрыт 7 лет назад .
Задачка: Предложите алгоритм, который определяет, является ли граф деревом.
Мое решение, которое, как оказалась, неверное
Думаю, некоторым будет интересно решить 🙂
Дерево — связный граф с n-1 ребром.
Моё решение на Pascal. Граф задаётся матрицей смежности (1 — есть ребро, 0 — иначе). maxV — максимальное число вершин maxE — максимальное число рёбер Храню граф списком рёбер.
Есть несколько способов решения. Можно использовать свойство ацикличности с подсчетом количества вершин, те обходим граф в ширину/глубину, подсчитывая число обойденных вершин, если мы обошли граф и не встретили ни одну вершину два раза, а также общее количество вершин и число обойденных вершин равны, то это дерево .
Выполняем обычный проход по графу и каждую пройденный узел заносим в список, при этом проверяем не содержится ли он в нем уже. Если содержится то всё не дерево 🙂
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43304
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Name already in use
progtexts2 / dfs / 04_2_simple.rst
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Простые задачи, решаемые поиском в глубину
В этом разделе почти везде будем рассматривать только неориентированные графы.
Компоненты связности графа
Довольно очевидно доказывается, что поиск в глубину, запущенный из некоторой вершины графа, обойдёт все вершины из той компоненты связности, в которой находится наша вершина.
Докажем это. Действительно, пусть есть вершина, лежащая в той же компоненте [1] связности, но до которой мы не дошли. Раз она лежит в той же компоненте связности, то есть путь из начальной вершины в неё. В начальной вершине пути мы точно побывали (мы ведь оттуда запустились), в конечной вершине нет (по предположению). Тогда очевидно, что вдоль пути найдутся две соседние вершины u и v такие, что в u мы побывали, а в v нет. Раз они соседние в нашем пути, то они соединены ребром. Тогда спрашивается: что мы делали, когда просматривали соседей вершины u? Почему не пошли в v? Противоречие, следовательно, мы действительно обойдём всю соответствующую компоненту связности.
Как видите, доказательство от противного. Мне кажется, что это довольно хорошо подчёркивает саму суть поиска в глубину: сразу далеко не очевидно, что оно работает. Попытки в лоб доказать, что оно работает, не пройдут. Но тем не менее оно действительно работает.
Естественно, мы считаем, что перед запуском массив was по крайней мере в пределах этой компоненты связности был заполнен нулями, иначе, конечно, ничего не получится.
Таким образом, чтобы проверить, что граф (неориентированный!) связен, поступаем очень просто: запускаем поиск в глубину из любой вершины и после этого проверяем, что мы побывали во всех вершинах:
Пусть теперь нам надо найти все компоненты нашего (возможно, не связанного) графа. Т.е. нам надо посчитать их, а в специальный массив для каждой вершины записать номер соответствующей компоненты. Я думаю, это тоже вполне понятно. Запускаемся из первой вершины, потом ищем ещё непосещённую вершину и запускаемся из неё и т.д. Правда, некоторую сложность может составить реализация этого дела, но, если немного подумать, то можно написать так:
Здесь nc — глобальная переменная, хранящая количество уже найденных компонент связности. Номер компоненты связности, как я и обещал выше, мы записываем прямо в массив was: компоненты мы нумеруем, начиная с 1, поэтому проблем не возникает. was[i]=0 обозначает, что вершина i ещё не была посещена, иначе вершина была посещена, а was[i] — номер её компоненты связности. Поэтому в процедуре мы делаем именно was[i]:=nc, а не 1, как раньше.
Ещё обратите внимание, что тут обязательно нужна проверка if was[i]=0 в главной программе, даже несмотря на то, что соответствующая проверка написана в начале процедуры. Действительно, проверка в главной программе нужна, чтобы не увеличить число компонент лишний раз.
И наконец заметьте, что, конечно, массив was мы инициализируем один раз за программу.
Проверка графа на двудольность
N-дольным называется неориентированный граф, вершины которого можно раскрасить в N цветов так, что концы любого ребра будут разноцветными, т.е. не будет рёбер, ведущих из одного цвета в тот же самый цвет. В таком случае группы вершин одного цвета называются долями графа. В частности, двудольный граф — граф, вершины которого можно разбить на две группы-доли так, что каждое ребро будет вести из одной доли в другую.
Нередко двудольные графы являются двудольными по своей природе, т.е. нередко сама природа вершин разных долей разная: классический пример — первая доля — люди (работники), вторая — работы, которые они могут выполнять, ребро между человеком и работой есть, если он умеет её выполнять. Очевидно, что тут ребра в пределах одной доли совершенно бессмысленно. В таких случаях обычно сразу во входном файле задаётся граф так, что он не может оказаться недвудольным, и вообще вопрос о проверке графа на двудольность бессмысленен. Но бывает так, что дан просто граф, а надо проверить, является ли он двудольным. Именно такую задачу мы и будем рассматривать здесь. Одновременно с проверкой на двудольность мы сразу будем находить его доли.
Итак, нам дан граф. Давайте попробуем его покрасить. Возьмём первую вершину и покрасим её в какой попало цвет (т.е. отнесём её к какой попало доле). Тогда сразу понятно, как надо красить соседние с ней вершины. Покрасим их как надо. После этого понятно, как надо красить соседние с ними вершины и т.д. (Довольно сильно напоминает поиск в ширину.) Так будет продолжаться до тех пор, пока не случится одно из двух:
а) Возникнет противоречие, т.е. мы должны будем покрасить одну и ту же вершину в разные цвета одновременно или должны будем перекрашивать уже покрашенную вершину. Что это обозначает? Единственный произвол, который мы делали, состоял в выборе цвета самой первой вершины. Очевидно, что, если мы попробуем другой вариант цвета первой вершины, то противоречие сохранится, просто цвета всех покрашенных вершин инвертируются. Тогда очевидно, что граф не двудольный.
б) Нам будет нечего делать, т.е. мы покрасили несколько вершин, противоречий нет, но ни у одной из уже покрашенных вершин нет непокрашенных соседей. Что это значит? Одно из двух: либо мы покрасили весь граф — круто, задача решена, ответ положительный.
Либо есть ещё непокрашенные вершины. Но ясно, что тогда они находятся в другой компоненте связности и потому их можно красить независимо от уже покрашенных. Возьмём любую из ещё непокрашенных вершин и покрасим её как попало и т.д., продолжая как описано выше. Опять либо возникнет противоречие, тогда граф точно не двудольный, т.к. на это противоречие влиял только самый последний произвол, а его инвертировать опять бессмысленно (а предыдущие выборы, которые мы делали, не имеют теперь значения), либо опять будет нечего красить — аналогично либо все покрасили, либо переходим к третьей компоненте и т.д.
Таким образом в конце концов мы или покрасим весь граф, или придём к выводу, что граф не двудольный. Прежде чем обсуждать реализацию, обсудим ещё небольшой теоретический вопрос.
Можно ли придумать какой-нибудь критерий двудольности графа? Давайте подумаем, когда «затыкается» наш алгоритм. Когда обнаруживает противоречие, т.е. одну и ту же вершину пытается сразу покрасить и в белый, и в чёрный цвет. Говоря по другому, когда у одной ещё непокрашенной вершины находятся два разноцветных соседа. Что это обозначает? До сих пор все было нормально, т.е. на каждом ребре цвет чередовался, поэтому цвета обозначают фактически «слои» графа: до вершин одного цвета от начальной мы добираемся за чётное число шагов (рёбер), до вершин второго цвета — за нечётное. Если же появилось противоречие, значит, нашлась вершина, до которой мы можем добраться и за чётное, и за нечётное количество шагов. Это обозначает, что появился цикл нечётной длины: от начальной вершины до неё самой можно добраться за нечётное количество шагов. Очевидно, что в двудольном графе не может быть циклов нечётной длины: в любом цикле вершины разных долей чередуются, и потому, чтобы вернутся в начальную вершину, надо сделать чётное количество шагов. Поэтому ясно, что, раз наш алгоритм нашёл-таки такой цикл, то граф точно недвудольный. А теперь заметим самое главное: если циклов нечётной длины в графе точно нет, то наш алгоритм в принципе не сможет «заткнуться», т.е. он корректно раскрасит граф, т.е. граф двудольный. Таким образом, мы доказали это утверждение в обе стороны: граф двудольный тогда и только тогда, когда в нем нет циклов нечётной длины.
Все то же самое, но по-другому изложенное (это изложение, может быть, сложнее с ходу понять, и тем более не понятно, как до него дойти, но зато оно очень хорошо помогает разложить все по полочкам, чтобы быть уверенными, что мы нигде ничего не сглючили):
Теорема (о двудольности графа): граф двудольный тогда и только тогда, когда в нем нет циклов нечётной длины.
Доказательство:
\underline Пусть граф двудольный. Тогда в нем вдоль каждого цикла цвета вершин чередуются, поэтому любой цикл обязательно имеет чётную длину.
\underline Пусть в графе нет циклов нечётной длины. Запустим вышеприведённый алгоритм. Он может остановиться, найдя противоречие, только если найдёт цикл нечётной длины, что невозможно. Следовательно, он корректно раскрасит граф, значит, граф двудольный. чтд.
Обратите внимание, что доказательство в одну сторону сильно отличается от доказательства в обратную. Ещё обратите внимание, что отсюда очевидно следует, что дерево (и вообще лес) — двудольный граф.
Как теперь реализовать этот алгоритм? Напрашивающаяся идея — поиск в ширину, он же волновой алгоритм. Вполне можно.
Но если немного подумать, то подойдёт любой обход графа, который переходит из одной вершины в другую только по рёбрам и обходит весь граф. Например, вполне подойдёт поиск в глубину; поскольку поиск в глубину реализовать обычно проще, чем в ширину, то обычно проверяют граф на двудольность с помощью поиска в глубину.
Итак, каждый раз, когда находим новую вершину, будем её красить в нужный цвет.
Итак, что тут. Массив was опять используем для хранения дополнительной информации: в данном случае цвета вершины (1 или 2). Может быть, логичнее его было бы назвать как-нибудь по-другому. В процедуре find, когда находим очередного соседа текущей вершины, смотрим: если он того же цвета, что и мы, то облом, иначе если он уже покрашен, то туда не сунемся, иначе красим (3-was[i] даёт как раз нужный цвет) и запускаем поиск из этой вершины. Обратите внимание, что красим вершину (т.е. заполняем was[j]) мы до входа в процедуру find(j), поэтому в начале процедуры ничего вообще не делаем. В главной программе теперь найдя ещё непокрашенную вершину, красим её (обязательно! т.к. не красим её в самой процедуре) и запускаемся. Обратите внимание, как сделана работа с переменной ok, которая хранит, не наши ли мы ещё противоречия.
Какой-то ужас тут получается. Поэтому имхо логичнее перенести всю работу в начало процедуры, а — внимание! — в процедуру будем передавать дополнительный параметр — цвет, в который надо покрасить эту вершину.
Теперь работа процедуры find имхо более очевидна: она пытается покрасить вершину i в цвет c. Во-первых, если вершина уже покрашена, то надо только посмотреть, в тот ли цвет (обратите внимание, что в прошлом варианте была проверка was[i]=was[j], а теперь was[i]<>c), и выйти. Иначе красим и смотрим соседей.
Ещё замечу, что, если в случае, когда граф недвудольный, нужно сделать что-то простое и завершить работу программы (например, вывести No solution и выйти), то можно с ok не возиться, а просто просто сделать что надо:
Ещё замечу, что можно переменную ok убрать, а процедуру find сделать функцией, возвращающей boolean. Можете попробовать это реализовать, это, даже, пожалуй, проще и правильнее. Наконец, если гарантируется, что граф двудольный, надо только его доли найти, то ok вообще не нужна.
Проверка, является ли граф деревом
Как вы знаете, деревом называется связный граф без циклов (все ещё рассматриваем только неориентированные графы), лесом называется произвольный, т.е. не обязательно связный, граф без циклов. Как проверить, является ли граф деревом или лесом? В принципе, понятно: проверить, что циклы в графе отсутствуют, можно просто запустив поиск в глубину и посмотрев, не придём ли мы когда-нибудь в ту вершину, где мы уже побывали.
Конкретно: если нам надо проверить, является ли граф деревом, то запустимся из первой вершины. Если хоть раз вернёмся в вершину, где мы уже побывали, то граф точно не дерево. Иначе в конце проверим, верно ли, что мы побывали во всех вершинах. Если да, то граф связен, а отсутствие циклов мы уже проверили — ок. Иначе не дерево.
Если нам надо проверить, является ли граф лесом, то все аналогично, только, аналогично поиску всех компонент связности, закончив поиск в глубину из первой вершины, запускаемся из первой ещё не посещённой и т.д. — такой же цикл, как и при поиске компонент связности.
Нахождение эйлерова пути и цикла
Я думаю, вы знаете, что такое эйлеров цикл — это цикл, который проходит по каждому ребру ровно один раз. Аналогично, эйлеров путь — это путь, который по каждому ребру проходит ровно один раз (но, в отличии от цикла, может начинаться и заканчиваться в разных вершинах). Я также думаю, что вы знаете критерий наличия эйлерова цикла и эйлерова пути в графе. Действительно, если в графе есть эйлеров цикл, то в при движении по нему в каждую вершину мы входим ровно столько же раз, сколько выходим. За время прохода по всему циклу мы прошли по все рёбрам, инцидентным данной вершине, следовательно, степень каждой вершины должна быть чётна (мы пока все ещё рассматриваем неориентированные графы). Совершенно аналогично, если в графе есть эйлеров путь, то степени только двух вершим могут быть нечётны — это будут начало и конец нашего пути: из начала мы вышли на один раз больше, чем вошли в него, с концом пути все наоборот. Ещё, очевидно, надо поставить некоторое условие на связность графа. Мы будем дальше считать граф связным, но это не есть необходимое условие.
Обратите внимание, что вышеприведённые рассуждения не доказывают существования цикла/пути, если эти условия выполняются. Существование цикла мы будем доказывать построением алгоритма, который будет решать эту задачу. Наш алгоритм будет находить цикл/путь в любом связном графе, удовлетворяющим условию на степени вершин (что делать для несвязного графа — это ваше задание).
Итак, пусть граф связен и степени всех его вершин чётны. Построим эйлеров цикл. Пожалуй, тут проще будет привести сам алгоритм, а потом объяснить, почему он работает. Итак, запустим поиск в глубину, но не будем контролировать возвращение в уже посещённые вершины: будем допускать сколько угодно раз приходить в одну и ту же вершину (очевидно, что в общем случае эйлеров цикл будет через каждую вершину проходить по нескольку раз, поэтому ясно, что без этого изменения поиск в глубину не поможет). Зато будем стирать ребра из графа, как только мы по ним прошли. Ясно, что тогда алгоритм до бесконечности работать не будет. Когда будем выходить из вершины, будем выводить её номер в выходной файл:
Обратите внимание, что стираем ребра мы двумя присваиваниями, ведь каждому ребру в матрице смежности соответствуют две единички.
Утверждается, что после работы этого алгоритма (точнее, после выполнения команды find(1)) на экран будет выведена последовательность вершин, которая образует эйлеров цикл. Чтобы понять это лучше, пожалуй, стоит разобрать простой пример. Рассмотрим граф, показанный ниже — в нем, очевидно, есть эйлеров цикл. Как будет работать наш алгоритм?
(пометка звёздочкой будет использоваться ниже)
Все. Вывели следующую последовательность на экран:
1 4 2 6 5 2 3 1
Это действительно эйлеров цикл, но, если сравнить с тем, как мы ходили по графу, то выглядит это очень странно: цикл получается какой-то каракатицей, проходя по рёбрам в обратную сторону по сравнению с тем, как мы по ним ходили при поиске в глубину. Я не буду строго доказывать, что этот алгоритм корректно находит цикл; пожалуй, самый лучший способ проверить его работу — это вручную промоделировать его работу на разных графах, стараясь придумать случай поподлее. Только скажу идею обоснования корректности работы. Текста много, но по-моему, он простой: я просто расписываю все подробно и повторяю по несколько раз 🙂
Итак, мы запустились из первой вершины v_1 и пошли в её соседа v_2, стерев по пути ребро. В результате степень как v_1, так и v_2, стала нечётной, т.к. изначально по условию они были чётными. Но это обозначает, что степень вершины v_2 теперь точно не равна нулю — значит, у неё есть ещё как минимум один сосед v_3, в который мы можем пойти. Пойдя в него, мы сотрём ребро v_2–v_3 и степень вершины v_2 опять станет чётной, зато степень v_3 станет нечётной. Значит, и у неё есть ещё как минимум один сосед v_4, в который мы и пойдём. И так далее, в каждый момент степени всех вершин будут чётными, за исключением первой v_1 и последней, в которую мы только что зашли, v_k. У этих двух вершин степени будут нечётными. Но это будет обозначать, что у каждой текущей вершины будет ещё как минимум один сосед и мы сможем идти так до бесконечности?! Что-то тут не так, мы же выяснили, что алгоритм бесконечно работать не может, в конце концов просто ребра кончатся. Значит. о! значит, в какой-то момент мы вернёмся в начальную вершину v_1! При этом мы сотрём ребра вдоль целого цикла и потому степени всех вершин будут чётными. Если степень вершины v_1 не ноль, то мы пойдём дальше, и совершенно аналогичными рассуждениями можно будет доказать, что мы опять вернёмся в неё. И так далее, до тех пор, пока на очередном возвращении в v_1 её степень не станет равной нулю. Тогда мы её и выведем в выходной файл.
Внимание! Это, пожалуй, конец основной идеи всех рассуждений. Мы доказали, что всегда первой выведенной в выходной файл вершиной будет та, с которой мы начали; с самого начала это имхо было весьма не очевидно. Если вы это ещё не осознали, попробуйте ещё раз это продумать; может быть, порисуйте примеры графов и посмотрите. Ещё раз кратко повторю основную идею: в каждый момент времени в каждую вершину в графе мы успели поровну раз войти и выйти, кроме самой первой вершины и той вершины, в которой мы находимся. Поэтому у всех вершин степени остались чётными, кроме этих двух вершин — если они не совпадают, то у них степени нечётные. Но тогда из текущей вершины мы можем пойти дальше. Значит, рекурсия остановится только эти две вершины будут совпадать, т.е. когда (в очередной раз) вернёмся в первую вершину. Значит, именно первую вершину мы и выведем первой.
Итак, что же дальше? А дальше, после того, как мы вывели вершину, про неё можно забыть: у неё степень точно ноль (т.к. мы не смогли никуда дальше пойти), поэтому в неё мы никогда больше не вернёмся (точнее, можем вернуться, но только откатываясь при выходе из рекурсии). Дальше мы будем откатываться по рекурсии назад и выводить все вершины по пути. Но они точно будут связаны рёбрами в исходном графе, т.к. мы по этим рёбрам шли вперёд. Значит, пока мы выводим корректный путь. Дальше в очередной момент мы выведем некоторую вершину u и откатимся до вершины v'_1, из которой будет куда пойти ещё (как вершина 2 в нашем примере); саму вершину v'_1 мы ещё не выведем к этому моменту. Мы пойдём в её соседа v'_2 и. опять попадём в такую же ситуацию, как уже было: у вершин v'_1 и v'_2 степени нечётные, а у остальных чётные. Поэтому из v'_2 мы пойдём куда-нибудь ещё и т.д.; остановиться мы сможем только в v'_1. (Обратите внимание, что степень самой начальной вершины v_1 уже давно ноль, и поэтому в ней мы, конечно, не сможем остановиться — не зря мы про неё забыли). Значит, мы выведем v'_1. Возникает вопрос: а корректно ли? Соединена ли она ребром с той вершиной, которую мы вывели перед этим? Да, конечно. Т.к. перед этим мы вывели u, а u — это та вершина, в которую мы в своё время, давным-давно, пошли из v'_1: ведь мы сравнительно недавно откатились из u в v'_1. Значит, вывод v'_1 корректен (если вы совсем запутались, то проследите это на нашем примере: тут v'_1=2, u=4, а обсуждаем мы корректность вывода 2 в операторе, помеченном звёздочкой. Вообще, переводите все рассуждения на наш пример, он, по-моему, довольно хорошо иллюстрирует тут все, о чем я говорю).
Так что наш вывод все ещё будет корректным. Далее мы опять будем откатываться назад до тех пор, пока не откатимся в вершину, откуда будет куда идти, и т.д. — а там опять все будет аналогично и т.д. Наконец, последней мы выведем ту же вершину, что и первой вывели: действительно, ведь мы из главной программы запустили find(v_1), поэтому последняя процедура find, из которой мы выйдем, будет именно эта, и последней выведенной вершиной будет v_1; а выше мы видели, что первой выведенной будет она же — т.е. действительно цикл замкнётся.
Более-менее понятно, что алгоритм работает. Правда, не уверен, что вышеприведённые рассуждения можно превратить в строгое доказательство (т.е. раскрыть «и т.д.» так, чтобы все было строго); может быть, строго все доказывается методом от противного — если честно, не знаю. Но идея, я надеюсь, ясна.
А тогда ясно и то, что нужно делать для случая поиска эйлерова пути и для работы в ориентированных графах. А именно, для эйлерова пути надо просто найти одну из двух вершин с нечётной степенью (пусть вершину v_1) и запуститься из неё. Аналогичными рассуждениями можно объяснить, что первая вершина, которую мы выведем, будет другая вершина с нечётной степенью, и что то, что мы выведем действительно путь в графе, и он закончится в вершине v_1.
В ориентированном графе несколько хитрее. Во-первых, там критерий немного другой: для цикла там надо требовать равенства входящей и выходящей степени для каждой вершины (т.е. равенства количеств входящих и выходящих рёбер). Во-вторых, поскольку мы выводим путь «каракатицей», то идти по рёбрам в поиске в глубину надо навстречу стрелкам, чтобы окончательный путь шёл как положено. Рассуждения, объясняющие корректность, проводятся аналогично. Ещё не забудем, что удалять обратное ребро тут не надо (т.е. когда идём из i в j, надо стирать только ребро i\to j, а j\to i не надо).
(На самом деле, конечно, я надеюсь, что вы напишите все алгоритмы, которые тут обсуждаются, но это — особо важное задание :))
Ещё отмечу, что всё это работает и для случая кратных рёбер, петель и т.д. (петля увеличивает степень соответствующей вершины на два). Алгоритм даже не придётся менять, кроме того, что надо аккуратнее хранить граф и стирать ребра (т.е., например, в матрице смежности хранить число рёбер между вершинами, которое может быть и больше 1 — в случае кратных рёбер —и стирать ребро уменьшением соответствующего элемента матрицы смежности).
А теперь немного обсудим сложность этого алгоритма. В той его реализации, которая приведена выше, сложность оценить непросто, но, пожалуй, можно так. Время работы одной процедуры, не считая рекурсивных вызовов, будет O(V). Всего вызовов процедур будет E, ведь именно столько вершин мы в итоге выведем. Поэтому все работает за O(VE).
Но, если подумать, то ясно, что алгоритм на самом деле делает кучу лишней работы. Действительно, если в find(i) мы уже дошли до вершины j, то точно все предыдущие ребра мы уже стёрли. Тогда, когда если мы в очередной раз запустим find(i), нам не надо будет перебирать все вершины сначала, можно начинать с j+1. (Речь не идёт о том, что нам делать, когда мы вернёмся на тот уровень рекурсии, где мы дошли до вершины j, а о том, что на более глубоком уровне рекурсии мы можем опять запустить find(i)). Можно, например, в особом массиве хранить, на какой вершине мы остановились, просматривая соседей i-ой (т.е. в cur[i] будем хранить, какого последнего соседа у i мы смотрели), и изменить цикл в find на что-нибудь типа
Теперь вроде должно бы работать быстрее (типа за O(V^2); но этот код я не продумывал до конца, вдруг здесь есть какие-нибудь подводные камни), но по-моему ещё проще написать все, если хранить граф списком соседних вершин (вообще, все основанное на поиске в глубину будет быстрее работать на списке соседних вершин — я уже говорил про это). Я, пожалуй, не буду приводить здесь соответствующей реализации (тут надо быть осторожным с удалением обратных рёбер, т.е. когда идёте из вершины i в j, удалить не только ребро i\to j, но и ребро j\to i; как следствие, для ориентированных графов, где удалять второе ребро не надо, тут все проще). Тем не менее это позволяет добиться времени работы O(E), как и всех остальных алгоритмов на поиске в глубину (т.е. лишней работы мы тут делать не будем, только ходить по рёбрам — по каждому по разу — и выводить вершины).