Задача о максимальном потоке.

Предварительно рассмотрим простую задачу. Пусть трубопровод состоит из трех труб различного сечения с пропускными способностями 10 л/мин, 5 л/мин, 7 л/мин.

Вполне очевидно, что пропускная способность системы равна 5 л/мин, т.е. совпадает с наименьшей пропускной способностью труб.

 

                                    10 л/мин 5 л/мин    7 л/мин               

 

 

Рис. 26 Трубопровод.

 

Пусть имеется некоторый взвешенный орграф G(V,E). Выделим в этом графе некоторые две вершины s, t, которые назовем источником и стоком. Будем рассматривать веса как пропускную способность дуги  q . Количество фактически проходящих единиц по дуге обозначим через z . z  - поток, проходящий через дугу ij. Ясно, что q z .

Пусть к источнику S прибывает поток Р. Для того, чтобы сеть функционировала нормально, должно быть Р = Р , Р - Р =0. Требуется организовать перемещение так, чтобы величина Р была максимальной.

Разделим множество вершин на подмножества Х  и Х . Рассмотрим дугу (V V ) и отнесем вершину V  к х , а V  к х . Таким образом, для данного разбиения (х ,х ) концы дуг принадлежат разным подмножествам. Такое разбиение называется разрезом, отделяющим вершину V  от V .

 Совокупность потоков, протекающих через х х , называется потоком разреза.

Теорема Форда – Фолкерсона.

Теорема. Максимальный поток сети равен минимальному потоку разреза.

Доказательство:

Так как максимальный поток обязательно пройдет по дуге минимального разреза, то это будет означать, что он совпадает с минимальным потоком разреза. Это будет выполняться, если выполняется условия: Р =P_t, т.е. Р_s - Р_t=0.

 Предположим, что пропускные способности дуг выражаются целыми числами.

. Будем последовательно строить разрезы, и назначать каждой вершине некоторое число – метку r по следующему правилу.

r = min(r , q _ij - z ), если z   ≤. q  и дуга исходит из вершины V , и  r = z , при z >0, если душа заходит в V  .

Для определенности в метку будем включать указатель вершины, из которой мы пришли в вершину V , то есть метка будет выглядеть: +V ,r  - если V  - вершина исхода; и -V , r  , если V  - вершина захода.

Будем строить разрезы.

Включаем в разрез источник - вершину V1 , присвоив ей метку

 r = ∞, и положив все потоки z = 0.

Просматриваем все смежные вершины, идущие в прямом направлении Γ+. Если им не присвоены метки, то присваиваем их r =min(r ,q -z ) (1)

Тем самым включаем эти вершины в подмножество Х1.

Просматриваем все смежные вершины, идущие в обратном направлении Γ-. Если им не присвоены метки, то присваиваем их

 r = z >0 (2).

Тем самым включаем эти вершины в подмножество Х1.

Проделаем это со следующей вершиной и со следующей, пока не дойдем до вершины t.

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

Для дуг, идущих в прямом направлении найдем

  в1 = min(q _ij - z ).

Для дуг, идущих в обратном направлении найдем в2 = min z >0.  

 Найдем в = min(в1, в2). Используя метки, строим цепь, связывающую сток с источником. Такие цепи называются аугментальными. Для дуг в прямом направлении к имеющимся потокам прибавим величину в, и вычтем в из потоков в обратном направлении.

После этого стираем все метки и строим новые разрезы с новыми потоками.

2). Вершина t не попала в Х₁. это значит, что для дуг в прямом направлении имеем q _ij = z , а для дуг в обратном направлении

 z .=0. Иначе говор, величина потока равна значению разреза, который и будет минимальным.

Т.к. пропускные способности дуг выражаются целыми числами, то в случае 1). Мы увеличивали поток на некоторое целое число, значит рано или поздно получим максимальный поток. Это наступит тогда, когда не останется аугментальных цепей.

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

Пример. Граф задается матрицей смежности (пропускных способностей).

	V1	V2	V3	V4	V5	V6	V7	V8	V9	V10
