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

Следствие к теореме 43

Для любого ребра существует цикл содержащий это ребро ("xÎE)

Следствие 2.

В графе G существует 2 цепи, содержащие вершины, a и b тогда из ребер этих цепей можно построить цикл.

a¹b, цепь p₁,p₂                                                      b

a

Связность

Граф называется связанным, если любые две его вершины можно соединить цепью G=(V,E)

Возьмем не пустое подмножество вершин графа d¹0, sÎV

E(s)={xÎE | aÎS, bÎS} – множество ребер, для которых эти вершины – концевые

G`=(S,E(s)) – подграф графа G, порожденный множеством S.

Вершина а вступает в отношение с b если их можно соединить цепью это отношение типа эквивалентности или равенства.

a=b   1) a=a

2) a=b  <=> b=a

3) a=b

b=a    => a=c

Если существуют 2 цепи, соединив получим путь, а из пути можно получить цепь.

Это отношение разбивает множество вершин на не пересекающиеся подмножества.

V₁ÈV₂È…ÈV₂=V,  V_iÇV_j=Æ

Если бы V_i=V_j, то был бы путь (3)

Рассмотрим  G₁=(V₁, E(V₁))

G₂=(V₂, E(V₂))

…

G_k=(V_k, E(V_k))

G₁…G_k называется компонентами связности графа G

K – степень связности графа G

Из связного графа – степень связности = 1

                                                                     Не пересекаются

Степень связности = 3

Определение:

Пусть существует G=(V,E), xÎE

G-X : = (V,E\{X}) выбрали ребра, вершины остались

Теорема: 44

Если в связанном графе ребро x принадлежит циклу, то граф G-X остается связанным графом.

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

Пусть x=(a₀,a₁)

a₀x₁a₁x₂a₂…x_La_L

верно и обратно

Теорема: 45

Если G=(V,E) связанный граф, если после удаления xÎE граф G-X остается связанным, то x принадлежит циклу

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

G=(V,E)  G-X – связанный, тогда а можно

x=(a,b)              соединить с b и добавить x получим цикл.

Определение:

Ребро xÎE, G=(V,E) называется мостом, если степень связности (G-X) > степени связности G

 

x                 x – мост

Теорема: 46  (44-45) необходимый и достаточный критерий моста х является мостом <=> в G нет циклов, содержащих эти ребра.

=> доказательство по теореме 44

<= доказательство по теореме 45

Теорема: 47  Задача о Кеннинсбергских мостах

Определение:

Разомкнутой (замкнутой) Эйлеровой цепью называется простой разомкнутый (замкнутый) путь, включающий все ребра графа.

В графе G=(V,E) существует замкнутая эйлерова цепь <=>

1)  G – связанный

2)  Все его вершины имеют четную степень deg(a_i) – четно "a_iÎV

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

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

2)  В каждой цепи, каждая вершина встречается четное число раз - вошли вышли.

          а₀             а₁              а₂

Пусть а₀ имеет нечетную степень , тогда их четное число(свойство), этого не может быть.

2 à 1 Т.к. имеются все вершины четной степени (т 42) ?????

a₀x₁a₁x₂a₂   x_La_L=a₀

он самый большой

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

1) Что вершины графа  принадлежат этому пути

Пусть это не так, b не лежит на этом пути. Т.к. граф связанный, вершина b связана цепью с любой a_i, среди путей выберем самый короткий путь, тогда ни одна вершина этого пути кроме a₁ не принадлежит этому пути (иначе получиться, что ест путь короче) следовательно рассмотрим последнее ребро y и оно не принадлежит x_i, т.к. одна из вершин не от сюда.

Выберем все ребра {x₁,…,x_L}, четность сохраняется, тогда в оставшемся графе G для y существует замкнутый простой путь, в оставшемся графе ребра не принадлежат пути.

G={V,E\{x₁,…,x_L}, тогда получим путь длиннее и останется простой.

На самом деле противоречие в принадлежании пути.

2) Все ребра лежат на пути.

Пусть существует  у  не принадлежащий пути, но т.к. все вершины лежат на этом пути, то это ребро «пристегнуто» к этому пути. (также как в 1)

Следствие: Граф имеет открытую Эйлерову цепь тогда когда

1)  граф связанный

2)  Существуют 2 вершины нечетной степени.

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