Разработка урока на тему "Графы, алгоритмы на графах"

Тема урока: Графы, алгоритмы на графах.

Перейдите по ссылке и рассмотрите графы:

https://www.youtube.com/watch?v=9fdkrSvgqeo

Изучить данный теоретический материал и выполнить тест по теме: «Графы, алгоритмы на графах».

Ответы внести в следующий бланк:

№ задания	Ответ:
1
2
3
4
5
6
7
8
9

1. Графы

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

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

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

Пример:

    

Мультиграф — это граф, у которого пара вершин соединены несколькими ребрами. А такие ребра, которые соединяют одну и ту же пару вершин, называют кратными. Две различные вершины графа, соединенные ребром, называются смежными.

Ребро не всегда соединяет разные вершины. 

Петля — это ребро, которое соединяет вершину саму с собой.

 

Рис. 1

 

На рисунке 1 изображен мультиграф со смежными ребрами (выделены черным цветом), кратными ребрами (выделены красным) и  петлями (выделены синим).  

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

Пример:

На рисунке 2 изображен граф с 7 вершинами.

 

Рис. 2

Составим список степеней вершин этого графа: γ(a)=1,γ(b)=5,γ(c)=2,γ(d)=2,γ(e)=3,γ(f)=2,γ(g)=1.  

Свойства графов:

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

2. Для любого графа количество вершин нечетной степени всегда будет четное.

3. Сумма степеней всех вершин графа равна удвоенному числу его ребер.

Рассмотрим пример «Представление графа таблицей смежности»:

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

Вершина	A	B	C	D	E
A		0	0	0	4
B	0	0		0	13
C	0	10	0		15
D	0		0	0	6
E	4	13	15	6

Решение:

Рассмотрим граф на рисунке.

 

Замечаем, что на графе всего 6 ребер, из них 1 петли. Составим список этих ребер: AE, BC, BE, CE, DE и EE. Каждому ребру сопоставленно число:

AE — 4, BC — 10, BE — 13, CE — 15, DE — 6, EE — 2.

А ребрам AA, AB, AC, AD, BB, BD, CC, CD, DD — 0, так как не соединены.

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

Вершина	A	B	C	D	E
A	0	0	0	0	4
B	0	0	10	0	13
C	0	10	0	0	15
D	0	0	0	0	6
E	4	13	15	6	2

 

Маршрут на графике — это последовательность ребер a1,a2,...,an, в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.

Для графа, изображенном на рисунка 2,  a1,a2,a3,a7,a1,a5 — маршрут, a6,a2,a5,a7 — циклический маршрут, а последовательность a7,a6,a2,a1,a4 — маршрутом не является.

  

Рис. 2

Цепь — это маршрут, в котором каждое ребро содержится не более одного раза. Цепь, являющаяся циклическим маршрутом, называется циклом.

Для графа, изображенном на рисунка 2, a1,a2,a6,a7,a4,a5,a7 — цепь, a2,a6,a7,a8,a4,a2,a6 — цикл.

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

Для графа, изображенном на рисунка 2, a1,a2,a6,a7,a4 — простая цепь, a2,a6,a7,a8,a4 — простой цикл.

Связанные вершины — это вершины a и b, для которых существует цепь, начинающаяся в a и заканчивающаяся в b.

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

Один и тот же граф может быть изображен по-разному. Например, граф на рисунке 2 тот же, что и изображен на рисунке 3. 

Рис. 3 

2. Алгоритм обработки графов.

 

Пусть требуется граф с n вершинами и m ребрами. Поскольку из каждой вершины выходит не более чем n−1 ребер, а сумма всех степеней вершин равна удвоенному числу ребер, имеем соотношение 2m≤(n−1)n. Приведем алгоритм, в котором через SR[1:m;1:2] обозначен массив, содержащий список ребер, а через TS[1:n;1:n] обозначен массив, содержащий таблицу смежности.

 

Алгоритм Случайный граф

цел: n,m,i,j,k,SR[1:m;1:2];TS[1:n;1:n];

{ Запросить n;    (* запрашивается количество вершин *)

   Запросить m;   (* запрашивается количество ребер *)

   Если (m≻n×(n−1)/2)

    то  { Сообщить «Такой граф строить нельзя»; }

    иначе

    { Делать от i:=1 до n

        { Делать от j:=1 до n

            { TS[i;j]:=0;

            }

        }       (* Первоначальное заполнение таблицы смежности нулями *)

        Делать от i:=1 до m

        {j:=INT((n−1)×rand(1))+1;

          k:=INT((n−j)×rand(1))+j+1;

               Делать пока TS[j;k]:=1

              {j:=INT((n−1)×rand(1))+1;

                k:=INT((n−j)×rand(1))+j+1;

               }

               TS[j;k]:=1;

               TS[k;j]:=1;

               SR[i;1]:=j;

               SR[i;2]:=k;

        }          (* случайное добавление одного ребра *)

       Сообщить «Вот таблица смежности»;

       Сообщить TS[1:n;1:n];      (* в реальной программе это действие оформляется двойным циклом *)

       Сообщить «Вот список ребер»;

       Сообщить SR[1:m;1:2];     (* в реальной программе это действие оформляется двойным циклом *)

    }

}

