Деревья и циклы

 
 

ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ  СООБЩЕНИЯ 
 
 
 
 
 
 
 
 
 
 

Лабораторная  работа №4

ДЕРЕВЬЯ И  ЦИКЛЫ 
 
 
 
 

Работу выполнила:

студентка группы КИБ-908

Дарзнек Н.В.

Работу проверил: Микони С.В. 
 
 
 
 
 
 

САНКТ-ПЕТЕРБУРГ  
2011 
 

ПРОТОКОЛ  выполнения работы

"Деревья  и циклы" 

1. Деревья. Остовы.

 

Задание 2. 

Вычислить количество остовных деревьев графа.

Задан неориентированный  граф с матрицей смежности: 
 

Число остовных деревьев равно 4. 

Задание выполнено  правильно.

Граф, заданный такой  матрицей, имеет следующий вид: 

                                 a1

                                                       a2

 

                    a4  
 

a3 

Для того, чтобы вычислить число всевозможных остовов графа, воспользуемся матрицей Кирхгофа: 
 

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

Составим  матрицу Кирхгофа для нашего графа  и найдем алгебраическое дополнение(например, первого элемента). 
 

Алгебраическое дополнение 1-го элемента: 
 
 

Следовательно, для  данного графа существует 4 остова: 

                                 a1 

                                                   a2

1) 

                    a4  
 

    a3 
 
 

                                  a1

                                                    a2

2) 

                    a4  
 

    a3                                                     

                                  a1

                                                    a2

3) 

                    a4  
 

       a3                                                                    

                                  a1

                                                    a2 

4)

                    a4  
 

    a3

2. Циклы и разрезы

Задание 4.

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

Задан граф с матрицей смежности: 
 

Граф, заданный такой  матрицей, имеет следующий вид:

                                  a1

                       1

           a2                                      3                         

                             2 
 

             4    5              6 

                                                                          a6

                             7

           a3                                                        10 

           8

a5

                     9

                             a4 
 
 

 Вы выделили  остовное дерево со следующей матрицей смежности: 
 
 

Граф, заданный такой  матрицей, имеет следующий вид:

                                  a1

           a2                                                     

                               2 
 
 

             4

                                                                           a6

                   7 

          a3 

                    8

                                                       a5

                         9

                             a4 

 Выделенному остовному дереву соответствует следующий цикловой базис: 

    Цикл  1 - а1,а2,а3,а1

    Цикл  2 - а3,а4,а2,а3

    Цикл  3 - а3,а4,а5,а2,а3

    Цикл  4 - а1,а3,а6,а1

    Цикл  5 - а3,а4,а5,а6,а3 

Задание выполнено  правильно.

• Фундаментальная(базисная) матрица циклов.

 

 

Алгоритм формирования фундаментальной матрицы циклов: 

1. G = T v T^*(Т-остов, T^*-кодерево)
2. i=1
3. G_i={e_iЄ T^*v e_j-kЄ T}
4. i++

• Фундаментальная матрица разрезов (коциклов). 
  

 
 
 
 
 

Алгоритм формирования фундаментальной матрицы: 

1. G = T v T^*(Т-остов, T^*-кодерево)
2. i=1
3. K_i={e_i Є T^*v e_jЄ T^*| e_j, e_iЄC_k}
4. i++

 
 

• Циклический и коциклический ранги графа.

 

Циклический рангсвязного графа равен числу хорд любого его кодерева: m-n+1.

Для несвязного графа m-n+p, где p-число связных компонент. 

Так как в нашем  случае граф связный, тогда: 
 
 

Коциклический рангсвязного графа равен числу рёбер любого остова: n-1.   
 
 

• Небазисные  циклы и разрезы на основе базисных(по одному).

 
 
 

3. Эйлеровы и Гамильтоновы  циклы и цепи

1. Эйлеров цикл должен одноразово обходить все рёбра.

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

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

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

2. Гамильтонов цикл должен одноразово обходить все вершины  графа.

В нашем случае можно  обойти все вершины одноразово, следовательно граф обладает свойством Гамильтонова графа. 

Определение Гамильтонова цикла(цепи) методом поиска в  глубину. 

Для этого представим исходный граф с помощью списка инциденций: 

а1⁰    а2¹    а3²    а6⁵

а2¹    а1⁰    а3²    а4³    а5⁴

а3²    а1⁰    а2¹    а4³    а6⁵

а4³    а2¹    а3²    а5⁴

а5⁴    а2¹    а4³    а6⁵

а6⁵    а1⁰    а3²    а5⁴ 

Помечая пройденные вершины(всеми способами), построим дерево. 
 
 
 
 
 
 
 
 

а1

 

            а2                     а3                          а6

 

а3           а4         а6     а2   а4     а6           а3               а5

 

а4     а6     а3    а5   а4   а6   а4  а2     а5        а2      а4      а2       а4

 

а5     а5     а6а6  а3   а3   а5  а5   а4   а2  а5  а4  а2  а5  а3  а4 а2  а3   а2

 

а6     а4     а5    а3   а6   а4   а6  а6   а2   а4  а4   а5  а5  а2  а4   а2  а3   а2  
 

• Корень дерева.

В соответствии каждой вершине поставим её тип. 

                                      a1    0  

          a2    0

 
 
 
 

                                                                      a6    0

 

           a3

              2

                                                                  0

                                                         a5

                             a4  1 

Корнем является вершина а3. 

4. Рекомендации  по практическомуприменению изученных свойств и алгоритмов 
 

1. Свойство эйлерового графа применимо, например, в задачах о кенигсбергских мостах.
2. Очевидно, что задача коммивояжера — это задача отыскания кратчайшего гамильтонова цикла в полном графе.
3. Нахождение циклов может применяться в выборе удобного маршрута следования.
4. Пусть задано множество аэродромов и нужно определить минимальный (по сумме расстояний) набор авиарейсов, который позволил бы перелететь с любого аэродрома на любой другой. Решением этой задачи будет кратчайший остов полного графа расстояний между аэродромами.