V1		10	17
V2				13		23
V3				11
V4					5
V5			19				11
V6					14		10	21
V7									8	11
V8							17
V9										23
V10								15

 

                V2              V6               V8                   V10

               ●                                                                             

                                                                         

V1 ●               V4

   

               ●                                        ●                       ●

               V3              V5               V7                        V9

Рис. 27. Пример сети с 10 вершинами.

 

Вершина V1 - источник, вершина V10 - сток. Строим разрезы.

Вершине V1 присваиваем метку r1= ∞, положив все потоки

 z = 0.

Просматриваем вершину V1.

Γ+ (V1) = {V2 , V3}.

Присваиваем вершине V2 метку + V1, r2= min(r1,q12-z12) = min(∞, 10 -0) =10. Метка V 2: + V 1, r 2 = 10.

Присваиваем вершине V3 метку + V1, r3= min(r1,q13-z13) = min(∞, 17 -0) =17. Метка V 3: + V 1, r 3 = 17.

Γ- (V1) – пусто.

Вершина V1 помечена и просмотрена.

Просматриваем вершину V2.

Γ+ (V2) = {V4 , V6}.

Присваиваем вершине V4 метку + V2, r4= min(r2,q24-z24) = min(10, 13 -0) =10. Метка V 4: + V 2, r 4 = 10.

Присваиваем вершине V6 метку + V2, r6= min(r2,q26-z26) = min(10, 23 -0) =10. Метка V 6: + V 2, r 6 = 10.

Γ- (V2) = {V1}. Но V1 помечена.

Вершина V2 помечена и просмотрена.

Просматриваем вершину V3.

Γ+ (V3) = {V4}. Но V4 помечена.

Γ- (V3) = {V1 , V5}. Но V1 помечена, а z53 = 0..

Вершина V3 помечена и просмотрена.

Просматриваем вершину V4.

Γ+ (V4) = {V5}.

Присваиваем вершине V5 метку + V4, r5= min(r4,q45-z45) = min(10, 5 -0) = 5. Метка V 5: + V 4, r 5 = 5.

Γ- (V4) – {V2 , V3}. Но V2 помечена, и V3 помечена.

Вершина V4 помечена и просмотрена.

Просматриваем вершину V5.

Γ+ (V5) = {V7 , V3}.

Присваиваем вершине V7 метку + V5, r7= min(r5,q57-z57) = min(5, 11 -0) = 5. Метка V 7: + V 5, r 7 = 5.

Вершина V3 помечена. 

Γ- (V5) – {V4 , V6}. Но V4 и V6помечены.

Вершина V5 помечена и просмотрена.

Просматриваем вершину V6.

Γ+ (V6) = {V5 , V7 , V8}. Но V5 и V7 помечены. Присваиваем вершине V8 метку + V6, r8= min(r6,q68-z168) = min(10, 21 -0) =10. Метка V 8: + V 6, r 8 = 10.

Γ- (V6) = {V2}. Но V2 помечена

Вершина V6 помечена и просмотрена.

Просматриваем вершину V7.

Γ+ (V7) = {V₉, V10}.

Присваиваем вершине V9 метку + V7, r9= min(r7,q79-z79) = min(5, 8 -0) =5. Метка V 9: + V 7, r 9 = 5.

Присваиваем вершине V10 метку + V7, r10= min(r7,q710- z710) = min(5, 11 - 0) =5. Метка V 10: + V 7, r 10 = 5

Γ- (V7) – {V5 , V6 V8}. Но они помечены.

Вершина V7 помечена и просмотрена.

Все вершины помечены. Получили цепь V10, V7, V5, V4, V2,V1

 Назначим новые потоки, учитывая, что в = 5.

Метка V10: + V7, r10=   5. Значит поток z710 = 0+5 =5.

Метка V7: + V5, r7= 5. Значит поток z57 = 0+5 =5.

Метка V5: + V4, r5= 5. Значит поток z45 = 0+5 =5..

Метка V4: + V2, r4= 10. Значит поток z24 = 0+5 =5.

