Лабораторная работа 5

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

Графы и их основные свойства

Изучение методов сортировки данных

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

1 Теоретическая часть

Определение графа - Граф - это пара (V,E), где V - конечное непустое множество вершин, а E - множество неупорядоченных пар <u,v> вершин из V называемых ребрами. Говорят, что ребро s=<u,v> соединяет вершины u и v. Ребро s и вершина u (а также s и v) называются инцидентными, а вершины u и v - смежными. Ребра, инцидентные одной и той же вершине, также называют смежными. степень вершины равна числу ребер, инцидентных ей.

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

Путь, соединяющий вершины u и v, - это последовательность вершин v(0), v(1), ... , v(n) (n>=0) такая, что v(0)=u, u(n)=v и для любого i ( 0 <= i <= n-1 ) вершины v(i) и v(i+1) соединены ребром. Длина пути v(0), v(1), ... ,v(n) равна количеству его ребер т.е. n. Путь замкнут, если v(0) = v(n). Путь называется простым, если все его вершины различны. Замкнутый путь, в котором все ребра различны называется циклом. Простой цикл - это замкнутый путь, все вершины которого, кроме v(0) и v(n), попарно различны. Гамильтоновым называется граф, в котором существует простой цикл, содержащий все вершины графа (но не обязательно все его ребра).

Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины. Обод - это граф, вершины которого v(0), v(1), ..., v(n) ( n >= 2 ) можно занумеровать так, что для всех i (1<=i<=n-1) вершина v(i) соединена ребрами с v(i-1), v(i+1), вершина v(0) - c v(n), а других ребер нет.

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

Дополнением графа G называется граф G' с тем же множеством вершин что и у G, причем две различные вершины смежны в G' тогда и только тогда, когда они не смежны в G.

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

Ориентированный граф, или орграф, G = (V,E) отличается от графа тем что E - это множество упорядоченных пар (u,v) вершин u,v принадлежащих V, называемых дугами. Дуга (u,v) ведет от вершины u к вершине v. При этом вершину v называют преемником вершины u, а u - предшественником вершины v.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представляет собой матрицу m на n, где m - количество ребер или дуг графа ( орграфа ), а n - количество вершин. На пересечении i - ой строки и j - ого столбца проставляются значения по следующему правилу:

" 1 " - если i - ое ребро и j - ая вершина инцидентны ( для

орграфа - если i - ая дуга "входит" в j - ую вершину );

" 0 " - если i - ая дуга и j - ая вершина не инциндентны;

" -1 " - только в случае орграфа: если i - ая дуга "выходит"

из j - ой вершины );

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

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

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

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

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

Каждая ячейка этой матрицы может принимать только два значения: 1 или 0. Как вы уже догадались, ячейка несет в себе информацию о том, смежны вершины или нет.

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

во-первых, главная диагональ матрицы всегда заполнена нулями,

так как вершина не может быть смежна сама себе;

во-вторых, если наш граф неориентированный - то часть матрицы

под главной диагональю и над ней абсолютно идентичны.

На Pascal-е матрица смежности, как и матрица инцидентности чаще всего задается при помощи двумерного массива:

Matr_Sm :array [1..TopsCount,1..TopsCount] of byte,

либо

Matr_Sm :array [1..TopsCount,1..TopsCount] of boolean;

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

Список смежности и список инцидентности

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

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

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

Пусть задан граф на n вершинах и требуется создать некоторую структуру переменных в памяти ЭВМ, отображающую список смежности, составленный для данного графа. Для начала выясним, что будет представлять собой данная структура. Так как строка списка содержит номера вершин, то естественно предположить, что мы должны иметь некоторую цепочку динамических переменных целочисленного типа, связанных между собой. Такая связь обеспечивается использованием указателей, объединённых вместе с целочисленной переменной в запись ( Pascal: record ). Для того, чтобы обеспечить хранение входных указателей в такие цепочки, используется одномерный массив указателей, имеющий длину, равную количеству вершин графа. Признаком конца цепочки можно использовать какое-либо значение, не допускаемое при нумерации вершин ( например - "0" ), занесенное в целочисленную переменную последнего блока.

Для создания такой структуры предварительно необходимо сделать объявления такого рода:

Type

BlockPtr = ^BlockType;

BlockType = record

Number :integer;

Point :BlockPtr;

end;

Var

In_Ptr :array [1..TopsCount] of BlockPtr;

Создание цепочки в памяти осуществляется при вводе списка смежности при помощи процедуры New (BlockPtr_Type_Variable), где BlockPtr_Type_Variable - переменная типа BlockPtr.

2 Варианты заданий

1. Разработать процедуры ввода графа в виде матрицы инцидентности, матрицы смежности и списка смежности с возможностью корректировки введенных данных.

2. Разработать процедуры преобразования различных форм хранения графа: из матрицы смежности в список смежности и обратно.

3. Разработать процедуры преобразования различных форм хранения графа: из матрицы инцидентности в список смежности и обратно.

4. Реализовать алгоритм Дейкстры.

5. Реализовать алгоритм преобразования матрицы смежности в матрицу достижимостей (алгоритм Флойда-Уоршелла).