Определение. Орграф G называется бесконтурным, если G не имеет контуров.

На рис. 6.10 приведены примеры бесконтурных графов.

Рис. 6.10

Любой граф частично упорядоченного множества является бесконтурным. Действительно, если G – граф частично упорядоченного множества (V, £) и граф G содержит контур x₀,x₁,…,x_k,x₀, то x₀ £ x₁ £ … £ x_k £ x₀. В силу антисимметричности из этих неравенств следует равенство x₀ = x₁. Аналогично получаем, что x₁ = x₂ = … =x_k. Однако контур не может состоять из одной вершины, поскольку G не содержит циклов.

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

Теорема 6.4. Любой бесконтурный орграф добавлением дуг можно превратить в граф линейно упорядоченного множества.

Доказательство. Рассмотрим две процедуры добавления дуги к орграфу, которые назовем процедурой А и процедурой В. Пусть x и y различные вершины графа G, причем в G нет (x,y)–дуги. Тогда если существует вершина t и дуги (x,t) и (t,y), то применение процедуры А состоит в добавлении к графу G (x,y)–дуги. Процедура В состоит в добавлении к графу G дуги (x,y) для различных вершин x и y, если вершины x и y не смежны, т.е. если нет дуг (x,y) и (y,x).

Убедимся в том, что если G – бесконтурный граф и граф G’ получен из G однократным применением процедуры А, то G’ - бесконтурный граф. Действительно, предположим, что после добавления процедурой А дуги (x,y) возник контур: x,y,y₁,…,y_k,x. Можно считать, что это простой контур. Поскольку дуга (x,y) добавлена, то существует в графе G вершина t и дуги (x,t) и (t,y). Но тогда последовательность x,t,y,y₁,…,y_k,x является контуром в графе G. Следовательно, G′ - бесконтурный граф.

Докажем теперь, что если G – граф частично упорядоченного множества и граф G’ получен из графа G однократным применением процедуры B, то G’ - бесконтурный граф. Пусть, напротив, после добавления дуги (x,y) в графе G’ появился контур: x,y,y₁,y₂,…,y_k,x. Тогда, поскольку G – граф частично упорядоченного множества и (y,y₁), (y₁,y₂),…,(y_k,x) – дуги этого графа, то G содержит дугу (y,x). Но в этом случае процедурой В нельзя добавлять дугу (x,y). Следовательно, граф G’ является бесконтурным.

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

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

Важный класс бесконтурных графов составляют ориентированные деревья.

Во многих приложениях дерево удобно считать ориентированным графом. Как показывает пример на рис. 6.11, «превратить» дерево в ориентированный граф несложно.

Рис. 6.11

Дадим соответствующее определение.

Определение. Ориентированный граф G называется ориентированным деревом, если выполняются следующие условия:

существует в точности одна вершина (корень), полустепень захода которой равна нулю;

полустепень захода любой вершины, кроме корня, равна единице,

для любой вершины v, отличной от корня, существует путь из корня в эту вершину.

Отметим два свойства ориентированных деревьев.

Теорема 6.5. Пусть G – ориентированное дерево с корнем v₀ .

Тогда G – бесконтурный граф для любой вершины v¹v₀ существует единственный путь из v₀ в v.

Доказательство. Предположим, что в дереве G есть контур. Поскольку G не содержит кратных дуг, то контур зададим последовательностью вершин: x₁,x₂,…,x_k,x₁. Среди указанных вершин нет корня v₀, поскольку r⁺(v₀)=0. В частности, x₁¹v₀. Тогда существует путь v₀=y₁,y₂,…,y_l=x₁, из v₀ в x₁. Этот путь вначале проходит через вершины, не принадлежащие контуру. В то же время путь содержит вершины из контура. Пусть y_i – первая вершина пути, которая принадлежит и контуру. Но тогда r⁺(y_i)³2, что противоречит определению ориентированного дерева. Следовательно, дерево не содержит контуров.

Если существует два пути из v₀ в v то, как легко видеть должна существовать общая вершина w этих путей, для которой r⁺(w)³2. Как и выше, получаем противоречие.

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