Алгоритмы поиска в графе. Поиск в глубину и в ширину. Классификация рёбер

Технический Университет  Молдовы

Факультет Вычислительной техники, Информатики и Микроэлектроники

Кафедра Информационных Технологий

 

 

 

 

 

 

 

 

 

 

 

 

 

Курсовая работа

 на тему:

Алгоритмы поиска в графе.

Поиск в глубину и в ширину.

Классификация рёбер.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил:                            ст. гр. С-114                   Келембет Т.

Проверил:                                                                      Фалько Н.С.                        

 

 

 

 

 

Кишинёв 2012

Введение.

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

       Начало  теории  графов  единодушно  относят   к  1736 г., когда  Л.Эйлер не  только решил популярную в  то время задачу о кенигсберских   мостах,  но  и  нашел  критерий  существования  в графе специального  маршрута (  эйлерова цикла, как  его теперь называют  ). Однако этот  результат  более ста  лет оставался  единственным результатом теории  графов.  Лишь  в  середине  19  века  инженер  -  электрик Г.Кирхгоф  разработал теорию  деревьев для исследования  электрических цепей, а  математик А.Кэли  в связи с  описанием строения углеводородов  решил  перечислительные задачи  для трех типов деревьев.  К тому же периоду  относится появление знаменитой проблемы четырех красок.

        Родившись  при решении головоломок и занимательных игр ( задачи  о шахматном  коне, о  ферзях, "кругосветное  путешествие", задачи  о  свадьбах и гаремах  и т.п. ), теория графов  стала в настоящее время  простым, доступным и мощным средством решения вопросов, относящихся к  широкому кругу проблем. Множество самых разнообразных задач формулируется в терминах точек и связей между ними, т.е. в терминах графов. Так, например, могут быть сформулированы задачи составления расписания, анализа сетей в электротехнике, анализа цепей Маркова в теории вероятностей, в программировании, в проектировании электронных схем, в экономике, в социологии и т.д. Поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое значение.

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

    Термин "граф" впервые появился в книге выдающегося венгерского  математика Д.Кенига  в 1936 г., хотя начальные задачи теории  графов  восходят еще к Эйлеру (18 век).

        Графом  G(V,E) называется совокупность двух множеств - непустого множества V (множества точек) и множества E (множества линий). Элементы множества V называются вершинами графа, а элементы множества E называются ребрами графа.

G(V,E) =

, V ¹ Æ, E Í V ´ V

Если в элементах множества E допускается перестановка вершин, тогда граф называется неориентированным.

Пусть v₁ и v₂ - вершины, е = (v₁, v₂) - соединяющее их ребро.   Тогда вершина v₁ и ребро е инцидентны,  вершина v₂ и ребро е также инцидентны. Ребра, инцидентные одной и той же вершине, называются смежными. Две вершины, инцидентные одному ребру, также называются смежными.

Степенью  вершины графа называется количество  ребер, инцидентных  данной вершине. Вершина графа, имеющая степень 0, называется изолированной, а если степень ее равна 1, то такая вершина называется висячей.

Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.

На рис. 1 приведен пример диаграммы  графа, имеющего четыре вершины и  четыре  ребра. В этом графе вершины v₁ и v₂, v₂ и v₃, v₄ и v₁, v₂ и v₄ смежны, а  вершины v₁ и v₃, v₃ и v₄ не смежны. Смежные ребра: е₁ и е₂, е₂ и е₃, е₁ и е₃, е₄ и е₁, е₄ и е₃. Несмежные ребра: е₂ и е₄.

 

Пример неориентированного графа:

 

 

 

 

 

 

 

 

Рис.1

        Часть графа G ( V, E) -  это такой граф G' (V',E'), что V' Í V, E' Í E.

   Подграфом графа G ( V, E) называется такая его часть G' (V',E'), которая вместе со  всякой парой вершин содержит и ребро, если только оно есть в G ( V, E).

Если V' = V, то G' (V',E') называется остовным подграфом G ( V, E).

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

v_0, e₁, v₁, e₂, v₂, …, e_k, v_k,

в которой любые два соседних элемента инцидентны.