Метка V2: + V1, r2= 10. Значит поток z12 = 0+5 =5.

Остальные потоки равны 0.

Стираем все метки и начинаем с начала строить разрезы с новыми потоками.

Вершине V1 присваиваем метку r1= ∞.

 Просматриваем вершину V1.

Γ+ (V1) = {V2 , V3}.

Присваиваем вершине V2 метку + V1, r2= min(r1,q12-z12) = min(∞, 10 -5) =5. Метка V 2: + V 1, r 2 = 5.

Присваиваем вершине V3 метку + V1, r3= min(r1,q13-z13) = min(∞, 17 -0) =17. Метка V 3: + V 1, r 3 = 17.

Γ- (V1) – пусто.

Вершина V1 помечена и просмотрена.

Просматриваем вершину V2.

Γ+ (V2) = {V4 , V6}.

Присваиваем вершине V4 метку + V2, r4= min(r2,q24-z24) = min(5, 13 -5) =5. Метка V 4: + V 2, r 4 = 5.

.Присваиваем вершине V6 метку + V2, r6= min(r2,q26-z26) = min(5, 23 -0) =5. Метка V 6: + V 2, r 6 = 5.

Γ- (V2) = {V1}. Но V1 помечена.

Вершина V2 помечена и просмотрена.

Просматриваем вершину V3.

Γ+ (V3) = {V4}. Но V4 помечена.

Γ- (V3) = {V1 , V5}. Но V1 помечена, а z53 = 0..

Вершина V3 помечена и просмотрена.

Просматриваем вершину   V4.

Γ+ (V4) = {V5}.

Присваиваем вершине V5 метку + V4, r5= min(r4,q45-z45) = min(5, 5 -5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V4) – {V2 , V3}. Но V2 помечена, и V3 помечена.

Вершина V4 помечена и просмотрена.

Т.к. вершина V5 не помечена, то её пока не просматриваем

Просматриваем вершину V6.

Γ+ (V6) = {V5 , V7 , V8}.

. Присваиваем вершине V5 метку + V6, r5= min(r6,q65-z65) = min(5, 14 - 0) = 5. Метка V 5: + V 6, r 5 = 5.

.Присваиваем вершине V7 метку + V6, r7= min(r6,q67-z67) = min(5, 10-0) = 5 Метка V7: + V6, r7= 5.

Присваиваем вершине V8 метку + V6, r8= min(r6,q68-z168) = min(5, 21 -0) =5. Метка V 8: + V 6, r 8 = 5.

Γ- (V6) = {V2}. Но V2 помечена.

Вершина V6 помечена и просмотрена.

Просматриваем вершину V5.

Γ+ (V5) = {V7 , V3}. Но V3 и V7 помечены.

 Γ- (V5) – {V4 , V6}. Но V4 и V6помечены

Вершина V5 помечена и просмотрена.

Просматриваем вершину V7.

Γ+ (V7) = {V₉, V10}.  

Присваиваем вершине V9 метку + V7, r9= min(r7,q79-z79) = min(5, 8 -0) =5. Метка V 9: + V 7, r 9 = 5.

Присваиваем вершине V10 метку + V7, r10= min(r7,q710- z710)= = min(5, 11 - -5) =5.

Все вершины помечены.

Все вершины помечены

. Получили цепь V10, V7, V6, V2, V1

 Назначим новые потоки, учитывая, что в = 5.

Метка V10: + V7, r10= 5. Значит поток z710 =5+5 =10.

Метка V7: + V6, r7= 5... Значит поток z67 =0+5 =5.

Метка V6: + V2, r5= 5. Значит поток z26 =0+5 =5..

Метка V2: + V1, r2= 10. Значит поток z12 =5+5 = 105.

Потоки имеют вид 

 

                    V2   5       V6              V8                    V10

                      ●                 ●                ●                      ●

         10         5

 

V1 ●                     ●V4                       5                    100

                                       5

                                        

                    ●                    ●               ●                       ●

                    V3                  V5             V7                     V10

                                                                                                        

                                                                          

