Алгоритмы на графах. Графы, оргафы, деревья

1 ВИДЫ ГРАФОВ

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки.

Определение графа.

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

Рисунок 1.1 – Изображение графов

 

1.1 Неориентированный граф

 

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

• V это непустое множество вершин или узлов,
• E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

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

Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V |  — порядком, число рёбер | E |  — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

Степенью deg V вершины V называют количество инцидентных ей рёбер(при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

 

1.2 Ориентированный граф

 

Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:

• V это непустое множество вершин или узлов,
• A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга  ведёт от вершины v к вершине w.

 

1.3 Смешанный и изоморфные графы

 

Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

Граф G называется изоморфным графу H, если существует биекция f из множества вершин графа G в множество вершин графа H, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и наоборот — если в графе H есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины f − 1(A) в вершину f − 1(B). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

 

1.4 Характеристики графов и матрица смежности, инцидентности

 

Граф называется:

• связным, если для любых вершин u,v есть путь из u в v.

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

деревом, если он связный и не содержит простых циклов.

полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.

• двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2.
• k-дольным, если его вершины можно разбить на k непересекающихся подмножества V1, V2, …, Vk так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
• полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
• планарным, если граф можно изобразить диаграммой на плоскости без         пересечений рёбер.
• взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.

Также бывает:

• k-раскрашиваемым
• k-хроматическим

Простой граф является одномерным симплициальным комплексом.

Более абстрактно, граф можно задать как тройку (V,E,φ), где V и E — некоторые множества (вершин и рёбер, соотв.), а  — функция инцидентности (или инцидентор), сопоставляющая каждому ребру  (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:

• ориентированные графы (орграфы) — когда φ(e) всегда является упорядоченной парой вершин;
• неориентированные графы — когда φ(e) всегда является неупорядоченной парой вершин;

• смешанные графы — в котором встречаются как ориентированные, так и неориентированные рёбра и петли;

• Эйлеровы графы — граф в котором существует циклический эйлеров путь (Эйлеров цикл).

Мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин.

Псевдографы — это мультиграфы, допускающие наличие петель;

простые графы — не имеющие петель и кратных рёбер.

Под данное выше определение не подходят некоторые другие обобщения:

• гиперграф — если ребро может соединять более двух вершин;
• ультраграф — если между элементами xi и uj существуют бинарные

отношения инцидентности.

Способы представления графа в информатике.

Таблица, где как столбцы, так и строки соответствуют вершинам графа.

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

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается: 1, в случае, если связь j «выходит» из вершины i, −1,если связь «входит» в вершину, 0 - во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине).

Данный способ является самым ёмким (размер пропорционален | E | | V | ) для хранения, но облегчает нахождение циклов в графе.

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

 

 

2 ОПЕРАЦИИ НАД ГРАФАМИ

 

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

 

2.1Локальные операции

 

Простейшая операция - удаление ребра.

  При удалении ребра сохраняются все вершины графа и все его ребра, кроме удаляемого. Обратная операция - добавление ребра.

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

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

2.2Алгебраические операции

 

Поскольку граф состоит из двух множеств (вершины и ребра), то различные операции над множествами естественным образом порождают соответствующие операции над графами. Например, объединение двух графов 

 и  определяется как граф   , у которого   ,   , а пересечение - как граф   , у которого   ,   .

Рисунок 2.1 - Иллюстрирует алгебраические операции на графах

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

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

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

Соединением двух графов   и   называется граф, получаемый из их суммы добавлением всех ребер, соединяющих вершины первого слагаемого с вершинами второго

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

 

3 МАРШРУТЫ, ПУТИ, ЦИКЛЫ В ГРАФЕ

 

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

Маршрут называется замкнутым, если  .Путь - это маршрут, в котором все ребра различны.

 Путь называется простым, если и все вершины в нем различны. Цикл - это замкнутый путь. Цикл   называется простым, если все вершины   попарно различны. 2,3,4,5 - не маршрут;

2,3,4,5,1,3,4- маршрут, но не путь;

3,1,4,5,1,2- путь, но не простой;

2,3,1,4,3,1,2 - замкнутый маршрут, но не цикл;

2,3,1,4,5,1,2 - цикл, но не простой;

2,3,4,5,1,2- простой цикл.

 

Рисунок 3.1- иллюстрирует маршрут

 

 

 

3.1 Поиск в ширину

 

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

Процедура поиска в ширину.

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