Определение 13. Ориентированный граф называется турниром, если для любой пары вершин в нем существует ровно одно инцидентное им ориентированное ребро.
Задача 1. Турнир задан списком ребер. Необходимо найти в нем цикл длины 3 или сообщить, что такого нет (N < 5000, где N - количество вершин в графе).
Решение. Цикл длины три есть в графе тогда и только тогда, когда в нем вообще есть цикл. Действительно, в одну сторону очевидно. Докажем теперь достаточность: возьмем найденный цикл (его можно найти, например, при помощи поиска в глубину) и будем его постепенно сужать. Рассмотрим три подряд идущие вершины ориентированного цикла (занумеруем их от 0 до 2). Если от 0 к 2 ведет ребро, значит, мы сузили цикл, иначе, если его нет (так как наш граф - турнир), есть ребро от 2 к 0, значит, мы нашли цикл длины три. Таким образом, мы научились решать эту задачу за сложность DFS.
Задача 1. Турнир задан списком ребер. Необходимо найти в нем цикл длины 3 или сообщить, что такого нет (N < 5000, где N - количество вершин в графе).
Решение. Цикл длины три есть в графе тогда и только тогда, когда в нем вообще есть цикл. Действительно, в одну сторону очевидно. Докажем теперь достаточность: возьмем найденный цикл (его можно найти, например, при помощи поиска в глубину) и будем его постепенно сужать. Рассмотрим три подряд идущие вершины ориентированного цикла (занумеруем их от 0 до 2). Если от 0 к 2 ведет ребро, значит, мы сузили цикл, иначе, если его нет (так как наш граф - турнир), есть ребро от 2 к 0, значит, мы нашли цикл длины три. Таким образом, мы научились решать эту задачу за сложность DFS.
