В этом видео мы обсудим ориентированный ациклический граф. Граф называется ориентированным ациклическим, если в нем нет ориентированных циклов. И вот на левой картинке граф действительно является ориентированным ациклическим, а на правой нет. Как это увидеть? С правой картинкой все просто, достаточно просто найти цикл, и действительно просто — вот этот цикл. С левой — можно поперебирать случаи и убедиться, что в графе нет циклов. Но давайте проговорим, как это делать быстро. Если в графе есть цикл, то в каждую вершину цикла входит хотя бы одно ребро. И давайте сразу заметим, что вершина A в цикл входить не может, потому что в нее не входит ни одного ребра. Как только мы заметили, что вершина A в цикл входить не может, мы можем заметить, что вершина B тоже не может входить в цикл. В нее есть входящее ребро, но оно ведет из вершины A, а вершина A уже не может входить в цикл, поэтому B тоже не может войти в цикл. Дальше аналогично —вершина C не может войти в цикл, потому что в нее есть ребра только из вершины A и вершины B, а они в цикл не входят, поэтому цикла, проходящего через C, не получится. И дальше, аналогично, вершина F не может входить в цикл, D не может входить в цикл, и E тоже не может входить в цикл, так что ни одна вершина не может входить в цикл, поэтому цикла в графе нет. Хорошо, мы уже видели пример ациклического ориентированного графа в начале курса, когда мы подсчитывали пути из вершины S в вершину T. Заметим, что тогда у нас граф был ациклический. Действительно, если бы у нас в графе был цикл, то могло так случиться, что путей было бы бесконечно много. Тут важно, что граф был ациклический. И где же такие графы могут встречаться? Например, это может быть граф зависимостей курсов в университете. В таком графе не должно быть циклов, потому что нехорошо, если у нас есть зацикливание в зависимостях курсов, так как — как мы тогда будем изучать эти курсы, если они друг от друга зависят по циклу. Или, например, это может быть граф зависимостей работ. Давайте обсудим этот пример чуть подробнее. Пусть у нас есть n дел, которые нам нужно сделать и между которыми есть зависимости. Для некоторых дел A и B известно, что A нужно выполнить до B. И тогда, что еще? Мы хотим выполнять эти работы одну за другой. И мы можем построить граф. Вершины — это наши работы, а ориентированные ребра — это зависимости. Мы проводим ребро из вершины A в вершину B, если работу A нужно выполнить до работы B. Получается такой граф, и мы хотели бы перенумеровать вершины так, чтобы ребра вели из вершин с меньшим номером в вершины с большим номером. Мы хотим выполнять работы последовательно, это то же самое, что перенумеровать их, а потом выполнять их в порядке возрастания номера. Соответственно, вот мы хотим перенумеровать их таким образом. И когда это возможно сделать? Есть простое наблюдение, когда это нельзя сделать. Ясно, что если в графе есть ориентированный цикл, то это сделать не получится, потому что если мы расставим так вершины по циклу, то первая из них, в нее будет входить ребро из какой-то более поздней вершины, которая с большим номером в том же цикле. Но вот что оказывается важным — это единственное препятствие. То есть ациклические графы — это в точности те графы, для которых возможно вот такое упорядочивание вершин. Давайте это немного формализуем. Мы называем топологической сортировкой сортировку вершин графа так, что все ребра ведут из вершин с меньшим номером в вершины с большим номером. И вот здесь есть пример такого графа, и он отсортирован, то есть вот у нас последней вершиной стоит A и так далее. То есть видно, что получилась топологическая сортировка. И мы сейчас докажем такую теорему, что всякий ациклический граф можно топологически отсортировать. Мы уже видели, что видно обратное: если граф можно топологически отсортировать, то в нем нет циклов, мы это уже заметили. Вот верно и обратное — всякий ориентированный ациклический граф можно отсортировать. Как мы это докажем? Во-первых, мы докажем, что в каждом ациклическом графе есть сток, есть вершина, из которой не выходит ребер. А как только мы это докажем, то дальше все будет довольно просто. Мы берем сток и говорим, что это будет последняя вершина в нашем, в нашей нумерации. Удаляем этот сток и повторяем. Опять же, в оставшемся графе по-прежнему нет циклов, есть новый сток, мы объявляем его последним из оставшихся вершин. Давайте рассмотрим пример. Вот наш граф — и кто же здесь является стоком? Например, вершина A является стоком, из нее не выходит ребер. Давайте объявим ее последней, удалим ее из графа и посмотрим, кто является стоком в оставшемся. Вот вершина B является стоком в оставшемся графе. Мы объявляем ее последней из оставшихся, опять же удаляем ее и смотрим, кто является стоком среди оставшихся вершин. Вершина C является стоком. Опять же, пишем ее следующей с конца, удаляем, дальше вершина E и дальше вершина D. Вот, собственно, мы все вершины и упорядочили. Хорошо, осталось доказать. Чтобы доказать теорему, нам осталось доказать, что в графе есть сток. Давайте это докажем. Докажем это от противного. Пусть у нас стока нет, и из каждой вершины выходит хотя бы одно ребро. Посмотрим, почему так не может быть. И как мы будем это делать? Начнем ходить просто по вершинам графа. Возьмем совершенно любую вершину и начнем ходить по ребрам. Из каждой вершины выходит хотя бы одно ребро, поэтому из этой вершины тоже выходит ребро. Давайте по нему пройдем. Дальше мы попали в следующую вершину, из нее тоже выходит ребро, потому что из каждой есть ребро, пройдем по этому ребру и так далее. Будем ходить, пока, вот каждый раз будем идти в следующую вершину. Заметим, что вершин в графе у нас конечно, поэтому до бесконечности это продолжаться не может, и рано или поздно мы попадем в ту же самую вершину, в которой уже были. То есть окажется, что мы попадем в ту же вершину, в которой мы уже были. И это уже противоречие, потому что тогда у нас образовался цикл, раз мы попали в вершину, в которой мы уже были, мы дальше можем ходить по этому циклу в этом цикле. И получается, что вершины ациклического графа можно топологически отсортировать.