Рис. 28. Распределение потоков после второй итерации.

 

Стираем все метки и начинаем с начала строить разрезы с новыми потоками.

Вершине V1 присваиваем метку r1= ∞.

 Просматриваем вершину V1.

Γ+ (V1) = {V2 , V3}.

Присваиваем вершине V2 метку + V1, r2= min(r1,q12-z12) = min(∞,10 - 105) =0. значит, вершине V2 метка не присваивается.

Присваиваем вершине V3 метку + V1, r3= min(r1,q13-z13) = min(∞, 17 -10) =1. Метка V 3: + V 1, r 3 = 17.

Γ- (V1) – пусто.

Вершина V1 помечена и просмотрена.

Т.к. вершина V2 не помечена, то её пока не просматриваем

Просматриваем вершину V3.

Γ+ (V3) = {V4}. 

Присваиваем вершине V4 метку + V3, r4= min(r₄,q34-z34) = min(17,11 - 0) = 11. Метка V4: + V3, r4= 11. 

Γ- (V3) = {V1 , V5}. Но V1 помечена, а z53 = 0..

Вершина V3 помечена и просмотрена.

Просматриваем вершину V4.

Γ+ (V4) = {V5}.

Присваиваем вершине V5 метку + V4, r5= min(r4,q45-z45) = min(11, 5 -5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V4) – {V2 , V3}. Но V3 помечена.

Присваиваем вершине V2 метку - V4, r2= z24 = 5.

Метка V 2: - V 4, r 2 = 5.

Вершина V4 помечена и просмотрена.

Просматриваем вершину V2.

Γ+ (V2) = {V4 , V6}.

Но V4 помечена.

.Присваиваем вершине V6 метку + V2, r6= min(r2,q26-z26) =

= min(5, 23 -5) =5. Метка V 6: + V 2, r 6 = 5.

Γ- (V2) = {V1}. Но V1 помечена.

Вершина V2 помечена и просмотрена.

Т.к. вершина V5 не помечена, то её пока не просматриваем.

Просматриваем вершину V6.

Γ+ (V6) = {V5 , V7 , V8}.

. Присваиваем вершине V5 метку + V6, r5= min(r6,q65-z65) = min(5, 14 - 5) = 5.

Метка V 5: + V 6, r 5 = 5.

.Присваиваем вершине V7 метку + V6, r7=  min(r6,q67-z67) = min(5, 10-5) = 5. Метка V 7: + V 6, r 7 = 5.

Присваиваем вершине V8 метку + V6, r8= min(r6,q68-z168) = min(5, 21 -0) =5. Метка V8: + V6, r8= 5.

Γ- (V6) = {V2}. Но V2 помечена.

Вершина V6 помечена и просмотрена.

Просматриваем вершину V5.

Γ+ (V5) = {V7 , V3}. Но V3 и V7 помечены.

 Γ- (V5) = {V4 , V6}. Но V4 и V6помечены

Вершина V5 помечена и просмотрена.

Просматриваем вершину V7.

Γ+ (V7) = {V₉, V10}.  

Присваиваем вершине V9 метку + V7, r9=  min(r7,q79-z79) = min(5, 8 -0) =5. Метка V 9: + V 7, r 9 = 5.

Присваиваем вершине V10 метку + V7, r10= min(r7,q710- z710) = min(5,11-10) =1.

Γ- (V7) = {V5 , V6}. Но V4 и V6помечены

Все вершины помечены. Получили цепьV10, V7, V6, V2, V4, V3, V1.  Имеем в₁ = 1, в₂ = 5. Тогда в = min (в₁, в₂) =1.                                  

 Назначим новые потоки, учитывая, что в = 1.

Метка V10: + V7, r10= 5. Значит поток z710 =10+1 =11.

Метка V7: + V6, r7= 5. Значит поток z67 =5 + 1 =6.

Метка V6: + V2, r5= 5. Значит поток z26 =5 +1 = 6..

Метка V2: - V4, r2= 5. Значит поток z24 =5-1= 4.

