Преимущества и недостатки каждого способа

Инцидентность и смежность в графах, матрицы смежности, матрицы инцидентности, списки инцидентности

Инцидентность вершин и рёбер графа, смежность вершин графа

Инцидентность — это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.

Для того, чтобы задать граф аналитически, множества V вершин графа и множества U рёбер графа, которые фигурировали в определении графа, будет недостаточно. Потребуется ещё и множество P троек вида (a, u, b) , указывающих какую пару a, b элементов множества вершин V соединяет тот или иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа. Вот мы и подошли к одному из первых понятий теории графов — инцидентности.

Понятие инцидентности — одно из главных при создании структур данных для представления графов в памяти ЭВМ, к которым мы перейдём после примера 1.

Пример 1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)

Решение. Распространённые ошибки — не заметить вершины графа, которые не соединены ни с одной другой вершиной, в том числе с самой собой, и не включить их во множество вершин графа, а также указать не все рёбра графа, соединяющие две вершины. Поэтому вершину f данного графа обязательно включаем во множество вершин графа V , а, рёбра 6 и 7, хотя они соединяют одну и ту же вершину саму с собой и обе не имеют направления, включаем во множество рёбер U .

Итак, задаём граф следующими множествами:

множество рёбер: U =

Смежность вершин графа — это когда две вершины графа соединены ребром.

Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.

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

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

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

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

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

Матрица смежности для неориентированного графа

Элемент матрицы смежности s ij неориентированного графа определяется следующим образом:

— равен единице, если вершины v i и v j смежны;

— равен нулю, если вершины v i и v j не смежны.

Если для элемента матрицы v ij имеет место i = j , то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 2. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1		1	1
2	1			1	1
3	1				1
4		1
5		1	1

Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.

Матрица смежности для ориентированного графа

Элемент матрицы смежности s ij ориентированного графа определяется следующим образом:

— равен единице, если из вершины v i в вершину v j входит дуга;

— равен нулю, если из вершины v i в вершину v j дуга не входит.

Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы v ij имеет место i = j , то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1		1
2		1
3	1
4		1
5		1	1

Таким образом, матрица смежности ориентированного графа не симметрична.

Матрица смежности для графа с кратными рёбрами

Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности s ij равен числу рёбер, соединяющих вершины v i и v j . Из этого следует, что если вершины v i и v j не соединены рёбрами, то элемент матрицы смежности s ij равен нулю.

Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1		3	2
2	3			1	1
3	2				1
4		1
5		1	1

Матрица смежности для взвешенного графа

В случае взвешенного графа элемент матрицы смежности s ij равен числу w, если существует ребро между вершинами v i и v j с весом w. Элемент s ij равен нулю, если рёбер между вершинами v i и v j не существует.

Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.

V	1	2	3	4	5
1		11	9
2	11			5	8
3	9				2
4		5
5		8	2

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

Матрица инцидентности H — это матрица размера n x m , где n — число вершин графа, m — число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы — рёбрам графа.

Матрица инцидентности для неориентированного графа

Элемент матрицы инцидентности для неориентированного графа h ij определяется следующим образом:

— равен единице, если вершина v i инцидентна ребру e j ;

— равен нулю, если вершина v i не инцидентна ребру e j .

Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

V	1-2	1-3	2-4	2-5	3-5
1	1	1
2	1		1	1
3		1			1
4			1
5				1	1

Матрица инцидентности для ориентированного графа

Элемент матрицы инцидентности для ориентированного графа h ij определяется следующим образом:

— равен минус единице, если вершина v i является началом ребра e j ;

— равен единице, если вершина v i является концом ребра e j ;

— равен нулю, если вершина v i не инцидентна ребру e j .

Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

V	1-2	1-3	2-4	2-5	3-5
1	1	-1
2	-1		-1	-1
3		1			-1
4			1
5				1	1

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

Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.

Список инцидентности одной вершины графа включает номера вершин, смежных с ней.

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

Пример 8. Составить списки инцидентности для графа, представленного на рисунке ниже.

Преимущества и недостатки каждого способа

Матрицы смежности и инцидентности целесообразнее использовать когда:

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

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

Списки инцидентности целесообразнее использовать когда:

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

На практике списки чаще используются в прикладных целях.

Источник

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

Матрица смежности — один из способов представления графа в виде матрицы.

Содержание

Определение

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i-й вершины графа в j-ю вершину.

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

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

Примеры

Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент » width=»» height=»»/> может считаться равным либо одному (как показано ниже), либо двум.

Граф	Матрица смежности
	$\begin<pmatrix data-lazy-src=$ 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ \end» width=»» height=»»/>

a_ij — число рёбер, связывающих вершины и , причем в некоторых приложениях при каждая петля (ребро $\<v_i, v_i\ data-lazy-src=$ » width=»» height=»»/> при некотором ) учитывается дважды.

Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

