Основные определения

Графы, как уже отмечалось в примерах, есть способ „визуализации" связей между определенными объектами. Связи эти могут быть „направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.

Построение математического определения графа осуществляется путем формализации и „объектов", и „связей" как элементов некоторых (как правило, конечных) множеств.

Основные понятия для неориентированных и ориентированных графов удобно вводить „параллельно". Такое изложение позволит наглядно сопоставить соответствующие понятия.

Неориентированные графы	Ориентированные графы
Неориентированный граф G задается двумя множествами G = (V, E), где V — конечное множество, элементы которого называют вершинами или узлами; Е — множество неупорядоченных пар на V, т.е. подмножество множества двухэлементных подмножеств V, элементы которого называют ребрами. Для каждого ребра {u, v} ∈ Е считаем, что u и v — различные вершины.	Ориентированный граф G задается двумя множествами G = (V,E), где V — конечное множество, элементы которого называют вершинами или узлами; Е — множество упорядоченных пар на V, т.е. подмножество множества V × V, элементы которого называют дугами.
Если ребро е = {u, v}, то говорят, что ребро е соединяет вершины u и v, и обозначают это uv; если необходимо, указывают имя графа G: uGv.	Если дуга е = (u, v), то говорят, что дуга е ведет из вершины u в вершину v, и обозначают это u → v; если необходимо, указывают имя графа G: u →G v
Вершины u и v, соединеные ребром (uv), называют смежными, а также концами ребра {u, v}. Если uv, говорят, что вершины u и v связаны отношением непосредственной достижимости.	Вершины u и v, такие, что из вершины u в вершину v ведет дуга (u → v), называют смежными, причем u называют началом, а v — концом дуги (u, v). Дугу, начало и конец которой есть одна и та же вершина, называют петлей. Если u → v, то говорят, что вершины u и v связаны отношением непосредственной достижимости.
Ребро е называют инцидентным вершине v, если она является одним из его концов.	Дугу (u,v) называют заходящей в вершину v и исходящей из вершины u. Дугу называют инцидентной вершине v, если она заходит в v или исходит из v.
Степенью вершины v называют число dgv всех инцидентных ей ребер.	Полустепенью захода вершины v называют число dg  (v) заходящих в нее дуг, а полустепенью исхода вершины v — число dg+(v) исходящих из нее дуг. Степень вершины v, обозначаемая dg(v), — это сумма полустепеней захода и исхода.
Для вершины v множество Г(v) = {х:xv} называют множеством смежных с v вершин. Справедливо равенство dg(v) = |Г(v)|.	Для вершины v множество Г(v) = {х: v → х} называют множеством преемников вершины v, а множество Г-1(v) = {х: x → v} - множеством предшественников вершины v. Справедливы равенства dg+(v) = |Г(v)|, dg  (v) = |Г-1(v)|.
Цепь в неориентированном графе G — это последовательность вершин (конечная или бесконечная) v0, v1, ..., vn, ..., такая, что vi,vi+1 для любого i, если vi+1 существует. (Под конечной последовательностью понимается кортеж вершин.)	Путь в ориентированном графе G — это последовательность вершин (конечная или бесконечная) v0, v1, ..., vn, ..., такая, что vi, → vi+1 для любого i, если vi+1 существует.
Для конечной цепи v0, v1, ..., vn число n (n ≥ 0) называют длиной цепи. Таким образом, длина цепи есть число ее ребер, т.е. всех ребер, соединяющих вершины vi и vi+1 (i = 0,n—1). Цепь длины 0 — это произвольная вершина графа.	Для конечного пути v0, v1, ..., vn число n называют длиной пути (n ≥ 0). Тем самым длина пути есть число его дуг, т.е. всех дуг, которые ведут из вершины vi в вершину vi+1 (i = 0,n—1). Путь длины 0 — это произвольная вершина графа.
Говорят, что вершина v неориентированного графа G достижима из вершины и этого графа и обозначают u*v, если существует цепь v0, v1, ..., vn, такая, что u = v0, vn = v (при этом говорят также, что данная цепь соединяет вершины u и v, которые называют концами цепи). Таким образом, задано отношение достижимости * в неориентированном графе. Оно является рефлексивно- транзитивным замыканием отношения непосредственной достижимости.	Говорят, что вершина v ориентированного графа G достижима из вершины и этого графа и обозначают u ⇒* v, если существует путь v0, v1, ..., vn, такой, что u = v0, v = vn (при этом говорят, что данный путь ведет из вершины и в вершину v, называя первую вершину началом, а вторую — концом данного пути). Таким образом, задано отношение достижимости ⇒* в ориентированном графе. Оно является рефлексивно-транзитивнглм замыканием отношения → непосредственной достижимости.
Отношение достижимости в неориентированном графе рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности.	Отношение достижимости в ориентированном графе рефлексивно и транзитивно, но в общем случае не антисимметрично: если две вершины ориентированного графа достижимы одна из другой, то из этого вовсе не следует, что они совпадают. Таким образом, отношение достижимости в ориентированном графе есть отношение предпорядка.
Если существует цепь ненулевой длины, соединяющая u и v, то пишут u+v. Если необходимо явно указать длину цепи, то пишут unv и говорят, что существует цепь длины n, соединяющая u и v.	Если существует путь ненулевой длины, ведущий из u в v, то пишут u ⇒ +v. Если необходимо явно указать длину пути, то пишут u ⇒ nv и говорят, что существует путь длины n, ведущий из u в v.
Простая цепь — это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра попарно различны.	Простой путь — это путь, все вершины которого, кроме, быть может, первой и последней, попарно различны.
Простую цепь ненулевой длины с совпадающими концами называют циклом.	Простой путь ненулевой длины, начало и конец которого совпадают, называют контуром.
Произвольную цепь ненулевой длины с совпадающими концами, все ребра которой попарно различны, будем называть замкнутой цепью.	Произвольный путь ненулевой длины, начало и конец которого совпадают, будем называть замкнутым путем.
Неориентированный граф, не содержащий циклов, называют ациклическим графом.	Ориентированный граф, не содержащий контуров, называют бесконтурным графом.

