Структуры данных. Графы.

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

 

 

Графы

Определение. Графом называется пара G=(V,E), где V - множество объектов произвольной природы, называемых вершинами (vertices, nodes), а E - семейство пар ei=(vi1, vi2), vijÎV, называемых ребрами (edges). В общем случае множество V и/или семейство E могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т.е. графы, у которых как V, так и E конечны. Отметим, что, вообще говоря, для каждой пары вершин ребра в семействе E могут быть неуникальными, что не дает возможности назвать E множеством.

Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным (directed graph), сокращенно - орграф (digraph), иначе - неориентированным (undirected graph). Ребра орграфа называются дугами (arcs).

Некоторая вершина и некоторое ребро графа называются инцидентными, если вершина является одной из вершин ребра. Соответственно, пара вершин инцидентна ребру, если эти вершины являются вершинами одного ребра, а сами вершины называются смежными. Два ребра графа называются смежными, если они инцидентны одной вершине.

 

Поиск пути в графе с наименьшим количеством промежуточных вершин

Пусть дан некоторый конечный граф G=(V,E) и две его вершины a,bÎV. Требуется найти путь между вершины графа a и b с минимальным количеством промежуточных вершин, т.е. требуется найти последовательность {a1,…,an}, где aiÎV, (ai, ai+1)ÎE  с минимально возможным n.

Стандартным решением данной задачи является алгоритм волны. Базовым понятием в нем является волна степени n – множество вершин графа, до которых можно добраться из вершины a за n шагов и нельзя добраться за меньшее количество шагов. Будем называть это множество вершин Sn . Для точки a волной степени 0 является множество, состоящее из одной точки a.

Основная идея алгоритма заключается в том, что волной степени n+1, при известной волне степени n, будет являться множество точек Sn+1, состоящее изо всех точек, смежных к точкам из волны степени n, которые при этом не состоят в волнах степени меньше или равной n. Т.о. утверждается, что Sn+1= Sn+1.

Доказательство этого факта тривиально. Докажем, что Sn+1Ì Sn+1. Действительно, до точек  из Sn+1 можно добраться за n+1 шаг по построению. За меньшее количество шагов добраться нельзя, т.к. для любого i£n  выбранные точки не принадлежат Si .

Докажем, что Sn+1Ì Sn+1. Допустим, что найдется точка x, которую мы не включили в созданное множество Sn+1, но xÎSn+1. По условию xÎSn+1 имеем, что существует путь к данной точке за n+1 шагов, а значит, у данной точки есть смежная вершина из Sn. По определению Sn+1 , до точки x нельзя добраться за n или менее шагов, поэтому x должна быть включена в создаваемое множество, согласно его построению.

¢

 

Осталось завести два исполнителя множество S0 и S1 (например, на базе вектора, количество элементов в котором не превосходит количество вершин графа) и добавить в каждую вершину графа x дополнительную целую переменную lx, которая будет указывать длину кратчайшего пути от вершины a до данной вершины. В начальный момент S0 и S1 должны быть пусты, а все значения l=-1. Первая часть алгоритма состоит в определении для каждой вершины x, до которой можно добраться из a медленнее, чем до b, значения lx:

Алгоритм волны. Часть 1.

 


n=0; S1= {(a,0)}

Вечный цикл

n++

S0= S1

S1=Æ

Для всех xÎ S0

                                Для всех точек, смежных x: y, таких что ly==-1

                                ly=n; занести y в S1;

                                Если b==x  то ВЫЙТИ ИЗ ВЕЧНОГО ЦИКЛА

Если S1  пусто то ВЫЙТИ ИЗ ВЕЧНОГО ЦИКЛА

 


Если после выхода из алгоритма  S1  пусто, то это говорит о том, что из a в b добраться нельзя.

Иначе, во второй части алгоритма следует по результатам построений из первой части алгоритма определить кратчайший (один из кратчайших) путь из b в a. Для этого следует заполнить искомую последовательность {x1,…,xn}.

xn=b;  x1=a

Далее для каждого i от n до 3 ищется вершина xi-1, смежная к xi, такая что lx(i-1)==i-1. Такая вершина существует из соображений, приведенных выше.

¢

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

