МАТРИЧНЫЕ СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ
Дата добавления: 2015-07-23 ; просмотров: 4168 ; Нарушение авторских прав
ЛАБОРАТОРНАЯ РАБОТА №8
Целью работы является изучение матричных способов представления графов.
2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования автоматов, логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной оптимизации.
2.1 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Граф G задается множеством точек или вершин x1,x2. xn (которое обозначается через X) и множеством линий или ребер a1,a2,…,an (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой
(X, А).
Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (орграф) (рисунок 1(а)). Если ребра не имеют ориентации, то граф называется неориентированным (неорграф) (рисунок 1(б)). В случае когда G=(X, А) является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как G=(X, А).
 |
Если дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рисунке 1(а) обозначение (x1,x2)относится к дуге a1, а (x2,x1) — к дуге a2.
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(X,Г).
Для графа на рисунке 1(а) имеем Г(x1)=<x2,x5>, т. е. вершины x2 и x5 являются конечными вершинами дуг, у которых начальной вершиной является x1.
В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рисунках 1(б) и 1(в)), предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рисунке 1(б), имеем Г(x5)=<x1,x3,x4>, Г(x1)=<x5>и др.
Поскольку прямое соответствие или образ вершины Г(xi)представляет собой множество таких вершин xjÎX, для которых в графе G существует дуга (xi,xj), то через Г -1 (xi) естественно обозначить множество вершин xk, для которых в G существует дуга (xk,xi). Такое отношение принято называть обратным соответствием или прообразом вершины. Для графа, изображенного на рисунке 1(а), имеем
Вполне очевидно, что для неориентированного графа Г -1 (xi)=Г(xi) для всех xiÎX.
Отображение Г(Г(xi)) записывается как Г 2 (xi). Аналогично «тройное» отображение Г(Г(Г(xi))) записывается как Г 3 (xi) и т. д. Для графа, показанного на рисунке 1(а), имеем:
Аналогично понимаются обозначения Г -2 (xi), Г -3 (xi) и т. д.
Дуги a=(xi,xj), xi¹xj, имеющие общие концевые вершины, называются смежными. Две вершины xi и xj называются смежными, если какая-нибудь из двух дуг (xi,xj) и (xj,xi) или обе одновременно присутствуют в графе. Так, например, на рисунке 2 дуги a1, a10, a3 и a6 как и вершины x5 и x3, являются смежными, в то время как дуги a1 и a5 или вершины x1 и x4 не являются смежными.
Число дуг, которые имеют вершину xi своей начальной вершиной, называется полустепенью исхода вершины xi, и, аналогично, число дуг, которые имеют xi своей конечной вершиной, называется полустепенью захода вершины xi.
Таким образом, на рисунке 2 полустепень исхода вершины x3, обозначаемая через deg + (x3), равна ½Г(x3)½=3, и полустепень захода вершины x3, обозначаемая через deg — (x3), равна ½Г -1 (x3)½=1.
Очевидно, что сумма полустепеней захода всех вершин графа, а также сумма полустепеней исхода всех вершин равны общему числу дуг графа G, т. е.
, (1)
где n — число вершин и m — число дуг графа G.
Для неориентированного графа G=(X,Г) степень вершины xi определяется аналогично — с помощью соотношения deg(xi) º½Г(xi)½=½Г -1 (xi)½.
Петлей называется дуга, начальная и конечная вершины которой совпадают. На рисунке 3, например, дуги a3 и a10 являются петлями.
2.2 МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ
2.2.1 МАТРИЦА СМЕЖНОСТИ
Пусть дан граф G, его матрица смежности обозначается через A=[aij]и определяется следующим образом:
Таким образом, матрица смежности графа, изображенного на рисунке 3, имеет вид
Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки xi матрицы дает полустепень исхода вершины xi, а сумма элементов столбца xi — полустепень захода вершины xi. Множество столбцов, имеющих 1 в строке xi есть множество Г(xi), а множество строк, которые имеют 1 в столбце xi совпадает с множеством Г -1 (xi).
Петли на графе представляют собой элементы, имеющие 1 на главной диагонали матрицы, например a22, a66 для графа, изображенного на рисунке 3.
В случае неориентированного графа матрица смежности является симметричной относительно главной диагонали (рисунок 4).
2.2.2 МАТРИЦА ИНЦИДЕНТНОСТИ
Пусть дан граф G с n вершинами и m дугами. Матрица инцидентности графа G обозначается через B=[bij] и является матрицей размерности n x m, определяемой следующим образом:
Для графа, приведенного на рисунке 3, матрица инцидентности имеет вид:
Поскольку каждая дуга инцидентна двум различным вершинам (за исключением случая, когда дуга образует петлю), то каждый столбец содержит один элемент, равный 1, и один — равный -1. Петля в матрице инцидентности не имеет адекватного математического представления (в программной реализации допустимо задание одного элемента bij=1).
Если G является неориентированным графом (рисунок 4), то его матрица инцидентности определяется следующим образом:
bij=1, если xi является концевой вершиной дуги aj;
Матрица инцидентности, как способ задания графов, успешно применяется при описании мультиграфов (графов, в которых смежные вершины могут соединяться несколькими параллельными дугами).
Не нашли то, что искали? Google вам в помощь!
Источник
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)
Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов, в которых число ребер близко к максимально возможному числу ребер (у полного графа).
Другой способ называется списком. Данный способ больше подходит для более разреженных графов, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа).
Перед чтением материала рекомендуется ознакомится с предыдущей статьей, о смежности и инцидентности, где данные определения подробно разбираются.
Матрица смежности
Но тем кто знает, но чуть забыл, что такое смежность есть краткое определение.
Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Матрица (назовем ее 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 или -∞.
Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.
Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.
Если заметили ошибку или есть предложения пишите в комментарии.
Источник
