Давайте обсудим понятие сильной связности для графов. У нас есть отношение достижимости, мы его уже завели, и мы увидели, что оно несимметрично, но его можно симметризовать. Мы назовем вершину А сильно связанной с вершиной В, если из каждой из этих вершин есть путь в другую. Например, на этой картинке есть вершины u и w, и они сильно связаны. Действительно, есть путь из u в w, вот он, и есть также обратный путь, путь из w в u. А, например, вершины v и u — они уже не сильно связаны. Действительно, есть путь в одну сторону — из v в u, но нет пути в обратную сторону. Почему его нет? Потому что просто нет входящих ребер в вершину v. Граф называется сильно связным, если из любой его вершины есть ориентированный путь в любую другую. Это, на самом деле, очень важное понятие — сильная связность бывает очень важна. Например, для транспортной задачи она просто говорит о ее разрешимости, то есть если мы хотим находить маршруты из каждой точки в каждую, то сильная связность говорит о разрешимости этой задачи в принципе. Что делать, если граф не сильно связный? Тогда оказывается, что его вершины можно разбить на компоненты сильной связности следующим образом: каждая вершина лежит ровно в одной компоненте, при этом любые вершины в одной компоненте сильно связаны (из любой вершины в компоненте можно дойти в любую другую), и вершины из разных компонент не сильно связаны. Давайте посмотрим на пример: вот довольно большой граф, и оказывается, что, действительно, его вершины можно разбить на такие компоненты связности. Вот они, их четыре. Давайте посмотрим, как они устроены. Давайте начнем справа налево. Во-первых, можно заметить, что есть вершины F, G и K; на них у нас цикл, и поэтому понятно, что из любой из них можно дойти в любую другую, но видно, что мы не можем из них попасть в какую-то еще вершину, поэтому они сильно связаны между собой, но не сильно связаны с остальными вершинами. Дальше есть вершина E, из нее можно попасть в вершины F, G и K, но нельзя попасть в более левые вершины; и эта вершина образует свою, отдельную, компоненту связности — из нее можно попасть только в нее саму и обратно тоже, а других вершин, в которые можно попасть из нее и обратно тоже, таких вершин нет. Дальше у нас есть вот эта большая компонента, и вершины в ней сильно связаны, потому, что тут есть два цикла: из B можно попасть в H, потом в D и обратно; и внизу тоже есть цикл: из D можно попасть в I, потом в A и обратно. Так что тут можно из любой вершины дойти в любую другую. Дальше, в более правые вершины мы можем дойти из этой компоненты, но не можем попасть обратно, а из вершины С мы можем попасть в эти вершины, но не можем попасть обратно, поэтому эти вершины образуют отдельную компоненту. И наконец, вершина С образует свою отдельную компоненту — из нее можно попасть куда угодно, но не обратно. Из любой другой вершины в С попасть нельзя, поэтому С образует свою, отдельную компоненту сильной связности. Давайте сделаем следующее: для каждой компоненты связности этого графа; мы построим сейчас новый граф, и для каждой компоненты связности этого графа мы рассмотрим свою отдельную вершину. У нас будет, соответственно, четыре вершины, потому что есть четыре компоненты связности. Мы соединим ребрами те компоненты связности, для которых есть ребро между какими-то двумя вершинами этих компонент, то есть есть хотя бы одно ребро между вершинами этих компонент, и это ребро будет ориентированное. Например, из С есть вершина в B, и в I тоже. Поэтому мы соединяем ребром вершину, соответствующую компоненте С, с вершиной, соответствующей большой компоненте. Дальше из большой компоненты есть ребра в E и в F, и поэтому мы проводим ребра направо, и из компоненты, соответствующей вершине E, есть ребро к компоненте, соответствующей вершинам F, G и K. Соответственно, проводим такое ребро. Такой граф называется метаграфом изначального графа; важно заметить, что он ациклический, то есть видно, что в нем нет циклов. Действительно, если бы был цикл в этом графе, то несколько компонент объединились бы в одну — мы могли бы попасть из любых вершин этих компонент в любые другие вершины этих же компонент. Они в изначальном графе образовали бы общую компоненту, раз они лежат в разных компонентах, то в этом графе нет циклов. Соответственно, вот мы увидели еще один пример, как могут возникать ациклические графы. В следующем уроке мы продолжим обсуждение ориентированных графов, в частности, мы обсудим, как эффективно искать компоненты сильной связности..