Метка V4: + V3, r4= 11. Значит поток z34 =0 + 1 =1.

Метка V3: + V1, r3= 17. Значит поток z13 =0 +1 = 1..

Потоки имеют вид

                                        V6 

     V2             6                               V8                        V10

  10                                         6                             

V₁                4

 

1                 V₄   5                                             11

.                     1                          5

       V3                   V5                   V7                           V9

                                                                                

 

Рис. 29 Распределение потоков после третьей итерации

 

Стираем все метки и начинаем с начала строить разрезы с новыми потоками.

Вершине V1 присваиваем метку r1= ∞.

 Просматриваем вершину V1.

Γ+ (V1) = {V2 , V3}.

Присваиваем вершине V2 метку + V1, r2= min(r1,q12-z12) = min(∞,10 - 10) =0. Значит, вершине V2 метка не присваивается.

Присваиваем вершине V3 метку + V1, r3= min(r1,q13-z13) = min(∞, 17 -1) =16 Метка V 3: + V 1, r 3 = 16

Γ- (V1) – пусто.

Вершина V1 помечена и просмотрена.

Т.к. вершина V2 не помечена, то её пока не просматриваем

Просматриваем вершину V3.

Γ+ (V3) = {V4}. 

Присваиваем вершине V4 метку + V3, r4= min(r₄,q34-z34) = min(17,11 - 1) = 10   Метка V 4: + V 3, r 4 = 10  

Γ- (V3) = {V1 , V5}. Но V1 помечена, а z53 = 0..

Вершина V3 помечена и просмотрена.

Просматриваем вершину V4.

Γ+ (V4) = {V5}.

Присваиваем вершине V5 метку + V4, r5= min(r4,q45-z45) = min(11, 5 -5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V4) ={V2 , V3}. Но V3 помечена.

Присваиваем вершине V2 метку - V4, r2= z24 = 4

Метка V 2: - V 4, r 2 = 4

Вершина V4 помечена и просмотрена.

Просматриваем вершину V2.

Γ+ (V2) = {V4 , V6}.

Но V4 помечена.

.Присваиваем вершине V6 метку + V2, r6= min(r2,q26-z26) =

= min(4,23 -6) =4 Метка V 6: + V 2, r 6 = 4.

Γ- (V2) = {V1}. Но V1 помечена.

Вершина V2 помечена и просмотрена.

Т.к. вершина V5 не помечена, то её пока не просматриваем.

Просматриваем вершину V6.

Γ+ (V6) = {V5 , V7 , V8}.

. Присваиваем вершине V5 метку + V6, r5= min(r6,q65-z65) = =min(6 14 - 6) = 6. Метка V 5: + V 6, r 5 = 6

.Присваиваем вершине V7 метку + V6, r7= min(r6,q67-z67) =

- min(6 10-6) = 4 Метка V 7: + V 6, r 7 = 4.

Присваиваем вершине V8 метку + V6, r8= min(r6,q68-z168) = min(6, 21 -0) =6. Метка V 8: + V 6, r 8 = 6.

Γ- (V6) = {V2}. Но V2 помечена.

Вершина V6 помечена и просмотрена.

Просматриваем вершину V5.

Γ+ (V5) = {V7 , V3}. Но V3 и V7 помечены.

 Γ- (V5) = {V4 , V6}. Но V4 и V6помечены

Вершина V5 помечена и просмотрена.

Просматриваем вершину V7.

Γ+ (V7) = {V₉, V10}.  

Присваиваем вершине V9 метку + V7, r9= min(r7,q79-z79) = min(4, 8 -0) =4. Метка V 9: + V 7, r 9 = 4.

Присваиваем вершине V10 метку + V7, r10= min(r7,q710- z710) = min(4,11-11) =0, значит, вершине V10 метка не присваивается.

Γ- (V7) = {V5 , V₈, V6}. Но V5 , V₈ и V6помечены.

Вершина V7 помечена и просмотрена.

Просматриваем вершину V8.

Γ+ (V8) = {V₇} Вершина V7 помечена.

 