В каждой вершине можно хранить дополнительную информацию о том, откуда мы в нее пришли, тогда вторая часть алгоритма будет выполняться за время O(n), где n – длина минимального пути из a в b (в случае возможности дойти из a в b), или за время O(N) , где N – количество вершин в графе (в любом случае).

Приведем пример программы на С++ с использованием STL для решения данной задачи. Программа распечатывает найденный путь (номера вершин в обратном порядке) и длину пути.

 

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

struct SPoint{SPoint(){l=iback=-1;} double x,y; int l,iback;};

struct SEdge{int i0,i1;};

 

ifstream &operator>>(ifstream &f,SPoint &p){f>>p.x>>p.y; return f;}

ifstream &operator>>(ifstream &f,SEdge &p){f>>p.i0>>p.i1; return f;}

 

int main(void)

{vector<SPoint> p; vector<SEdge> e; vector<vector<int>> a; int l;

 vector<int> v0,v1;//== Sn S(n+1)

 int i0=0,i1=11;

 {SPoint P; ifstream f("vertex.txt"); while(f>>P)p.push_back(P);}

 {SEdge E; ifstream f("edges.txt"); while(f>>E)e.push_back(E);}

 //--

 a.resize(p.size());

 for(vector<SEdge>::iterator i=e.begin(); i!=e.end(); i++)

 {a[i->i0].push_back(i->i1);a[i->i1].push_back(i->i0);}

 //--

 for(v0.push_back(i0), p[i0].l=0, l=1; !v0.empty(); v0.swap(v1), l++, v1.clear())

  for(vector<int>::iterator i=v0.begin(); i!=v0.end(); i++)

   for(vector<int>::iterator j=a[*i].begin(); j!=a[*i].end(); j++)

    if(*j==i1)

    {

     cout<<"l="<<l<<endl;

     p[*j].iback=*i;

     for(int k=*j;k>=0;k=p[k].iback)cout<<k<<" ";cout<<endl;

     goto le;

    }

    else if(p[*j].l<0)

    {p[*j].l=l;p[*j].iback=*i;v1.push_back(*j);}

//--

    cout<<"can't find the way"<<endl;

le:

    getchar();

 return 0;

}

 

 

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

Теорема 1. Верны оценки для графа, состоящего из N вершин

1. Если в графе отсутствуют петли и кратные ребра, то алгоритм волны работает за время O(N2).

2. Если каждая вершина графа имеет не более M1  инцидентных ребер, то алгоритм волны работает за время O(M1 N).

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

Доказательство теоремы сводится к тому, что время работы алгоритма волны равно O(M+N) , где N – количество вершин, M – количество ребер в графе (точнее, не ребер, а пар смежных вершин, но в условиях теоремы это – одно и тоже). Последний факт следует из того, что каждое ребро при взятии смежной вершины в алгоритме может встретиться не более двух раз.

Чтобы получить более оптимистичную оценку введем несколько новых понятий.

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

Теорема 2.  Для любого конечного графа существует его геометрическое представление в R3.

Доказательство. Рассмотрим произвольный отрезок [a,b]Ì R3. Сопоставим всем вершинам графа различные точки на отрезке [a,b]. Сопоставим каждому ребру графа свою плоскость, проходящую через [a,b]. Плоскости, соответствующие ребрам, пересекаются только вдоль отрезка [a,b], поэтому в каждой плоскости можно нарисовать кривую, соединяющую вершины, инцидентные соответствующему ребру, которая не пересекается с другими построенными кривыми нигде, кроме как в вершинах графа.

¢

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

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

 Теорема 3. Для любого конечного планарного графа без кратных ребер и петель существует его плоская укладка.

Иногда в литературе последнее утверждение выступает в виде определения планарного графа, а не его свойства.

Геометрическое представление планарного графа разбивает плоскость на некоторое количество связных областей (одна из них - бесконечна). Эти области называются гранями.

Путем в графе называется такая последовательность {x1,…,xn} вершин графа, что для всех i: (xi,xi+1)ÎE.

Циклом в графе называется такой путь, что крайние вершины в нем совпадают. Т.е. последовательность {x1,…,xn} вершин графа называется циклом, если для всех i: (xi,xi+1)ÎE  и x1=xn.

