Основные понятия теории графов

Граф – пара G(V, X), где V = V(G) – конечное непустое множество – множество вершин графа, X = X(G) – конечное множество неупорядоченных пар различных элементов из V –

множество ребер графа.

Элементы v V называются вершинами / узлами графа, элементы x v, w X , v, w V , – его ребрами. Вершины v и w при этом называются смежными, а ребро x и каждая из вершин из вершин v и w – инцидентными. Говорят, что ребро x соединяет вершины v и w, а v и w называются

концами ребра x.

Два ребра x, y X – смежные, если они инцидентны одной и той же вершине, т.е. x y . Из приведенных определений следует, что в графах любые две различные вершины могут

быть соединены не более чем одним ребром. Такие графы называют иногда простыми графами. Если V G p , X G q , то граф G называется (p, q)-графом.

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

Ребра, соединяющие одну и ту же пару вершин, называется кратными ребрами. Их обозначают x = {v, w, n}, v и w – различные вершины графа, а n – номер одного из кратных ребер.

Мультиграф – граф, в котором допускаются кратные ребра.

Ребро, концы которого совпадают, называется петлей. Обозначение – стандартное – x={v,v}. Псевдограф – граф, в котором допускаются петли.

В самом общем случае могут присутствовать и кратные ребра, и кратные петли.

Подграфы. Дополнения

Пусть даны два графа G = (V, X) и H = (W, Y).

Граф H называется подграфом графа G, если W V &Y X , G при этом называется надграфом графа H. Данный факт обозначается: H G .

Графы G и H считаем равными (G = H) если V = W & X = Y, т.е. G H & H G . Подграф H графа G называется остовным подграфом / суграфом, если W = V.

Пусть S V . Подграф, порожденный множеством S, или просто порожденный подграфом

S , – максимальный (в смысле ) подграф графа G с множеством вершин S.

Граф G называется пустым или нуль-графом, если X . Обозначение 0p, 0(V) ( p V ).

Граф G называется полным, если v, w V : v, w X , т.е. любые две вершины смежны.

Обозначение: Kp, K(V)

Пусть G1 = (V, X1) и G2 = (V, X2) – остовные подграфы графа G = (V, X). Тогда граф G2 называется дополнением графа G1 в графе G, если X2 = X \ X1, т.е. дополнение графа G1 в G – это остовной подграф графа G, который содержит те и только те ребра графа G, которые не содержатся в G1.

Дополнение G = (V, X) в K(V) называется просто дополнением графа G, обозначается G . Две вершины в G смежны тогда и только тогда, когда они не смежны в G.

Очевидно G G , K V 0 V и 0 V K V .

Степени вершин

Степень вершины v графа G – число инцидентных ей ребер. Обозначается d(G, v), d(v). Для псевдографов обычно каждая петля в рассматриваемой вершине учитывается дважды. Если d(v) = 0, то вершина называется изолированной.

1

Вершина v, для которой d(v) = 1, называется висячей или концевой.

Граф G называется однородным / регулярным, если все его вершины имеют одинаковую степень d(G), называемую степенью графа. Очевидно, 0n и Kn – однородные и d(0n)=0; d(Kn)=n –1.

Дополнение регулярного графа также является регулярным графом и d G V 1 d G . Теорема 1. В любом графе сумма степеней всех вершин равна удвоенному числу ребер:

G V , X : d v 2 X .

v V

Для однородного графа V d G 2 X .

Следствие. В любом графе G = (V, X) число вершин с нечетными степенями четно.

Пусть G = (V, X) – граф с p вершинами; d1, d2, …, dp – степени его вершин, d1 ≤ d2 ≤ … ≤ dp.

Вектор степеней графа G – кортеж dG = (d1, d2, …, dp).

Если граф G – однородный степени m, то вместо dG = (m, …, m) пишем dG = d(G) = m. Минимальная и максимальная из степеней вершин графа обозначают соответственно δ(G) и

Δ(G). Очевидно, для однородных графов Δ(G) = δ(G) = d(G).

Ориентированные графы

Ориентированный граф / орграф – называется пара G = (V, Г), где V – конечное непустое множество вершин, Г – конечное множество упорядоченных пар различных вершин, т.е. V 2 .

