Основы теории делимости. Основная теорема теории чисел. Алгоритм Евклида и цепные дроби. Разложение числа в цепную дробь, страница 15

   8       9                    

5       6     7

2     3       4

1

8,5,6,7,4,3,2,1

Т – множество ребер, содержащих каркас.

T={(1,2), (2,3), (3,4), (4,7), (7,6), (6,5), (5,8), (6,9)}

Если граф дерево, то существует 1 каркас, если граф цикл, то – несколько.

Следствие к т.51

1) Граф связан G=(V,E)   и есть подмножество ребер FÍE, для любого цикла графа G существует хотя бы 1 ребро не лежащее в F, тогда можно построить каркас Т, все ребра F будут принадлежать T. T=(V,E`) FÍE`

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

Мы можем удалить ребро из цикла, не принадлежащее F.

2) Связанный граф с Р вершинами и Р-1 ребрами, является деревом.

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

Допустим P, P-1,    если были бы циклы, то при построении Р вершин, было бы Р ребер, т.е. удаляя 1 ребро получим дерево.

3)  Если связанный граф имеет p вершин и q ребер, то q-p+1 >= 0.

Строя каркас, Р и Р-1 ребер, а в графе больше ребер, чем в каркасе. Следовательно это и будет >= 0.

Определение: Есть произвольный граф p – вершин, q – ребер.

k – число компонент связности, тогда говорят, что j:=p-k –называется корангом графа.

m:=q-p+k – называется цикломатическим числом графа.

p1q1        p2q2     …       pkqk

(V1,E1)   (V2,E2)  …     (Vk,Ek)

k – число компонент связности. Тогда для любой компоненты есть коранг и цикломатическое число.

ji:=pi –1       j=Si=1kji

mi:=qi -pi+1   m=Si=1kmi

Теорема: 52

1.  Для любого графа его m>=0, т.к. mi=qi-pi+1>=0  (Теорема 51)

2.  G – связанный

G – дерево <=> m=0 ( необходимый и достаточный признак дерева).

Определение: Пусть есть связанный граф P – вершин, q – ребер

G(V,E),   T=(V,E) – стягивающее дерево

XÎE` - ребра из каркаса называются ветвями, которые не вошли хорды.

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

yÎE\E`  y – хорда

Каждой хорде соответствует главный цикл.

М – главным циклов (сколько хорд)

P – вершин, q – ребер из них вычесть ветви (p-1)

q-(p-1)=m

Пример: На главные циклы

x1,x2,x3,x4,x5 – ветви                  с    y1     e    y2        циклы: bcedb:  y1

y1,y2,y3 – хорды                        x2x3  x4dx5     f                   defd :   y2

ax1             y3                             abdfa:   y3

Определение: Пусть есть каркас данного графа

Элементарное преобразование дерева. Вводим хорду, получаем цикл, удаляем ветвь, получаем каркас.

 


Коциклы

G=(V,E)

Коцикл – минимальное количество ребер при удалении одного из них граф теряет связанность. C=E`ÌE   G`=(V,E\C)

Минимум: Что ни какое собственное подмножество С этим свойством не обладают

{x1,x2}  -  коцикл                                                                                    x3      x1

{x1,x2,x3}   -  не является коциклом, т.к. {x1,x2} его подмножество              x2

Определение:  Пусть есть связанный граф G=(V,E)

C – его коцикл

G=(V,E\C)

Получим у G` несколько компонент связности k>=2

Пусть k=3

(V1,E1), (V2,E2), (V3,E3)

т.к. G связан, то существует ребро x, которое соединяет (V1,E1) и (V2,E2) и оно принадлежит С, тогда если рассмотреть множество С-х  (С\{x}), то все равно граф несвязан, но мы получим множество С-х – коцикл, этого не может быть, т.к. мы предположили, что k=3, a k=2, т.е. при удалении ребер принадлежащих С, граф распадается на 2 компоненты связности.

Ребра коцикла обладают свойством: (они не соединяют V1 и E1, V2 и E2), они должны соединять V1 и V2.

Теорема: 53 При удалении ребра коцикла, он распадается на 2 компоненты связности и ребра коцикла соединяют вершины одной компоненты связности с другой.

Следствие: Любой Цикл и любой коцикл связанного графа имеют четное число общих ребер.

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

 


(1)        а       (2)

a)  Если цикл принадлежит (1) и  не пересекается с ребром коцикла, четно.

b)  Если цикл пересекается с ребрами, коцикла, то нужно пройти четное число раз, туда и обратно.