Γ- (V8) = {V6 , V10}. Но V6п. помечен, а. z10 8 = 0.

Вершина V8 помечена и просмотрена.

Просматриваем вершину V9.

Γ+ (V9) = {V₁₀}.

Присваиваем вершине V10 метку + V9, r10= min(r9,q910- z910) = min(4,23-0) =4, Метка V 10: + V 9, r 10 = 4.

Все вершины помечены. Получили цепь V10, V9,V7, V6, V2, V4, V3, V1.

 Имеем в₁ = 4, в₂ =4 5. Тогда в = min (в₁, в₂) =4.                                  

 Назначим новые потоки, учитывая, что в = 4.

 Метка V10: + V9, r10= 4. Значит поток z910 =0+4 =4.

 Метка V9: + V7, r9= 4. Значит поток z79 =0 + 4 = 4.

Метка V7: + V6, r7= 5. Значит поток z67 =6 +4 =10

Метка V6: + V2, r5= 5. Значит поток z26 =6 + 4 = 10..

Метка V2: - V4, r2= 5. Значит поток z24 =4 – 4 =0.

Метка V4: + V3, r4= 11. Значит поток z34 =1 + 4 = 5..

Метка V3: + V1, r3= 17. Значит поток z13 =1 +4 = 5.

Потоки имеют вид

                V2   10  V6                       V8                      V10

                                        

10                                                                                

V1                                   

                                                           10                  11             4

5                     5      V4     

 

                 V3        5  

                                      V₅            5      V7   4           V9 

                                                                                    

Рис. 30 Распределение потоков после четвертой итерации

 

Стираем все метки и начинаем с начала строить разрезы с новыми потоками.

Вершине V1 присваиваем метку r1= ∞.

 Просматриваем вершину V1.

Γ+ (V1) = {V2 , V3}.

Присваиваем вершине V2 метку + V1, r2= min(r1,q12-z12) = min(∞,10 - 105) =0. значит, вершине V2 метка не присваивается.

Присваиваем вершине V3 метку + V1, r3= min(r1,q13-z13) = min(∞, 17 -5) =12 

Метка V 3: + V 1, r 3 = 12

Γ- (V1) – пусто.

Вершина V1 помечена и просмотрена.

Т.к. вершина V2 не помечена, то её пока не просматриваем

Просматриваем вершину V3.

Γ+ (V3) = {V4}. 

Присваиваем вершине V4 метку + V3, r4= min(r₄,q34-z34) = min(12,11 - 5) = 6

Метка V 4: + V 3, r 4 = 6

Γ- (V3) = {V1 , V5}. Но V1 помечена, а z53 = 0..

Вершина V3 помечена и просмотрена.

Просматриваем вершину V4.

Γ+ (V4) = {V5}.

Присваиваем вершине V5 метку + V4, r5= min(r4,q45-z45) = min(11, 5 -5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V4) ={V2 , V3}. Но V3 помечена, а. z24 = 0

Вершина V4 помечена и просмотрена.

.Дальнейшая расстановка меток невозможна, значит, полученный поток является оптимальным. Он равен 15.

Связность в графах.

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

 

 

Рис. 31. G = G₁ U G_2, k =2.

 

                                        ●

 

Рис. 32. Несвязный граф, k=3.

 

 

Теорема. Пусть имеется три инварианта: р, q и k. Тогда

.

Доказательство по индукции:

1) Докажем, что р- k q        (1)

 а). Пусть р=1; q=0; тогда р-k=1-1=0 - верно.

 б). Пусть р=2; При k=2, получим: р-k=0, q=0. При k=1:

 р-k=1.Слдовательно, неравенство (1) справедливо.

 в). Пусть неравенство (1) справедливо для некоторого р. Покажем, что оно справедливо и для р = р+1, то есть мы должны показать, что справедливо р -k q (2), где q  - количество ребер, получившихся после добавления вершины, а k  - число компонент нового графа.

В самом деле:                