v, w – дуга орграфа G. В этом случае говорят, что дуга γ исходит из вершины v и

заходит в вершину w. Вершина v называется началом дуги γ (v=Пр1 γ), а w – ее концом (w =Пр2 γ).

Дуги α и γ графа G называют симметричными, если v, w V : v, w & w, v .

Симметричный орграф – орграф G, в котором vi , v j		V : ij ji .
Орграф называется направленным / антисимметричным, если в нем нет симметричных пар дуг.
Симметризация орграфа G = (V, Γ)	– операция,	при	которой орграфу G ставится в
~	~		~
соответствие симметричный орграф G	V , , в котором		v, w : v, w w, v .

~

Орграф G при этом называется симметризованным орграфом G.

Любой симметричный орграф можно понимать как простой орграф, каждое ребро которого соответствует паре симметричных дуг с теми же концами, т.е. {v, w} = {(v, w), (w, v)}, и каждый простой граф можно понимать как соответствующий симметричный орграф.

~	V , X , полученный симметризацией G.
Основанием орграфа G = (V, Γ) называется граф G
Пусть G = (V, Г) – произвольный орграф, v V .

Полустепень исхода вершины v – число дуг, исходящих из нее: d v					: v Пр						.
						1
Полустепень захода вершины v – число дуг, заходящих в нее:	d v		: v Пр			2			.

Степень d(v) вершины v орграфа G – сумма её полустепеней исхода и захода d(v) = d+(v) + d–(v). Теорема 2. В любом орграфе G = (V, Γ) сумма полустепеней исхода всех вершин равна

сумме их полустепеней захода: G V , : d v d v .

v V v V

Отношения и графы. Отображения, индуцируемые графами

Пусть G = (V, Γ) – орграф. V 2 , а, значит, является бинарным отношением на V. Отображение :V V , индуцируемое орграфом G, определяется так: v V : v w V : v,w . И наоборот: для отображения f :V V его графом называется орграф Gf = (V, Γ), где

v, w : v V & w f v . При этом w является образом вершины v, а v – прообразом w.

2

Маршруты в графах

Неориентированные графы

Маршрут в графе G = (V, X) – такая чередующая последовательность вершин и ребер, начинающаяся и оканчивающаяся вершинами, что каждое ребро в ней инцидентно предыдущей и последующей вершинам. Обозначение: μ = (v1, x1, v2, …, vi, xi, vi+1, …, vn). v1 и vn, при этом называются концами маршрута μ, который называется также (v1 – vn)-маршрутом.

Можно использовать сокращенную формой записи маршрута, указывая только вершины: (v1, v2, …, vn) или только ребра: (x1, x2, …, xn–1).

Маршрут, концы которого совпадают, называется замкнутым, иначе – разомкнутым. Длина маршрута – число ребер в нем. Обозначение: X .

Цепь – маршрут, в котором все ребра разные.

Простая цепь – маршрут, в котором все вершины (а следовательно, и ребра) разные. Цикл – замкнутая цепь.

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

Длина любой простой цепи не превосходит p – 1 ( p V G ), длина любого простого цикла

не превосходит числа р. Следовательно, числа простых цепей и простых циклов в графе конечны. Расстояние между вершинами v и w – наименьшая из длин простых (v – w)-цепей.

Обозначается: ρ(v, w).

Если μ1 и μ2 – маршруты, причем μ2 является подпоследовательностью μ1, то μ2 называется

подмаршрутом маршрута μ1.

Если μ1 – (v – u)-маршрут, а μ2 – (u – w)-маршрут, то сцепкой μ1 и μ2 называется маршрут

μ = (v, …, u, …, w) = v μ1 u μ2 w = μ1μ2.

Лемма 1. Из любого (v – w)-маршрута графа можно выделить простую (v – w) -цепь. Лемма 2. Кратчайший (v – w)-маршрут (v ≠ w) является простой цепью.

Лемма 3. Из любого цикла графа G можно выделить простой цикл.

Лемма 4. Любой цикл графа можно представить как объединение ребернонепересекающихся (т.е. не имеющих общих ребер) простых циклов.

