Пути и циклы

Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг - в орграфе) вида v₀, (v₀,v₁), v₁, ... , (v_n-1,v_n), v_n. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин - простой цепью. Путь может быть замкнутым (v₀=v_n). Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом.

Утверждение 1. Если в графе существует путь, ведущий из вершины v₀ в v_n, то существует и простая цепь между этими вершинами.

Доказательство: такую простую цепь можно построить, "выкинув" из пути все циклы.

~

Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным - в противном случае. Несвязный граф состоит из нескольких связных компонент (связных подграфов).

Для орграфов понятие связности является более сложным: различают сильную связность, одностороннюю связность и слабую связность. Орграф называется сильно связным, если для любых двух его вершин v и u существует как маршрут из v в u (v->u), так и из u в v (u->v). Орграф называется односторонне связным, если для любых двух его вершин u и v существует по крайней один из маршрутов v->u или u->v. Наконец, орграф называется слабо связным, если связен неориентированный граф, получаемый из этого орграфа путем снятия ориентации с дуг. Очевидно, что любой сильно связный граф является односторонне связным, а односторонне связный - слабо связным, но не наоборот.