Способы задания графов.
Рассмотрим три способа задания графов: графический, аналитический и матричный.
1) Графический способ.
Вершины изображают точками на плоскости, а ребра – линиями, соединяющими соответствующие точки. Для изображения дуги используется линия со стрелкой, указывающей направление от начала к концу дуги.
На рисунке 12 изображен смешанный граф с вершинами v1, v2,¼, v6, ребрами e1, e2, e3, e5 и дугой e4. Смежные вершины v1, v2, инциденты ребру e1. Вершины v1, v3, инциденты параллельным ребрам e2 и e3. Вершине v4 инциденты петля e5 и дуга e4, причем v4 является началом дуги e4, а v5 – концом этой дуги. Степень вершины v1 равна 3, вершины v2 – 1, вершины v3 – 2, вершины v4 – 3, вершины v5 – 1, вершины v6 – 0. Таким образом, вершины v2 и v5 – висячие, а вершина v6 – изолированная. В случае дуги e4 точнее было бы говорить о полустепенях исхода и захода вершин v4 и v5, а именно: полустепень исхода вершины v4 равна 3, вершины v5 – 0, полустепень захода вершины v4 равна 2, вершины v5 – 1.
2) Аналитический способ.
3) Матричный способ.
Имеется несколько вариантов задать граф матрицей. Наиболее употребимыми являются матрица инциденций и матрица смежности.
а) Матрица инциденций – это прямоугольная матрица, число строк которой равно числу вершин, а число столбцов – числу дуг (ребер) графа. Элементы этой матрицы определяются следующим образом:
Таким образом, для графа на рисунке 12 матрица инциденций такова:
| e1 | e2 | e3 | e4 | e5 |
| v1 | ||||
| v2 | ||||
| I= | v3 | |||
| v4 | ||||
| v5 | -1 | |||
| v6 |
По этой матрице легко судить о наличии в графе параллельных ребер (два одинаковых столбца), петли (одна единица в столбце), дуги (значения разных знаков в столбце), изолированной вершины (нулевая строка), висячих вершин (одно ненулевое значение в строке).
б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так: 
. Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Так матрица смежности для графа на рисунке 12 такова:
| v1 | v2 | v3 | v4 | v5 | v6 |
| v1 | |||||
| v2 | |||||
| S= | v3 | ||||
| v4 | |||||
| v5 | |||||
| v6 |
По виду этой матрицы также несложно судить о наличии в графе кратных ребер, дуг, петель, висячих и изолированных вершин.
Дата добавления: 2015-10-19 ; просмотров: 17466 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ
Источник
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)
Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов, в которых число ребер близко к максимально возможному числу ребер (у полного графа).
Другой способ называется списком. Данный способ больше подходит для более разреженных графов, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа).
Перед чтением материала рекомендуется ознакомится с предыдущей статьей, о смежности и инцидентности, где данные определения подробно разбираются.
Матрица смежности
Но тем кто знает, но чуть забыл, что такое смежность есть краткое определение.
Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Матрица (назовем ее L) состоит из n строк и n столбцов и поэтому занимает n^2 места.
Каждая ячейка матрицы равна либо 1, либо 0;
Ячейка в позиции L (i, j) равна 1 тогда и только тогда, когда существует ребро (E) между вершинами (V) i и j. Если у нас положение (j, i), то мы также сможем использовать данное правило. Из этого следует, что число единиц в матрице равно удвоенному числу ребер в графе. (если граф неориентированный). Если ребра между вершинами i и j не существует, то ставится 0.
Для практического примера возьмем самый обыкновенный неориентированный граф:
А теперь представим его в виде матрицы:
Ячейки, расположенные на главной диагонали всегда равны нулю, потому что ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней только если мы не используем петли. То есть наша матрица симметрична относительно главной диагонали. Благодаря этому мы можем уменьшить объем памяти, который нам нужен для хранения.
С одной стороны объем памяти будет:
Но используя вышеописанный подход получается:
Потому что нижнюю часть матрицы мы можем создать из верхней половины матрицы. Только при условии того, что у нас главная диагональ должна быть пустой, потому что при наличии петель данное правило не работает.
Если граф неориентированный, то, когда мы просуммируем строку или столбец мы узнаем степень рассматриваемой нами вершины.
Если мы используем ориентированный граф, то кое-что меняется.
Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра.
Возьмем в этот раз ориентированный граф и сделаем матрицу смежности для него:
Если мы работаем со строкой матрицы, то мы имеем элемент из которого выходит ребро, в нашем случаи вершина 1 входит в вершину 2 и 8. Когда мы работаем со столбцом то мы рассматриваем те ребра, которые входят в данную вершину. В вершину 1 ничего не входит, значит матрица верна.
Если бы на главной диагонали была бы 1, то есть в графе присутствовала петля, то мы бы работали уже не с простым графом, с каким мы работали до сих пор.
Используя петли мы должны запомнить, что в неориентированном графе петля учитывается дважды, а в ориентированном — единожды.
Матрица инцидентности
Инцидентность – понятие, используемое только в отношении ребра и вершины: две вершины (или два ребра) инцидентными быть не могут.
Матрица (назовем ее I) состоит из n строк которое равно числу вершин графа, и m столбцов, которое равно числу ребер. Таким образом полная матрица имеет размерность n x m. То есть она может быть, как квадратной, так и отличной от нее.
Ячейка в позиции I (i, j) равна 1 тогда, когда вершина инцидентна ребру иначе мы записываем в ячейку 0, такой вариант представления верен для неориентированного графа.
Сразу же иллюстрируем данное правило:
Сумма элементов i-ой строки равна степени вершины.
При ориентированным графе, ячейка I (i, j) равна 1, если вершина V (i) начало дуги E(j) и ячейка I (i, j) равна -1 если вершина V (i) конец дуги E (j), иначе ставится 0.
Одной из особенностей данной матрицы является то, что в столбце может быть только две ненулевых ячейки. Так как у ребра два конца.
При суммировании строки, ячейки со значением -1, могут складываться только с ячейками, также имеющими значение -1, то же касается и 1, мы можем узнать степень входа и степень выхода из вершины. Допустим при сложении первой вершины, мы узнаем, что из нее исходит 1 ребро и входят два других ребра. Это является еще одной особенностью (при том очень удобной) данной матрицы.
Список смежности (инцидентности)
Список смежности подразумевает под собой, то что мы работаем с некоторым списком (массивом). В нем указаны вершины нашего графа. И каждый из них имеет ссылку на смежные с ним вершины.
В виде списка это будет выглядеть так:
Неважно в каком порядке вы расположите ссылку так как вы рассматриваете смежность относительно первой ячейки, все остальные ссылки указывают лишь на связь с ней, а не между собой.
Так как здесь рассматривается смежность, то здесь не обойдется без дублирования вершин. Поэтому сумма длин всех списков считается как:
Когда мы работаем с ориентированным графом, то замечаем, что объем задействованной памяти будет меньше, чем при неориентированном (из-за отсутствия дублирования).
Сумма длин всех списков:
Со списком инцидентности все просто. Вместо вершин в список (массив) вы вставляете рёбра и потом делаете ссылки на те вершины, с которыми он связан.
К недостатку списка смежности (инцидентности) относится то что сложно определить наличие конкретного ребра (требуется поиск по списку). А если у вас большой список, то удачи вам и творческих успехов! Поэтому, чтобы работать максимальной отдачей в графе должно быть мало рёбер.
Взвешенность графа
Взвешенный граф — это граф, в котором вместо 1 обозначающее наличие связи между вершинами или связи между вершиной и ребром, хранится вес ребра, то есть определённое число с которым мы будем проводить различные действия.
К примеру, возьмем граф с весами на ребрах:
И сделаем матрицу смежности:
В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.
Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.
Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.
Если заметили ошибку или есть предложения пишите в комментарии.
Источник
MT1100: Дискретная математика
Помимо геометрического (графического) и аналитического способов задания графов существует еще, как минимум, три эквивалентых им способа.
Матрицей смежности для графа %%G = (V, E)%% называется квадратная матрица %%A = (a_
$$ A = \begin
Матрица смежности для примера из «Основных понятий»
Списком ребер графа называется таблица, состоящая из двух столбцов, в которой на пересечении %%i%%-й строки и первого (левого) столбца записывается ребро %%e_i%%, а на пересечении %%i%% -й строки и второго (правого) столбца записываются вершины, инцидентные ребру %%e_i%%.
Для того, чтобы список ребер однозначно задавал граф, необходимо помимо списка ребер указать множество всех изолированных вершин этого графа.
| 1 | %%B, C%% |
| 2 | %%A, C%% |
| 3 | %%B, F%% |
| 4 | %%A, F%% |
| 5 | %%A, F%% |
| 6 | %%A, D%% |
| 7 | %%D, F%% |
| 8 | %%D, E%% |
| 9 | %%E, F%% |
| 10 | %%B, E%% |
| 11 | %%E, E%% |
Список ребер для примера из «Основных понятий»
Матрицей инцидентности для графа %%G = (V, E)%% называется матрица %%B = (b_
Для неориентированного графа %%b_
У матрицы инцидентности есть пара особенностей:
- в каждой строке должны стоять две единицы, а все остальные символы — нули;
- она не используется для графов с петлями.
$$ B = \begin
Матрица инцидентности для примера из «Основных понятий» с учетом удаления петли у %%E%%
Источник