Замечание 5.1. Требование, чтобы все ребра простой цепи неориентированного графа были попарно различными, существенно. Если его снять, то цепь вида u, v, u, где u⁺v, будет циклом, в котором одно и то же ребро {u, v} проходится дважды в противоположных направлениях, хотя такую цепь естественно циклом не считать. Не будет эта цепь в соответствии с принятой терминологией и замкнутой цепью.

В неориентированном графе на рис. 5.1 цепь abcdeca является примером замкнутой цепи.

Замечание 5.2. В общем случае в ориентированном графе пересечение множества преемников Г(v) вершины v и множества Г^-1(v) ее предшественников будет не пусто, если есть петля (v, v): Г(v) ∩ Г^-1(v) ≠ ∅

.

Пример 5.1. Расмотрим неориентированный граф, изображенный на рис. 5.2. Он задается множеством вершин

V ={v₁,v₂,v₃,v₄,v₅,v₆,v₇}

и множеством неупорядоченных пар

Е = {{v₁,v₂},{v₁,v₃},{v₂,v₃},{v₃,v₄},{v₅,v₆}}.

В этом графе последовательность вершин v₁,v₃,v₄ есть простая цепь, а последовательность v₁,v₃,v₂v₁,v₃,v₄ — цепь, не щаяся простой, поскольку в ней есть совпадающие ребра. Последовательность вершин v₃,v₁,v₂,v₄ не является цепью, поскольку в графе нет ребра {v₂,v₄}. Последовательность v₁,v₃,v₂,v₁ есть цикл, а последовательность v₄,v₃,v₁,v₂,v₃,v₄ — цепь с совпадающими концами, но не цикл, поскольку эта цепь не является простой. Эта цепь не будет и замкнутой, так как в ней есть повторяющееся ребро {v₃,v₄}.

Степени вершин графа следующие: dg(v₁) = dg(v₂) = 2, dg(v₃) = 3, dg(v₄) = dg(v₅) = dg(v₆) = 1, dg(v₇) = 0.