Граф называется связным, если для любых двух вершин графа a и b существует путь по ребрам графа от a до b, т.е. существует последовательность {x1,…,xn} вершин графа, такая что x1=a, xn=b и для всех i: пара (xi, xi+1) инцидентна некоторому ребру графа.

Связный граф без циклов называется деревом. Вершины, инцидентные не более чем одному ребру дерева называются конечными вершинами. Иногда в литературе такие вершины называют листьями, но нам такое определение листьев неудобно. Отметим, что понятия ориентации ребер в этом определении нет!

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

Лемма 1. Любое конечное неориентированное дерево имеет плоскую укладку.

Доказательство. Возьмем произвольную вершину дерева. Поместим ее в точку плоскости с координатами (0,0) и назовем корнем дерева. Пусть ей инцидентно k ребер. Поместим вторые вершины, инцидентные данным ребрам в точки (-1,i). Каждой из вновь размещенных точек сопоставим полосу плоскости со сторонами, параллельными оси Y, не имеющую общих точек с полосами соседних точек. 

Пусть для каждой вершины x, помещенной на плоскость в точку с координатой y=-h найдутся lx парных ей вершин, которые еще не размещены на плоскости.  Будем называть эти вершины потомками вершины x, а вершину x – их родителем. Разобьем полосу, соответствующую вершине x на  lx непересекающихся полос и разместим в них потомков x на координате y=-h-1.

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

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

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

¢

 

Доказательство Леммы 1 одновременно служит конструктивным доказательством того, что верна следующая

Лемма 2. В любом конечном дереве можно ввести ориентацию, т.е. для ребер произвольного дерева можно задать ориентацию так, что дерево станет ориентированным.

Верна следующая известная теорема

Теорема 4 (формула Эйлера). Пусть задан связный планарный граф, имеющий в некотором геометрическом представлении p вершин, q ребер, r граней, тогда верна формула

p-q+r=2

 

               Лемма 3. Пусть в некотором графе p вершин и q ребер, то  в графе содержится не менее p-q связных компонент. Если в графе нет циклов, то в графе ровно p-q связных компонент. Если в графе есть циклы, то в графе строго больше p-q связных компонент.

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

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

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

Следствием Леммы 3 является простой критерий наличия циклов в графе:

 p-q=количеству связных компонент в графе Û в графе нет циклов.

В частности, для связного графа мы получаем, что p-q=1 Û в графе нет циклов.

Доказательство формулы Эйлера. Исходя из леммы, получаем, что теорема Эйлера верна для деревьев. Действительно, по Лемме 1, каждое дерево с конечным числом вершин имеет плоскую укладку. Количество граней в этой укладке равно1 (иначе существует хотя бы одна конечная грань, а значит существует последовательность ребер на ее границе, образующая цикл). Количество граней в геометрическом представлении дерева равно 1 и  в силу Леммы 3 

p-q+r=1+1=2.

Рассмотрим произвольный связный граф с циклами с q0 ребрами. По Лемме 3  p-q0>1. Зафиксируем p и предположим, что для всех q<q0 теорема доказана. Заметим, что для случая p-q=1 мы уже доказали теорему. По предположению, в графе есть цикл, возьмем одно ребро в этом цикле и исключим из графа. Ребро было в цикле графа, поэтому связность нарушена не была. Т.к. ребро содержалось в цикле, то оно было общим для двух граней, поэтому при исключении ребра количество граней и количество ребер уменьшились на 1. По предположению индукции для урезанного графа теорема выполняется, следовательно, она выполняется и для исходного графа.

¢

Рассмотрим планарный граф без кратных ребер и петель, в каждой связной компоненте которого есть хотя бы три ребра. В его плоской укладке для каждой грани i количество ребер на ее границе qi³3. Т.о. имеем

S qi ³ 3r

С другой стороны каждое ребро принадлежит не более, чем двум граням, поэтому

2q ³ S qi

Итого имеем

2q ³3r

r £ 2/3 q.

Тогда по формуле Эйлера, примененной для i-ой связной компоненты графа, имеем:

qi=pi+ri-2£ pi+2/3 qi -2.

qi/3£pi-2

qi£3pi

А значит и для всего графа

q£3p

В силу последнего соотношения верна следующая

