Проверка ориентированного графа на наличие циклов путем отбрасывания «истоков» и «стоков»

У нас исток вершина V0, ее исходящие дуги X0={(0,1),(0,2),(0,3)}, рис. 1.6.

Рисунок 1.6 — Выделение первого истока Теперь за исток принимаем вершину V1, отбрасываем ее и дуги X1={(1,2), (1,4), (1,5), (1,6)}, рис. 1.7.

Рисунок 1.7 — Новые истоки после отбрасывания V0.

Теперь истоком стала вершина V2, отбрасываем ее и дуги X2={(2,3), (2,5)}, рис. 1.8. математический граф вершина матрица.

Рисунок 1.8 — Истоки после отбрасывания V2.

В оставшемся подграфе истоком является вершина V4, отбрасываем ее и дуги X4={(4,6), (4,5)}.

Рисунок 1.9 — Истоки после отбрасывания V4.

В оставшемся подграфе истоком является вершина V5, отбрасываем ее и дуги X5 ={(5,3), (5,6), (5,8)}, рис. 1.10.

Рисунок 1.10 — Подграф, полученный путем отбрасывания вершины V5.

В оставшемся подграфе два истока — 3 и 6, выбираем вершину V3, отбрасываем ее и дуги X3 ={(3,8), (3,9)}, рис. 1.11.

Рисунок 1.11 — Подграф, полученный отбрасыванием вершины V3.

В оставшемся подграфе два истока — 6 и 7, выбираем вершину V6, отбрасываем ее и ее дугу X6 ={(6,9)}, рис. 1.12.

Рисунок 1.12 — Подграф, полученный отбрасыванием вершины V6.

В оставшемся подграфе истоком является вершина V7, отбрасываем ее и дуги X7 ={(7,8), (7,9)}, рис. 1.13.

Рисунок 1.13 — Подграф, полученный отбрасыванием вершины V7.

В результате у нас остается подграф из одной дуги. Одна дуга не может являться циклом (если это не петля в вершине), а следовательно, в результате исследования графа мы доказали, что граф Gор циклов не имеет.