Длиной пути называется количество ребер в нем ( с повторениями). Если путь М = v_0, e₁, v₁, e₂, v₂, …, e_k, v_k, то длина М равна k ( обозначается | М | = k.

Если v₀ = v_k, то путь замкнут.

Если все  ребра различны, то путь называется цепью. Если все вершины ( а значит и ребра) различны, то путь называется простой цепью.

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

        Расстояние между двумя вершинами - это длина кратчайшего пути,  соединяющего эти  вершины.

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

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

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

        Дополнением простого графа G  называется граф  G' , имеющий те же вершины, а его ребра являются дополнением G  до полного графа.

 Два графа G  и H изоморфны если существует взаимно  однозначное отображение ( называемое изоморфизмом ) множества вершин  графа  G  на  множество   вершин  графа  H,  сохраняющее смежность. Автоморфизмом графа G называется изоморфизм графа G на себя. Деревом называется связный неориентированный граф без циклов, без петель и кратных ребер.

Пример дерева

 

Рис.2

 

Несвязный граф без циклов называется лесом.      

Пустой граф (дерево) - это граф с пустым множеством вершин.

 Если в элементах множества Е не допускается перестановка вершин, тогда граф называется ориентированным.  Элементы множества Е называются      дугами. Пример ориентированного графа:

 

 

 

 

 

 

 

Рис. 3

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

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

        Корневое   дерево   -   это   связный   орграф   без   циклов,  удовлетворяющий следующим условиям:

        а). имеется   ровно одна вершина, называемая  корнем, к которой  не ведет  ни одна дуга;

        б). к  каждой  вершине, отличной  от корня,  ведет  ровно одна  дуга;

        в).  преемники  всякой  вершины упорядочены.

        Вершины   корневого дерева,  не имеющие   преемников, называются  листьям

 

 

 

 

 

Рис. 4

          

Способы задания графов 

               Существует три основных способа  дискретного задания графа:

 

        1). Матрица  инцидентности;

 

        2). Матрица  смежности;

 

        3). Список смежности  ( инцидентности );

 

        Рассмотрим  подробнее каждый из этих способов  задания графа:

         

 

 

 

Матрица инцидентности  графа

  Матрицей  инцидентности для неориентированного графа с n вершинами и m ребрами называется матрица , строки которой соответствуют ребрам, а столбцы - вершинам.

 Элементы 

 

 

 

 

Матрицей  инцидентности для ориентированного графа с n вершинами и m ребрами называется матрица , строки которой соответствуют ребрам, а столбцы - вершинам.

 Элементы 

 

      

 

 

 

Например, для  неориентированного графа  на рис.1  матрица инцидентности                        

имеет следующий вид (рис. 5):     

 

	v1	v2	v3	v4
е1	1	1	0	0
е2	0	1	1	0
е3	0	1	0	1
е4	1	0	0	1

 

Рис. 5

Для  ориентированного графа  на рис. 3  матрица инцидентности            

имеет следующий вид (рис. 6):

 

 

	v1	v2	v3	v4
e1	-1	1	0	0
e2	0	-1	1	0
e3	-1	0	1	0
e4	-1	0	0	1
e5	0	0	1	-1

 

Рис. 6

 

        Как легко   можно заметить, этот способ  задания  графа довольно  неэффективен: каждая  строка такой матрицы содержит  только 2 ячейки с  ненулевыми  значениями  ( очевидно, так  как  одно ребро  (дуга) может  быть  инцидентно не  более чем двум вершинам). В  результате мы имеем  довольно  неэкономное использование  оперативной памяти ЭВМ.

        Типичный пример  задания матрицы  инцидентности  на языке Pascal  - при помощи  двумерного массива m на n:

        Matr_Ints: array [1..LinksCount, 1..TopsCount] of integer;

 

 

 

Матрица смежности графа

Матрицей смежности неориентированного графа с n вершинами называется матрица , в которой

 

 

 

 

Например, для  неориентированного графа  на рис.1  матрица смежности                 

имеет следующий вид (рис. 7):     

	v1	v2	v3	v4
v1	0	1	0	1
v2	1	0	1	1
v3	0	1	0	0
v4	1	1	0	0

 

Рис. 7

Матрицей смежности  ориентированного графа с n вершинами называется матрица , в которой

 

 

 

Например, для  ориентированного графа  на рис. 3  матрица смежности           имеет следующий вид (рис. 8):     

 

	v1	v2	v3	v4
v1	0	1	1	1
v2	0	0	1	0
v3	0	0	0	0
v4	0	0	1	0