Терема 5. Для случая планарного графа без кратных ребер и петель, состоящего из N вершин, алгоритм волны работает за время O(N).

 

Здесь случай количества ребер меньше 3 легко рассмотреть отдельно.

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

Терема 6. Для случая планарного графа без кратных ребер и петель, имеющего в плоском представлении p вершин, q ребер, r граней верны оценки

q£3p

r£2p

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

·         количество ребер для каждой такой компоненты строго меньше количества ее вершин;

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

 

 

Представление графа в памяти ЭВМ

Пусть имеется граф G=(V,E), имеющий N вершин и M ребер. Вершинам и ребрам можно сопоставить их номера от 1 до N и от 1 до M, соответственно. Рассмотрим различные варианты хранения данных об этом графе. Отметим, что для работы с графом требуются следующие операции

 

Массив ребер

Для хранения информации о графе можно использовать массив ребер, в каждом элементе которого хранятся номера вершин, инцидентных ребру

#typedef  MMax 100

int edges[MMax][2], n_edges;

здесь предполагается, что в графе содержится не более MMax ребер;

Имеем следующие времена выполнения интересующих нас операций

 

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

Для хранения информации о графе можно использовать матрицу смежности из N строк и N столбцов, в (i,j) – элементе которой хранится количество ребер, инцидентных паре вершин с номерами i  и  j.

Имеем следующие времена выполнения интересующих нас операций

 

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

Для хранения информации о графе можно использовать матрицу инцидентности из N строк и М столбцов, в (i,j) – элементе которой хранится 1, если вершина i инцидентна ребру j, и 0 – если нет.

Имеем следующие времена выполнения интересующих нас операций

 

Списки смежных вершин

Для хранения информации о графе можно для каждой вершины хранить множество смежных вершин. Множество можно реализовать либо в виде массива:

#typedef  NMax 100

typedef struct CVertex1_

{

  int AdjacentVertices[NMax];

  int NAdjacentVertices;

} CVertex1;

CVertex1 vertices[NMax];

здесь предполагается, что в графе содержится не более NMax вершин;

либо в виде списка:

#typedef  NMax 100

typedef struct CAdjVertex_

{

  int i;                         //номер текущей вершины

  int i_next;                //номер следующей вершины

} CAdjVertex;

typedef struct CVertex2_

{

CAdjVertex *AdjacentVerticesList_Head; //голова списка  смежных вершин                             int i;             //номер текущей вершины

} CVertex2;

CVertex2 vertices[NMax];

 

Т.о. в каждой вершине графа будет храниться вектор или список смежных вершин к данной вершине.

Имеем следующие времена выполнения интересующих нас операций

Реберный список с двойными связями (РСДС) (для плоской укладки планарных графов)

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

typedef struct SEdge_

{

 int vertex0, vertex1;

 int edge0,edge1;

 int face0,face1;

}SEdge;

    здесь vertex0, vertex1 – номера первой и второй вершины ребра. Порядок вершин задает ориентацию. edge0 – номер первого ребра (в массиве элементов SEdge), выходящего из вершины vertex0, взятого против часовой стрелки (при обходе ребер из вершины vertex0), edge1 – первое ребро, выходящее из вершины vertex1, взятое против часовой стрелки (при обходе ребер из вершины vertex1). face0 – номер грани, находящейся слева от направленного отрезка (vertex0, vertex1), face1 – номер грани, находящейся справа от направленного отрезка (vertex0, vertex1).

Вместо структуры можно использовать массив из шести целых чисел.

На следующем рисунке показан пример графа. Стрелками на ребрах указан порядок вершин в узлах РСДС, соответствующих ребрам. Стрелками между ребрами указаны ссылки на ребра из соответствующих узлов РСДС.

 

Описание: Описание: Описание: Описание: Описание: Описание: Описание: Описание: Описание: Описание: Описание: Описание: Описание: p1

Для данного графа РСДС будет представлен следующим массивом улов:

{

{1,2, 5,2, 1,4},

{2,4, 1,7, 1,4},

{1,3, 1,4, 4,2},

{3,4, 6,5, 3,2},

{1,4, 3,2, 2,1},

{5,3, 7,3, 3,4},

{4,5, 4,6, 3,4}

}

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