Вершины v₁,v₂,v₃,v₄ попарно достижимы (v_i*v_j, i, j ∈ {1,2,3,4} и образуют класс эквивалентности по отношению достижимости. Для вершин v₅ и v₆ имеет место v₅*v₆, и они также образуют класс эквивалентности. Заметим, что вершина v₇, по определению, образует цепь длины 0 и эквивалентна по отношению достижимости только самой себе.

Пример 5.2. Обратимся к ориентированному графу, изображенному на рис. 5.3. Он задается множеством вершин V = {v₁,v₂,v₃,v₄,v₅,v₆} и множеством дуг

E = {(v₁,v₂), (v₁,v₃), (v₂,v₁), (v₂,v₃),(v₂,v₄),(v₃,v₁),(v₃,v₄),(v₅,v₆),(v₆,v₄)}.

В этом ориентированном графе последовательность вершин v1,v2,v3,v4 есть простой путь, а последовательность вершин v1,v2,v3,v1,v3,v4 — путь, не являющийся простым, поскольку в нем, например, два раза встречается вершина v3, не служащая началом и концом пути.

Последовательность вершин v₃,v₁,v₂,v₃ есть контур, а последовательность v₃,v₁,v₂,v₁,v₃ — замкнутый путь, но не контур, поскольку вершина v₁, не являющаяся началом пути, встречается два раза. Последовательность вершин v₁,v₃,v₄,v₆ не задает путь, так как в рассматриваемом ориентированном графе нет дуги (v₄,v₆).

Полустепени захода, полустепени исхода и степени у вершин следующие: у v₁ и v₃ — dg  (v₁) = dg  (v₃) = 2, dg⁺(v₁) = = dg⁺(v₃) = 2, dg(v₁) = dg(v₃) = 4; у v₂ — dg  (v₂) = 1, dg⁺(v₂) = = 3, dg(v₂) = 4; у v₄ — dg  (v₄) = 3, dg⁺(v₄) = 0, dg(v₄) = 3; у v₅ — dg  (v₅) = 0, dg⁺(v₅) = 1, dg(v₅) = 1; у v₆ — dg  (v₆) = 1, dg⁺(v₆) = 1, dg(v₆) = 2.#

Отношение достижимости в неориентированных и ориентированных графах обладает следующим важным свойством.

Теорема 5.1. Для любой цепи, соединяющей две вершины неориентированного графа, существует простая цепь, соединяющая те же вершины. Для любого пути, ведущего из вершины u в вершину v ориентированного графа, существует простой путь, ведущий из u в v.

◀ Проведем доказательство для неориентированного графа (для ориентированного графа доказательство проводится аналогично).

Пусть вершины u и v неориентированного графа таковы, что u+v. Если эти вершины являются концами цепи нулевой длины, то утверждение теоремы тривиально. Пусть u+v, т.е. существует цепь ненулевой длины, соединяющая u и v. Рассмотрим какую-либо из таких цепей (рис. 5.4). Обозначим ее С. Если цепь С простая, то доказывать нечего. Пусть существует внутренняя (не совпадающая ни с одним из концов) вершина w цепи C, которая повторяется в этой цепи, т.е. u* w+ w* v. Это значит, что вершина w содержится в некоторой цепи С' ненулевой длины (подцепи цепи С) с совпадающими концами (рис. 5.5). Удалим все вершины и ребра цепи С', кроме вершины w (служащей ее началом и концом одновременно). После этого получим новую цепь C1, соединяющую вершиы u и v (рис. 5.6), в которой число повторений вершины w будет по крайней мере на единицу меньше, чем в цепи С. Если цепь С1 простая, то утверждение доказано. В противном случае поступаем с ней так же, как и с цепью С. В силу конечности множества вершин и ребер графа после конечного числа шагов получим простую цепь, соединяющую вершиы u и v. ▶

Следствие 5.1. Если вершина неориентированного графа содержится в некоторой замкнутой цепи, то она содержится и в некотором цикле. Если вершина ориентированного графа содержится в некотором замкнутом пути, то она содержится и в некотором контуре.

Замечание 5.3. Следствие 5.1 перестает быть верным для произвольной цепи с совпадающими концами. Например, для неориентированного графа, состоящего из двух вершин v₁, v₂ и единственного ребра (v₁, v₂) цепь v₁, v₂, v₁ с совпадающими концами не содержит цикла. #

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

Определение 5.1. Неориентированный (ориентированный) граф G₁ = (V₁, E₁) называют подграфом неориентированного (ориентированного) графа G = (V, E), если V₁ ⊆ V и Е₁ ⊆ Е.

Будем использовать обозначение G₁ ⊆ G, аналогичное обозначению включения для множеств.

Замечание 5.4. Так как в определении 5.1 пара G₁ = (V₁,E₁) есть неориентированный (ориентированный) граф, то для бого ребра {u, v} ∈ Е₁ (дуги (u, v) ∈ Е₁) предполагается, конечно, что u, v ∈ V₁, поскольку иначе пару (V₁, E₁) нельзя будет считать неориентированным (ориентированным) графом. #

Если хотя бы одно из указанных двух включений в определении 5.1 строгое, то G₁ называют собственным подграфом графа G; если V₁ = V, то G₁ называют остовным подграфом графа G.

Подграф G₁ неориентированного (ориентированного) графа G называют подграфом, порожденным множеством вершин V₁ ⊆ V, если каждое ребро (дуга) тогда и только тогда принадлежит Е₁ ⊆ Е, когда его (ее) концы принадлежат V₁. Часто в случае, если множество вершин V₁ подразумевается, говорят просто о порожденном подграфе.

Отметим, что подграф графа G, порожденный множеством вершин V₁, в отличие от произвольного подграфа графа G с множеством вершин V₁, должен включать все ребра (дуги), концы которых принадлежат множеству V₁.

Подграф G₁ ⊆ G называют максимальным подграфом, обладающим данным свойством Р, если он не является собственным подграфом никакого другого подграфа графа G, обладающего свойством Р.

Например, на рис. 5.7 подграфы G₁, G₁, G₁ являются максимальными ациклическими подграфами графа G. Отметим, что они также являются собственными и остовными подграфами указанного графа.

Следующее важное понятие снова введем параллельно для рассматриваемых двух видов графов.

Неориентированные графы	Ориентированные графы
Неориентированный граф называют связным, если любые две его вершины u и v соединены цепью (u*v).	Ориентированный граф называют связным, если для любых двух его вершин u, v вершина v достижима из вершины u или вершина и достижима из вершины v (u ⇒* v или v ⇒* u).
Компонента связности (или просто компонента) неориентированного графа — это его максимальный связный подграф.	Компонента связности (или просто компонента) ориентированного графа — это максимальный связный подграф.

В неориентированном графе две вершины, соединенные цепью, связаны отношением достижимости, которое является эквивалентностью. Поэтому компонента такого графа — это подграф, порожденный некоторым классом эквивалентности вершин по отношению достижимости.

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

Так как отношение достижимости в ориентированном графе не является эквивалентностью, то компоненты ориентированного графа могут пересекаться.

Пример 5.3. Граф, изображенный на рис. 5.2, не является связным. Он состоит из трех компонент. Эти компоненты порождены тремя классами эквивалентности по отношению достижимости, указанными в примере 5.1.

Связными являются все графы, изображенные на рис. 5.7. Ориентированный граф на рис. 5.8 связный, а ориентированные графы на рис. 5.3 и 5.9 не являются связными. В ориентированном графе на рис. 5.3 вершины v2 и v5 не достижимы одна из другой, а в ориентированном графе на рис. 5.9 взаимно не достижимы, например, вершины v2 и v6. В ориентированном графе, изображенном на рис. 5.9, имеются две компоненты связности: С1 и С2, которые пересекаются. #

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

Определение 5.2. Ориентированный граф называют сильно связным, если для любых двух его вершин u и v вершина v достижима из вершины и и вершина и достижима из вершины v (u ⇒* v и v ⇒* u). Бикомпонента ориентированного графа — это его максимальный сильно связный подграф.

Если u ⇒* v и v ⇒* u, то говорят, что u и v связаны отношением взаимной достижимости. Это бинарное отношение рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности. Следовательно, две различные бикомпоненты не пересекаются, т.е. не имеют ни общих вершин, ни общих ребер.

Пример 5.4. а. В ориентированном графе, изображенном на рис. 5.3, бикомпонентой является подграф G₁, порожденный множеством вершин {v₁,v₂,v₃}. Действительно, эти вершины взаимно достижимы, поэтому ориентированный граф G₁ сильно связный. Так как из вершин v₄,v₅,v₆ ни одна из вершин v₁,v₂,v₃ не достижима, то выделенный сильно связный подграф G₁ является максимальным.

б. В ориентированном графе, представленном на рис. 5.9, имеются четыре бикомпоненты В₁, В₂, В₃, В₄. Это подграфы, порожденные соответственно множествами вершин {v₁}, {v₂,v₃}, {v₄,v₅} и {v₆,v₇}. Отметим, что подграф, порожденный множеством {v₁}, не содержит ни одной дуги. Тем не менее этот подграф — бикомпонента, поскольку каждая вершина достижима сама из себя (по пути длины 0).

Определение 5.3. Неориентированный граф G₁ = (V₁, E₁) называют ассоциированным с ориентированном графом G = (V, E), если его множество вершин совпадает с множеством вершин ориентированного графа G, а пара {u, v} образует ребро тогда и только тогда, когда uv ≠ и из u в v или из v в г ведет дуга, т.е. V₁ = V и

E₁ = {{u,v}: (u, v) ∈ Е или (v, u) ∈ Е, u ≠ v}.

Таким образом, переход от ориентированного графа к ассоциированному с ним неориентированному графу состоит в „стирании" ориентации дуг ориентированного графа с учетом того, что все петли исчезают, а дуги (u, v) и (v, u) при u ≠ v переходят в одно и то же ребро {u, v}.

Для ориентированного графа, изображенного на рис. 5.10, а, ассоциированный с ним неориентированный граф приведен на рис. 5.10, б. Отметим, что дуги (v₁, v₂) и (v₂, v₁) переходят в ребро {v₁, v₂}> а петля (v₆, v₆) исчезает.

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

Ориентированные графы, представленные на рис. 5.3, 5.9 и 5.8, являются слабо связными. Ориентированный граф, изображенный на рис. 5.10, не является слабо связным, поскольку не является связным ассоциированный с ним неориентированный граф. Ориентированный граф на рис. 5.10, а имеет две компоненты слабой связности. Соответственно ассоциированный с ним неориентированный граф на рис. 5.10, б имеет две компоненты связности.