Свойства

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

Два графа G₁ и G₂ с матрицами смежности A₁ и A₂ являются изоморфными если и только если существует перестановочная матрица P, такая что

Из этого следует, что матрицы A₁ и A₂ подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны.

Степени матрицы

Если A — матрица смежности графа G, то матрица править] Структура данных

Матрица смежности и cписки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах

n^2

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

$\infty$

В алгоритмах, работающих со взвешенными графами (например в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих ребер. При этом на место отсутствующих ребер ставят некоторое специальное граничное значение (англ. sentinel ), зависящее от решаемой задачи, обычно 0 или .

Источник

Понятие и представление графа: матрица смежности, список смежности

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

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

Ну а более формально, граф — комбинация набора вершин и набора рёбер. Вершины — это города, а рёбра — дороги. Визуально граф можно представить так:

Этот граф состоит из 6 вершин, пронумерованных начиная с единицы, и 7 двухсторонних рёбер. Рёбра обычно записывают в виде пар вершин, которые они соединяют: $1$-$2$, $1$-$5$, $2$-$3$, $2$-$5$, $3$-$4$, $4$-$5$, $4$-$6$.

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

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

Граф, в котором все рёбра неориентированные, также называют неориентированным, а граф с ориентированными рёбрами, соответственно, ориентированным.

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

Пути и циклы

Путём в графе называется последовательность вершин, каждая из которых соединена со следующей ребром. Чаще всего под “путём” подразумевают простой путь, все вершины которого различны. Путь, который проходит через какую-либо вершину более одного раза называют сложным путём.

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

Приведём примеры на этом графе:

Из множества возможных простых путей самый длинный: $a — f — c — d — e — b — h$ (существуют и другие пути с такой же длиной).

Циклом является путь $b — c — d — e — b$ (выделен цветом). Можно начать и с любой другой вершины, например, $c — d — e — b — c$.

Кратные рёбра и петли

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

Красным выделены кратные рёбра, а синим — петли.

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

Связные графы

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

Одно из рёбер проведено штрихами. Если это ребро присутствует, то граф является связным. Если же его убрать, то связность теряется, граф разбивается на две части, друг с другом не связанные. Такие части называются компонентами связности.

Определение дерева

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

Дерево — это связный граф без циклов, петель и кратных рёбер.

Все изображённые графы являются деревьями:

Среди множества свойств деревьев можно выделить два самых известных:

Количество рёбер связано с количеством вершин формулой $E = V — 1$.
Между любой парой вершин существует ровно один путь.

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

Существует два основных способа представления графов в программировании. Один из них, матрица смежности, используется гораздо реже, но очень просто реализуется. Граф из $N$ вершин задаётся матрицей (двумерным массивом) $N * N$, в которой $g[i][j]$ — логическое значение, true или false , обозначающее, существует ли ребро из вершины $i$ в вершину $j$.

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

Преимущества матрицы смежности:

Сложность проверки наличия ребра между двумя вершинами: $O(1)$

Недостатки матрицы смежности:

Занимает $N^2$ памяти, что неприемлемо для достаточно больших графов.
Сложность перебора всех вершин, смежных с данной: $O(N)$

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

Гораздо чаще для представления графов используется список смежности. Его идея заключается в хранении для каждой вершины расширяемого массива (вектора), содержащего всех её соседей.

Решим ту же задачу с использованием списка смежности (и С++11 для for-each):

Если требуется также удалять рёбра, то вместо вектора нужно использовать std::set .

Преимущества списка смежности:

Использует $O(M)$ памяти, что оптимально.
Позволяет быстро перебирать соседей вершины.
Позволяет за $O(\log N)$ проверять наличие ребра и удалять его (при использовании std::set ).

Недостатки списка смежности:

При работе с насыщенными графами (количество рёбер близко к $N^2$) скорости $O(\log N)$ может не хватать (единственный повод использовать матрицу смежности).
Для взвешенных графов приходится хранить vector

> , что усложняет код.

brestprog

Олимпиадное программирование в Бресте и Беларуси

Источник

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

Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. Прежде чем отобразить граф через матрицу смежности, рассмотрим простой пример такой матрицы (рис. 1).

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

Слева на рисунке изображена все та же матрица смежности, имеющая размерность 4×4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа – того, представлением которого является матрица.

Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе – 0. Немного формализовав только что сказанное, получим: если из i в j существует ребро, то A[i][j]:=1, в противном случае A[i][j]:=0. Как видно, все элементы на главной диагонали равны нулю, это следствие отсутствия у графа петель. Но ни что не мешает, чтобы некоторые или все элементы главной диагонали были единицами.

В программе матрица смежности задается при помощи обычного двумерного массива, имеющего размерность n×n, где n – число вершин графа.

На языке C++, описать ее можно, например, так:

Источник