3.Алгоритмы поиск в глубину и поиск в ширину

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

 

Рассмотрим несколько таких алгоритмов, которые можно составить.  

Алгоритм поиск в глубину. Пусть зафиксирована начальная вершина v0. Выберем смежную с ней вершину v1. Затем для вершины v1 выбираем смежную с ней вершину из числа еще не выбранных вершин и т.д.: если мы уже выбрали вершины v0,v1,...,vk, то следующая вершина выбирается смежной с вершиной vk из числа невыбранных. Если для вершины vk такой вершины не нашлось, то возвращаемся к вершине vk−1 и для нее ищем смежную среди невыбранных. При необходимости возвращаемся назад и т.д. Так будут перебраны все вершины графа и поиск закончится.

Пример:

На рисунках 1 и 2 показаны реализации поиска в глубину для одного и того же графа (начальная вершина — 0).

 

  

Порядок  обхода графа с помощью алгоритма поиск в глубину для рисунка 1 — 0,1,2,3,4,5,6,9,7,10,11,8, а для рисунка 2 — 0,1,2,4,5,3,6,7,8,9,10,11.  

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

 

Если граф задан таблицей смежности, организуем одномерный массив В, число элементов в котором совпадает с числом вершин в графе. На k−м  месте этого массива будем писать номер вершины, в которую мы попали на k−м шаге. Из всех смежных вершин будем выбирать вершину с наименьшим номером.

 

Алгоритм, реализующий поиск в глубину:

  

Алгоритм Поиск в глубину

цел: k,m,s,t,u,n,a,v,i,G[1:n;1:n],B[1:n];

{ Запросить n;    (*запрашивается количество вершин*)

   Запросить G[1:n;1:n];   (*реально это действие — ввод таблицы смежности — оформляется двойным циклом*)

   B[1]:=1;   (*в качестве исходной взята вершина с номером 1*)

   Делать от k:=2 до n

  {  B[k]:=0;

   }

   k:=1;   (*счетчик количества пройденных вершин*)

   m:=0;   (*k - m — порядковый номер вершины для очередного шага поиска*)

   Делать пока (k)

   {  s:=1;

      Делать от t:=1 до n

      {  v:=1;

         Делать от i:=1 до k

         {  Если (B[i]=t) то { v:=0; } }

          Если ( v=1 и G(B[k−m],t)=1) то

          { a:=t;

            s:=0;

          }

       }

 (*если существует смежная вершина, которая еще не просматривалась, то s=0*)

       Если (s=0) то

       {  k:=k+1;

           B[k]:=a;

           m:=0;

        }

        иначе  { m:=m+1; }

     }

     Делать от k:=1 до n

    { Сообщить B[k],k;

    }

}

Алгоритм поиск в ширину. Пусть зафиксирована начальная вершина v0. Рассматриваем все смежные с ней вершины v1,v2,...,vk. Затем рассматриваем смежные вершины каждой из рассмотренных вершин v1,v2,...,vk, и т.д. Так будут перебраны все вершины графа и поиск закончится.

Пример:

На рисунках 3 и 4 показаны реализации поиска в ширину для одного и того же графа (начальная вершина — 0).

 

Порядок  обхода графа с помощью алгоритма поиск в ширину для рисунка 3 — 0,1,2,3,4,5,6,7,8,9,12,1,0,11, а для рисунка 4 — 0,1,2,3,4,5,6,10,7,8,9,11,12.

Алгоритм, реализующий поиск в ширину:

  

Алгоритм Поиск в ширину

цел: k,m,s,t,n,G[1:n;1:n],B[1:n];

{ Запросить n;    (*запрашивается количество вершин*)

   Запросить G[1:n;1:n];   (*реально это действие — ввод таблицы смежности — оформляется двойным циклом*)

   B[1]:=1;   (*в качестве исходной взята вершина с номером 1*)

   Делать от k:=2 до n

  {  B[k]:=0;

   }

   s:=1;

   Делать от k:=2 до n

   {  t:=1;     

       m:=−1;

       Делать пока (G[s,t]=0 или t=s или B[t]≠0)

      { t:=t+1;

      }

      Если (t) то

      {  B[t]:=k;

          m:=m+1;

       }

       иначе

       { s:=k−m;

        }

    }

    Делать от k:=1 до n

    { Сообщить B[k],k;

    }

}

1. Волновой алгоритм, мосты и точки сочленения

Рассмотрим одну из часто встречающихся задач: найти длину кратчайшей цепи от заданной вершины до любой другой. Для решения этой задачи нам нужен волновой алгоритм.

Длина цепи — это количество ребер, которые содержатся в этой цепи.

Волновой алгоритм. Исходной вершине припишем число 0. Каждой смежной с ней вершине припишем число 1. Каждой вершине, смежной с той, которая уже помечена числом 1 и не была помечена раньше, приписываем число 2. Каждой вершине, смежной той, которая уже помечена числом 2 и не была помечена раньше, приписывают число 3. И так далее до тех пор, пока такое действие можно будет производить. При этом могут оказаться вершины, добраться до которых так и не удастся.

