В этом видео мы обсудим пути и достижимость в ориентированных графах. Ориентированным путем мы будем называть последовательность вершин: v0, v1, и так далее, vk, аналогично неориентированному случаю, и из каждой вершины должно быть ребро в следующую. В отличие от неориентированного случая, тут теперь важна ориентация. Мы считаем, что из каждой вершины vi-тая должно быть ребро в вершину v(i+1), и оно должно быть именно в этом направлении. Длиной пути мы называем число шагов в нем — у нас это k. Вершины в пути могут повторяться, и если они не повторяются, то это простой ориентированный путь. Давайте рассмотрим примеры. Например, такая последовательность: A, B, C, D, A, C — это ориентированный путь, но при этом не простой. Действительно, это ориентированный путь — из A можно попасть в B, из B можно попасть в C (по ориентированному ребру), из C — в D, из D — в A, и из A можно пройти в C. Но это не простой путь, потому что вершина A повторяется два раза, вершина C повторяется два раза. Дальше вот такой путь: A, B, C, D, E — это простой ориентированный путь. Действительно, по ребрам можно пройти из A — в B, из B — в C, из C — в D и из D — в E, и вершины не повторяются. А вот такая последовательность A, C, E, D, A — не является ориентированным путем. Почему? Здесь, в принципе, почти между всеми вершинами можно пройти, но вот из E в D у нас нет ориентированного ребра, поэтому это не является ориентированным путем. Ориентированными циклами мы называем такие ориентированные пути, у которых последняя и первая вершины совпадают — это аналогично неориентированному случаю. Длина цикла — это число шагов в нем (у нас k). Например, в этом графе есть такой цикл: A, B, C, D, A. Действительно, по всем ребрам можно пройти — это видно на картинке. С точки зрения путей в графах, неориентированные графы можно задать с помощью ориентированных: пусть у нас есть неориентированный граф — как же мы можем это сделать? Достаточно просто раздвоить каждое ребро и поставить стрелки в разные стороны. Действительно, с точки зрения путей, если у нас раньше была связь между вершинами, то и теперь мы можем дойти как в ту, так и в другую сторону, так что граф остается тем же самым, просто мы с помощью ориентированного графа задали наш неориентированный. Все пути остаются путями и в ориентированном случае. Давайте обсудим достижимость в ориентированных графах. Мы говорим, что вершина u достижима из вершины v, если есть ориентированный путь из вершины v в вершину u. Это отношение транзитивно: если есть путь из вершины v в вершину u, а также есть путь из вершины u в вершину w, то есть путь и из v в w. Это легко увидеть — просто надо взять эти оба пути и их соединить, тогда получится один большой путь из вершины v в w. Но, в отличие от неориентированного случая, это отношение несимметрично. Например: есть путь из вершины v в w на этой картинке, но нет пути в обратную сторону. Это, на самом деле, довольно легко увидеть — достаточно просто заметить, что в вершину v не входит никаких ребер, а поэтому не может быть пути из w в v: такой путь обязательно своим последним ребром должен иметь ребро, входящее в вершину v, а его просто нет в графе. Итак, это отношение несимметрично; его можно симметризовать, но это мы обсудим чуть позже.