Теорема (критерий эйлеровости)

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

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

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

 

Если цикл заменить на произвольный путь, то это будет полугамильтоновый граф.

Сети.

Ориентированный граф G =(V,A) - пара множеств V и A, таких, что V - некоторое конечное непустое множество, а A - некоторое подмножество декартового квадрата V(AÍ V2 = V * V).

Вершины графа G - элементы множества B.

Дуги графа G - элементы множества A.

Дуга - упорядоченная пара вершин a=(u,v). Начало дуги - вершина u, конец дуги - вершина v. Дуга исходит из своего начала и заходит в свой конец.

Орграф G - орграф p-го порядка, если мощность множества |V|=p.

Полустепень захода вершины v графа G - число дуг, заходящих в вершину v:

deg- (v) = | X |; X = { x | x = (u,v) ÎA}.

 

Полустепень исхода вершины v графа G - число дуг, исходящих из вершины v:

deg+ (v) = | Y |; Y = { y | y = (v,u)Î A}.

 

Степень вершины v графа G - сумма полустепеней захода и исхода в вершине v:

deg (v) = deg+(v) + deg-(v).

Сеть - это некоторый нагруженный смешанный орграф, в котором выделены 2 вершины:

вершина S - это вершина с нулевой полустепенью захода является истоком графа,

вершина t - это вершина с нулевой полустепенью захода сток графа.

Каждой дуге (ij) орграфа G поставлено в соответствие некоторое число (положительное) bij, которое называется пропускной способностью дуги.

Под потоком в сети будем понимать xij, если выполняется следующее условие:

1. xij по дуге 0 ≤ xij ≤ bij.

2. Для каждого промежуточного узла i ≠ S ≠ t выполняется закон Кирхгофа, т. е. поток в промежуточном узле не теряется и не увеличивается.

∑kxki=∑jxij

 

Вычисление максимального потока через сеть, раскраска вершин и ребер графов;

Сети.

Ориентированный граф G =(V,A) - пара множеств V и A, таких, что V - некоторое конечное непустое множество, а A - некоторое подмножество декартового квадрата V(AÍ V2 = V * V).

Вершины графа G - элементы множества B.

Дуги графа G - элементы множества A.

Дуга - упорядоченная пара вершин a=(u,v). Начало дуги - вершина u, конец дуги - вершина v. Дуга исходит из своего начала и заходит в свой конец.

Орграф G - орграф p-го порядка, если мощность множества |V|=p.

Полустепень захода вершины v графа G - число дуг, заходящих в вершину v:

deg- (v) = | X |; X = { x | x = (u,v) ÎA}.

 

Полустепень исхода вершины v графа G - число дуг, исходящих из вершины v:

deg+ (v) = | Y |; Y = { y | y = (v,u)Î A}.

 

Степень вершины v графа G - сумма полустепеней захода и исхода в вершине v:

deg (v) = deg+(v) + deg-(v).

Сеть - это некоторый нагруженный смешанный орграф, в котором выделены 2 вершины:

вершина S - это вершина с нулевой полустепенью захода является истоком графа,

вершина t - это вершина с нулевой полустепенью захода сток графа.

Каждой дуге (ij) орграфа G поставлено в соответствие некоторое число (положительное) bij, которое называется пропускной способностью дуги.

Под потоком в сети будем понимать xij, если выполняется следующее условие:

1. xij по дуге 0 ≤ xij ≤ bij.

2. Для каждого промежуточного узла i ≠ S ≠ t выполняется закон Кирхгофа, т. е. поток в промежуточном узле не теряется и не увеличивается.

∑kxki=∑jxij

 

(сколько входит, столько выходит)

3. Величина потока, исходящая из источника является величиной потока, входящая в сток

∑kxki=∑xit

Величиной потока x называется

Задача о максимальном потоке заключается в определении потока максимальной величины1.

Разрезом W в сети называется любое множество вершин, обязательно содержащее выход и не содержащее вход. Пропускной способностью C (W) разреза W называется сумма пропускных способностей дуг, заходящих в разрез.

Известно, что величина любого потока не превышает пропускной способности любого разреза (теорема Форда-Фалкерсона).

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

Алгоритм 7 (алгоритм Форда-Фалкерсона). Применение алгоритма проиллюстрируем примером сети, приведенной на рисунке 3, в которой пропускные способности всех дуг равны единице.

Шаг 0. Берем произвольный поток (например, поток x01 = x12 = x25 = 1). Помечаем начальную вершину индексом «0».

Обозначим Z – множество помеченных вершин.

Общий шаг. Первое действие. Помечаем вершину j индексом + i, если, во-первых, существует дуга (i; j), и, во-вторых, i I Z, j I Z, xij < Cij.

Если в результате этого типа пометок мы пометили выход, то поток можно увеличить хотя бы на единицу (если cij – целые числа). Двигаясь обратно, можно найти путь, поток по которому можно увеличить. Однако, как видно из примера, этого недостаточно для нахождения максимального потока.

Второе действие. Помечаем вершину i индексом -j, если, во-первых, существует дуга (j; i), и, во-вторых, j I Z, i I Z, xij > 0 (легко видеть, что пометки первого типа увеличивают поток по

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

Рассмотрим цепь m = (0; 3; 2; 1; 4; 5), приведенную на рисунке 3. Полученные в результате второго действия потоки обозначены жирным шрифтом. Критерий остановки алгоритма следующий: если, применяя пометки обоих типов, вершину n пометить не удалось, то полученный поток имеет максимальную величину.

Раскраска графов.

граф G неориентированный и пусть k - натуральное число. Тогда k-раскраской графа G называется произвольная функция f, отображающая множество вершин графа G в некоторое k-элементное множество:

f: V→{a1, a2,..., ak} = A

В качестве элементов множества A чаще всего используется отрезок натурального ряда {1, 2,..., k} либо {a, b,..., n} или краски типа {синий, красный,:, черный}.

Раскраска называется правильной, если f(u) ≠ f(v) для любых смежных вершин u и v графа G.

Хроматическое число графа G - это минимальное число красок, при котором граф имеет правильную раскраску. Если хроматическое число равно k, то граф называется k-хроматическим (обозначают λ(G) = k).

Для полного графа Kn хроматическое число равно:

λ(Kn) = n,

Для пустого: λ(0n) = 1.

Раскраска ребер.

Пусть есть G = (V, E), где |V| = p, |E| = q. Тогда реберной k-раскраской называется некоторая функция j, задающая отображения множества E, т. е.

φ: E → A = {a1,..., ak}

Граф называется k-раскрашиваемым, если существует правильная раскраска ребер.

Минимальное число k, при котором существует правильная реберная k-раскраска называется реберным хроматическим числом или индексом.

Граф G называется реберно k-хроматическим, если хроматический индекс равен k.