Условимся, что в этом и следующих параграфах рассматриваются орграфы без петель и кратных дуг.

Введем аналоги понятий маршрута, циклического маршрута и их частных случаев для орграфа.

Определение. Пусть G – орграф. Ориентированным маршрутом (или ормаршрутом) графа G называется последовательность дуг е₁,е₂,…,е_k, для которой существует последовательность вершин v₀,v₁,…,v_k такая, что дуга е_i выходит из v_i-1 и заходит в v_i для 1£i£k. Вершина v₀ называется началом, v_k – концом маршрута, а число k – длиной маршрута.

Мы будем говорить, что маршрут e₁,e₂,…,e_k проходит через дуги e₁,…,e_k и вершины v₀,v₁,…,v_k. Так как рассматриваются орграфы без петель и кратных дуг, то последовательность вершин v₀,v₁,…,v_k однозначно определяет маршрут e₁,…,e_k. Этим фактом мы будем иногда пользоваться при задании маршрута. Маршрут с началом в вершине v и концом в вершине w будем называть (v,w)–маршрутом.

Определение. Ормаршрут, у которого начало совпадает с концом называется циклическим ормаршрутом.

Например, для графа G, изображенного на рис. 6.6 последовательность дуг u₁,u₃,u₆,u₁₀ является ормаршрутом, а последовательность дуг u₁,u₃,u₆,u₈,u₅,u₃,u₂ – циклическим ормаршрутом.

Определение. Ормаршрут называется путем, если он проходит по разным дугам и простым путем, если он проходит по разным вершинам (кроме возможного случая v₀=v_k). Циклический путь называется контуром, а циклический простой путь – простым контуром.

Так, для графа на рис. 6.6 последовательность u₃,u₆,u₈,u₇,u₁₀ – путь, который не является простым путем, так как дважды проходит через вершину а₅, а последовательность u₃,u₆,u₈,u₅ – простой контур.

Следующее утверждение является простым следствием определений.

Предложение. Если x и y – различные вершины орграфа G и существует (x,y)-ормаршрут, то существует простой (x,y)–путь. Если орграф содержит циклический ормаршрут, то G содержит простой контур.

Определим теперь аналог связности для классов орграфов.

Определение. Пусть х и y – вершины орграфа G. Вершина y достижима из х, если существует (x,y)–путь. Любая вершина достижима сама из себя. Вершины х и y сильно связаны, если они достижимы одна из другой.

Например, для графа, изображенного на рис. 6.6, вершины а₁ и а₄ сильно связаны, вершина а₆ достижима из а₁, но вершина а₁ недостижима из а₆.

Рис. 6.6

Легко видеть, что отношение сильной связности является отношением эквивалентности. Этому отношению соответствует разбиение на классы сильно связанных между собой вершин.

Определение. Класс разбиения (вместе с дугами, которые соединяют вершины этого класса) называется компонентой сильной связности.

Граф, изображенный на рис. 6.7 имеет три компоненты сильной связности. Они обведены пунктирными линиями.

Рис. 6.7

Заметим, что существуют дуги, не принадлежащие ни одной из компонент сильной связности.

Определение. Орграф называется сильно связным, если любые две его вершины сильно связаны.

Другими словами, орграф сильно связан, если он состоит из одной компоненты сильной связности.

Следующее утверждение часто бывает полезным.

Теорема 6.1. Орграф G является сильно связанным тогда и только тогда, когда в G содержится циклический ормаршрут, проходящий по всем вершинам графа.

Доказательство. Пусть G сильно связный граф. Возьмем циклический ормаршрут Р графа G, проходящий по наиболее возможному числу вершин. Как отмечалось, ормаршрут можно задавать последовательностью вершин. Пусть это будет последовательность х₀,x₁,x₂,…,x_k,x₀. Предположим, что ормаршрут Р не проходит через вершину w. Так как G – сильно связный граф, то существует (x₀,w) – маршрут x₀,y₁,…,y_l,w и (w,x₀) – маршрут w,z₁,…,z_m,x₀. Но тогда циклический ормаршрут x₀,x₁,…,x_k,x₀,y₁,…,y_l,w,z₁,…,z_m,x₀ будет проходить по большому числу вершин, нежели ормаршрут Р. Следовательно, Р проходит по всем вершинам графа G.

Предположим теперь, что граф G содержит циклический ормаршрут Р, проходящий по всем вершинам графа G. Возьмем две различные вершины u и v графа G. Тогда

P=(x₀,x₁,…,x_i,u,x_i+1,…,x_j,v,xj₊₁,…,x₀).

Следовательно, существует (u,v) – маршрут u,x_i+1,…,x_j,v и существует (v,u) –маршрут v,x_j+1,…,x₀,x₁,…,x_i,u. Это означает, что вершины u и v сильно связаны.

Теорема доказана.

В заключение параграфа введем понятия эйлеровости и гамильтоновости для ориентированных графов.

Определение. Орграф называется эйлеровым, если в нем существует контур, проходящий через каждую дугу.

Граф G₂ (см. рис. 6.8) является эйлеровым, а G₁ нет.

Рис. 6.8

Ясно, что эйлеров граф без изолированных вершин будет сильно связным. Нетрудно понять также, что в таком графе полустепень исхода вершины равна полустепени захода. Оказывается справедливо и обратное.

Теорема 6.2. Орграф G без изолированных вершин является эйлеровым тогда и только тогда, когда G сильно связан и r⁺(v)=r^-(v) для любой вершины v графа G.

Теорема представляет собой аналог теоремы Эйлера о циклах. Доказательство теоремы 6.1 легко получается из доказательства теоремы Эйлера и поэтому здесь не приводится.

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

Граф G₃, изображенный на рис. 6.9, является гамильтоновым, а граф G₄ не является таковым.

Рис. 6.9

Задача распознавания гамильтоновости в классе орграфов имеет ту же вычислительную сложность, что и в неориентированном случае. В силу этого нет простых критериев гамильтоновости. Из достаточных условий гамильтоновости приведем без доказательства аналог теоремы Дирака.

Теорема 6.3. Пусть G – сильно связанный граф, имеющий n вершин. Если для любой вершины v выполняются неравенства

r⁺(v)³n/2, r^-(v)³n/2,

то G – гамильтонов граф.

Условие теоремы является достаточно сильным, поэтому для доказательства гамильтоновости теорема применима довольно редко.