Решение задачи: Сильная связность ориентированного графа

Ориентированный граф называется сильно связным, если из любой его вершины можно добраться до любой другой вершины, следуя по направлению стрелок. Проверим каждый граф: 1. Первый граф (7 вершин): Проверим возможность вернуться в вершину 1. В вершину 1 ведет стрелка из 4. В 4 можно попасть из 3 или 5. В 3 из 2, в 2 из 1. Получаем цикл: \( 1 \to 2 \to 3 \to 4 \to 1 \). Теперь проверим нижнюю часть: из 1 идем в 2, из 2 в 3, из 3 в 4, из 4 в 1... Но как попасть в 6 или 7? Из 5 можно попасть в 6, из 6 в 7, из 7 в 5. Это отдельный цикл. Связь между ними: из 5 можно уйти в 4. Однако из верхнего цикла (1-2-3-4) нет ни одной стрелки, ведущей в нижний цикл (5-6-7). Следовательно, из вершины 1 нельзя попасть в вершину 6. Граф не является сильно связным. 2. Второй граф (4 вершины): Проверим пути: \( 1 \to 2 \to 4 \to 3 \to 1 \). Этот цикл охватывает все вершины графа. Поскольку существует замкнутый путь, проходящий через все вершины, из любой точки можно дойти до любой другой. Граф сильно связный. 3. Третий граф (5 вершин): Посмотрим на вершину 3. В неё входит стрелка из 2, но из самой вершины 3 выходит только одна стрелка в вершину 4. Из вершины 4 стрелки ведут только "дальше" (путей назад к 1, 2 или 3 нет, так как из 4 нет выходящих стрелок в ту сторону). Из 4 вообще нет выходящих стрелок, это "сток". Если из вершины нельзя выйти, граф не может быть сильно связным. 4. Четвертый граф (5 вершин): Проверим наличие путей: \( 1 \to 3 \to 4 \to 2 \). Из 2 стрелка ведет в 4 (уже были). Из 5 можно попасть в 1 или 2. Заметим вершину 5: в неё не входит ни одна стрелка. Это "источник". Если в вершину нельзя попасть из других точек, граф не является сильно связным. 5. Пятый граф (6 вершин): Проверим пути: \( 1 \to 5 \to 6 \to 1 \). Это цикл. Также есть \( 1 \to 3 \to 4 \to 2 \). Но из вершины 2 стрелка ведет только в 4. Из вершин 2, 3, 4 невозможно попасть обратно в 1, 5 или 6. Граф не является сильно связным. Ответ: Сильно связным является только: — Второй граф (с 4 вершинами, где есть цикл \( 1 \to 2 \to 4 \to 3 \to 1 \))