Пример:

На рисунке 1 показан результат обработки графа волновым алгоритмом после первого шага.

 

 

 

На рисунке 2 полностью обработанный результат обработки графа волновым алгоритмом.

 

 

Для волнового алгоритма граф указывается таблицей смежности, где таблицей смежности с 20 вершинами графа является целочисленный массив G[1:20;1:20]; результатом работы алгоритма — одномерный целочисленный массив P[1:20], для которого каждое значение элемента P[k] равно длине пути от заданной вершины с номером k. Элементу P[k] присваивается значение −1, если вершина с номером k недостижима.

 

Алгоритм Кратчайший путь

цел: I,J,A,K,G[1:20;1:20],P[1:20];

{ Запросить G[1:20;1:20];

   Запросить A;   (*запрашивается номер начальной вершины*)

   Делать от I:=1 до 20 

  {  P[I]:=−1;   (*сначала все элементы массива-результатов равны -1*)

   }

   P[A]:=0;    (*до исходной вершины добираемся за 0 шагов*)

   Делать от I:=0 до 19 

  {  Делать от K:=1 до 20 

       {  Если P[K]=I то

           {  Делать от J:=1 до 20 

              {  Если (P[J]=−1 и G[J,K]=1) то

                  {  P[J]:=I+1;

                  }

              }

           }

        }

   }

   Делать от I:=1 до 20

   {  Сообщить "Кратчайший путь от вершины", A;

       Сообщить "до вершины", I;

       Сообщить "равен", P[I];

   }

}

 

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

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

Двусвязный граф — это связный граф, не имеющий точек сочленения.

Полный граф — это граф, у которого каждая вершина соединена со всеми остальными.

Пример:

На рисунке 3 изображен граф, у которого вершины D, E, F и H — точки сочленения, а ребра DE и HI — мосты.

 

 

На рисунке 4 изображен двусвязный граф.

 

Тест по теме: «Графы, алгоритмы на графах».

1. Соотнесите понятия и их определения:

 

1. Маршрут на графике 

2. Цепь 

3. Граф 

4. Петля 

5. Таблица смежности 

А) это последовательность рёбер а1, а2, ..., an, в которой конец одного ребра служит началом другого.

В) это конечная совокупность вершин, некоторые из которых соединены рёбрами.

С) это ребро, которое соединяет вершину саму с собой.

 D) это это маршрут, в котором каждое ребро содержится не более одного раза.

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

Ответ:

1	2	3	4	5

1. Представление графа списком его ребер

Для данного графа выбери правильное его представление списком ребер:

1. (AB; 11), (AD; 3), (BC; 5), (BD; 7), (CD; 9)

2. (AС; 5), (AD; 9), (BC; 7), (BD; 3), (CD; 11)

3. (AB; 5), (AD; 9), (BC; 7), (BD; 3), (CD; 11)

4. (AB; 3), (AD; 5), (BC; 9), (BD; 11), (CD; 7)

1. Представление графа таблицей смежности

Начало формы

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

 

 

Вершина	A	B	C	D	E
A		5	2	4	0
B	5	3		6	10
C	2	0	1		7
D	4		0	8	0
E	0	10	7	0

Конец формы

1. Степени вершин графа

Приведен список степеней вершин графа. Выбери на каком из рисунков изображен граф.

 

γ(A)=4,γ(B)=3,γ(C)=2,γ(D)=4,γ(E)=4,γ(F)=1,γ(G)=4,γ(H)=2.

1. 

2. 

5. Простой цикл графа

Начало формы

Для данного графа выбери простой его цикл длиной — 4.

1. a17,a10,a6

2. a17,a12,a14,a3

3. a17,a10,a6,a17

4. a17,a10,a5,a3

5. a17,a10,a5,a13

1. Сколько ребер и вершин в данном графе?

 

1. 10 вершин и 14 ребер

2. 8 вершин и 16 ребер

3. 8 вершин и 14 ребер

4. 8 вершин и 15 ребер

5. 7 вершин и 14 ребер

6. 14 вершин и 7 ребер

1. Основные определения

Двусвязный граф — это ... .

1. граф, имеющий точек сочления

2. связный граф, неимеющий точек сочления

3. граф, у которого каждому ребру сопоставлено некоторое число

4. граф, имеющий мосты

1. Определение точек сочленения и мостов графа

Дан граф. Определи его точки сочленения и мосты.

 

 

1) Точки сочленения графа:

1. C, D, I, H

2. C, I

1. A, B, F, J, K, L

2. D, H. E, G

2) Мосты графа:

1. AD, AH

2. AD, BD, BJ, JH, AH

3. BJ

4. AF, BC, EK, FK, FL, LG, IJ

1. Обход графа с помощью алгоритмов поиск в глубину и поиск в ширину

Дан граф. Перечисли вершины графа в порядке обхода с помощью алгоритма поиск в глубину, где 1 — начальная вершина (ответ запиши через запятую с пробелом).

 

 

Порядок обхода: _________