Лемма 5. Любой замкнутый маршрут графа нечетной длины содержит простой цикл нечетной длины.

Ориентированные графы

Путь в орграфе G = (V, Γ) – такая чередующаяся последовательность вершин и дуг, начинающаяся и оканчивающаяся вершинами, что любая дуга в ней исходит из предшествующей вершины и заходит в последующую вершину, т.е. если v1 , 1 , v2 , , vi , i , vi 1 , , vn – путь, то

i 1, n 1: Пр1 i vi & Пр2 i vi 1 .

Этот путь μ называют (v1 – vn)-путем. Он соединяет вершину v1 с вершиной vn, но не vn с v1.

Вершина v1 называется началом пути, а vn – концом пути.

Длина пути – число дуг в нем, обозначается .

Простой путь – путь, в котором все дуги в нем разные Элементарный путь – путь, в котором все вершины разные. Контур – замкнутый путь.

Простой контур – контур, в котором все дуги разные.

Элементарным контур – контур, в котором все вершины, кроме крайних, разные. Справедливы леммы, аналогичные леммам 1 – 5.

3

Связность. Компоненты

Граф G называется связным, если для v, w V простая (v – w)-цепь.

Теорема 3. Граф G = (V, X) связный тогда и только тогда, когда существует маршрут,

содержащий (проходящий через) все вершины графа.

Компонентой связности графа G (или просто компонентой) называется максимальный (в

смысле ) связный подграф этого графа.

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

совпадающую с G.

Теорема 4. Граф G = (V, X)

связный

тогда и только тогда,

когда для

любого разбиения

{V1, V2} множества V на два подмножества существует ребро, соединяющее некоторую вершину

из V1 с некоторой вершиной V2.

Доказательство. Достаточность ( ). Докажем связность графа.

Выберем две произвольные вершины v, w V .

Рассмотрим разбиение V 0

,V 0

, где V 0

v , V

0 V \ V 0 .

1

2

1

2

1

По условию теоремы существует ребро x 0 v, v

, где v

V

0 .

Построим новое разбиение V 1 ,V 1 ,

1

1

2

где V 1 v, v , V 1 V \ V 1 и найдём новое ребро

1

2

1

1

2

1

x 1

v, v

x 1 v , v

. Здесь

v

2

V 1 .

2

1

2

2

V k

,V k . В соответствие с описанной процедурой

Пусть построено разбиение k-го шага

1

2

V k 1

,V k 1 , где

переходим к

новому

разбиению

(k + 1)-го

шага

V k 1 V k v

k 1

,

1

2

1

1

V k 1 V \ V k 1

. Здесь

v

k 1

V k

и vk+1 смежна некоторой вершине из V k .

2

1

2

1

Будем продолжать этот процесс построения новых разбиений до тех пор, когда на некотором s-м шаге будет выполнено условие vs+1 = w ( w V1 s 1 ).

Это условие обязательно будет выполнено через конечное число шагов, так как k V1 k является собственным подмножеством V1 k 1 и множество вершин V конечно.

Заметим также, что на каждом k-м шаге любые две				вершины множества V k	можно
				1
соединить маршрутом. Отсюда следует, что условие w V s 1				означает наличие в графе G (v – w)-
	1
маршрута. В силу произвольности вершин v, w справедлив вывод о связности графа G.					■
Доказательство теоремы 3.2 конструктивно и позволяет построить алгоритм проверки
возможности соединения любых двух вершин графа.
Теорема 5.	Если граф G несвязный, то G – связный граф.
Теорема 6.	В связном графе любые две длиннейшие простые цепи имеют общую вершину.
Теорема 7.	Удаление ребра, принадлежащего циклу графа G, не нарушает связности графа.

В случае ориентированных графов G = (V, Γ) вводится три понятия связности:

~

орграф G – связный / слабо связный / слабый, если связно его основание G ;

–односторонне связный, если v, w V v w путь w v путь ;

–сильно связный / бисвязный / сильный, если v,w V v w путь& w v путь .

Всоответствие с этими определениями вводятся понятия компонент орграфа:

сильная компонента – максимальный сильно связный подграф;

односторонняя компонента – максимальный односторонне связный подграф;

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

4