При р  = р+ 1, k =k+1 и q = q получим р - k = р + 1- k-1 = р- k  (в силу неравенства (1)). q = q . 

Если же при р  = р+ 1 имеем q =q+n (n 1) и k =k, то р -k =р+1-k (в силу неравенства (1)). q+1 q+n=q . Неравенство (2) доказано.

2) Докажем, что q  (3)

а). Пусть р=1; q=0; k=1. Тогда =0=q.

Пусть неравенство (3) справедливо для некоторого р. Докажем, что оно справедливо и для р =р+1, т.е.

q (4)

 б). Пусть р = р+1; q =q и k =k+1. (*) Тогда =  = = q =q

в). Пусть р =р+1; q =q+1 и k =k. Тогда

                        = = подставляя (*)

 

и раскрывая скобки) =

+1                       (в силу неравенства (3))    q+1=q .

Что и требовалось доказать.

Циклы.

      Цепь, в которой начальная и конечная вершины совпадают, называется циклом. Для циклов вводится понятие циклонического числа z = q -р+ k.

Если z=0, то граф не имеет циклов. Если же z=1, то граф имеет один цикл. Для мультиграфа z выражает число циклов.

Например: при р=4, q=8 и k=1: z= q-р+ k=8-4+1=5.

Теорема.

Деревья.

Если граф не имеет циклов, то он называется ациклическим. В связном графе мостом называется ребро, при удалении которого увеличивается число компонент связности. Если в графе q=р-1, то граф называется древовидным. Ациклический связный граф называется деревом.

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

1) Граф ацикличен и связан.

2) Граф ацикличен и древовиден.

3) Граф связан и древовиден.

4) Граф ацикличен, но добавление одного ребра приводит к образованию ровно одного цикла.

5) Каждое ребро графа есть мост.

6) Любые две вершины соединены единственной цепью.

Доказательство:

Из 1 2:

Граф ациклический и связный. Так как граф ацикличен, то z=0. Так как граф связный, то k=1. Т.к. z=q-р+k, (1), то 0=q-р+1, тогда q=р-1. А значит граф древовидный.

Докажем теперь, что из 2 3:

Так как граф древовидный, то q=р-1. Так как граф ациклический, то z=0. Подставим в (1): 0=р-1-р+k, отсюда k=1, следовательно, граф связный.

Из 3 4:

В графе G k=1; q =р-1; значит из (11 получим)z=0. Добавим ребро и получим граф G , в котором q = q+1; р =р и k = k=1. Тогда z = q -р + k = q+1-р+1=р-1+1-р+1=1. z=1,следовательно, образовался один цикл.

Докажем, что из 4 5:

Допустим, что граф G таков, что некоторое ребро U – не мост, то есть его удаление не приводит к увеличению компонент связности, а значит, граф G = G-U остается связным. По 4 он еще и ацикличен. Но если к связному ациклическому графу добавить ребро U, то должен получиться граф с циклом, значит граф циклический. Пришли к противоречию, следовательно, каждое ребро является мостом.

Из 5 6:

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

Из 6 цепь единственная.

Из 6 1:

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

Что и требовалось доказать.

 

 

 

                                            V0

                                           •

                          V1 •

                                                         • V2

                    V3•

 

    V5 •                   • V6      • V7     • V8         • V9

 

  

  •   •  •  •      •    •    • • • •

V10 V11 V12 V13 V14 V15 V16 V17 V18 V19

 

Рис. 33. Граф-дерево

 

В деревьях обычно одну из вершин выделяют и называют корнем.

Вершины, удаленные от корня на одно и то же расстояние образуют ярус. V0- нулевой ярус, V1, V2 – первый ярус, V3, V4, V7, V8, V9 – второй ярус, V5, V6, V15, V16, V17, V18, V19 - третий ярус, V10, V11, V12, V13, V14 – четвертый ярус.

Вершины, степень которых равна 1 (висячие) называются концевыми, или листьями. На рис. 33 – это вершины, V10, V11, V12, V13, V14V15, V16, V17, V18, V19.

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

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

Каждая вершина дерева называется узлом.