Инцидентность и смежность в графах, матрицы смежности, матрицы инцидентности
- Инцидентность и смежность в графах
- Матрицы смежности
- Матрицы инцидентности
- Списки инцидентности
- Преимущества и недостатки каждого способа
Инцидентность — это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.
Для того, чтобы задать граф аналитически, множества V вершин графа и
множества U рёбер графа, которые фигурировали в определении графа, будет недостаточно. Потребуется
ещё и множество P троек вида (a, u, b),
указывающих какую пару a, b элементов множества вершин V соединяет тот или
иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа.
Вот мы и подошли к одному из первых понятий теории графов —
Понятие инцидентности — одно из главных при создании структур данных для представления графов в памяти ЭВМ, к которым мы перейдём после примера 1.
Пример 1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)
Решение. Распространённые ошибки — не заметить вершины графа, которые не соединены ни с одной другой вершиной, в том числе с самой собой, и не включить их во множество вершин графа, а также указать не все рёбра графа, соединяющие две вершины. Поэтому вершину f данного графа обязательно включаем во множество вершин графа V, а, рёбра 6 и 7, хотя они соединяют одну и ту же вершину саму с собой и обе не имеют направления, включаем во множество рёбер U.
Итак, задаём граф следующими множествами:
множество вершин: V = {a
, b, c, d, e, f}множество рёбер: U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
множество инциденций: P = {(b, 1, a), (b, 2, a), (a, 3, b), (b, 4, b), (b, 5, b), (c, 6, c), (c, 7, c), (b, 8, d), (d, 8, b), (b, 9, d), (b, 10, e), (b, 11, e), (e, 11, b)}
Смежность вершин графа — это когда две вершины графа соединены ребром.
Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.
В связи с широким применением графов в программировании и информационных технологиях вообще возникает вопрос о представлении графа в виде структуры данных. Различные способы представления графов в памяти компьютера отличаются объёмом занимаемой памяти и скоростью выполнения операций над графами.
Наиболее часто используются три такие структуры данных — матрица смежности, матрица инцидентности и список инцидентности.
Матрица смежности, как и матрица инцидентности, позволяет установить множество вершин,
соседних с заданной (то есть рассматриваемой в конкретной задаче), не прибегая к полному просмотру всей
матрицы.
Матрица смежности S — это квадратная матрица, в которой и число строк, и число столбцов равно n — числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.
Матрица смежности для неориентированного графа
Элемент матрицы смежности sij неориентированного графа определяется следующим образом:
— равен единице, если вершины vi и vj смежны;
— равен нулю, если вершины vi и vj не смежны.
Если для элемента матрицы vij
имеет место i = j, то есть элемент находится на диагонали,
то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.
Пример 2. Составить матрицу смежности для графа, представленного на рисунке ниже.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 |
| 3 | 1 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Таким образом, матрица смежности неориентированного графа
симметрична относительно главной диагонали.
Матрица смежности для ориентированного графа
Элемент матрицы смежности sij ориентированного графа определяется следующим образом:
— равен единице, если из вершины vi в вершину vj входит дуга;
— равен нулю, если из вершины v
Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы vij имеет место i = j, то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.
Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Таким образом, матрица смежности ориентированного графа
не симметрична.
Матрица смежности для графа с кратными рёбрами
Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности sij
равен числу рёбер, соединяющих вершины
Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 3 | 2 | 0 | 0 |
| 2 | 3 | 0 | 0 | 1 | 1 |
| 3 | 2 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Нет времени вникать в решение? Можно заказать работу!
Матрица смежности для взвешенного графа
В случае взвешенного графа элемент матрицы смежности sij
равен числу w, если существует ребро между вершинами vi и vj с весом w.
Элемент sij
равен нулю, если рёбер между вершинами vi и vj не существует.
Пример 5.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 11 | 9 | 0 | 0 |
| 2 | 11 | 0 | 0 | 5 | 8 |
| 3 | 9 | 0 | 0 | 0 | 2 |
| 4 | 0 | 5 | 0 | 0 | 0 |
| 5 | 0 | 8 | 2 | 0 | 0 |
Матрица инцидентности H — это матрица размера n x m,
где n — число вершин графа, m — число рёбер графа.
Обычно в матрице инцидентности
строки соответствуют вершинам графа, а столбцы — рёбрам графа.
Матрица инцидентности для неориентированного графа
Элемент матрицы инцидентности для неориентированного графа hij определяется следующим образом:
— равен единице, если вершина vi инцидентна ребру ej;
— равен нулю, если вершина vi не инцидентна ребру ej.
Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
Ответ.
| V | 1-2 | 1-3 | 2-4 | 2-5 | 3-5 |
| 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 |
Матрица инцидентности для ориентированного графа
Элемент матрицы инцидентности для ориентированного графа hij определяется следующим образом:
— равен минус единице, если вершина vi является началом ребра ej;
— равен единице, если вершина vi является концом ребра ej;
— равен нулю, если вершина vi
не инцидентна ребру ej.
Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
Ответ.
| V | 1-2 | 1-3 | 2-4 | 2-5 | 3-5 |
| 1 | 1 | -1 | 0 | 0 | 0 |
| 2 | -1 | 0 | -1 | -1 | 0 |
| 3 | 0 | 1 | 0 | 0 | -1 |
| 4 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 |
На сайте есть пример реализации на языке программирования С++ алгоритма обхода
в глубину графа, представленного матрицей инцидентности.
Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.
Список инцидентности одной вершины графа включает номера вершин, смежных с ней.
Ссылки на начало этих списков образуют одномерный массив, индексами которого служат номера вершин графа.
Пример 8. Составить списки инцидентности для графа, представленного на рисунке ниже.
Ответ.
1:2→3
2:1→4→5
3:1→5
4:2
5:2→3
Матрицы смежности и инцидентности целесообразнее использовать когда:
- число вершин графа невелико;
- число рёбер графа относительно большое;
- в алгоритме часто требуется проверять, соединены ли между собой две вершины;
- в алгоритме используются фундаментальные понятия теории графов, например, связность графа.
Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.
Списки инцидентности целесообразнее использовать когда:
- число вершин графа велико;
- число рёбер графа относительно невелико;
- граф формируется по какой-либо модели;
- во время действия алгоритма часто требуется модифицировать граф;
- в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.
На практике списки чаще используются в прикладных целях.
| Назад | Листать | Вперёд>>> |
Весь блок «Теория графов»
Теория графов: основные понятия и задачи
Основные виды графов
Математические модели в виде графов. Дерево решений. Дерево игры
Виды вершин и рёбер графа.
Маршруты, цепи, циклы в графах
К началу страницы
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности) / Хабр
Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
В этой статье:
Матрица смежности
Матрица инцидентности
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов, в которых число ребер близко к максимально возможному числу ребер (у полного графа).
Другой способ называется списком. Данный способ больше подходит для более разреженных графов, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа).
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 или -∞.
Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.
Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.
Если заметили ошибку или есть предложения пишите в комментарии.
Представление взвешенного графа с помощью матрицы смежности в JavaScript | by Regina Furness
Чтение: 4 мин.
·
22 февраля 2021 г.
Photo by Omar Flores on Unsplash Недавно я наткнулся на реализацию неориентированного взвешенного графа с использованием матрицы смежности.
До этого я привык видеть графы, представленные с помощью списков смежности. Чтобы сохранить внимание к этому блогу, сегодня я буду писать только о представлении взвешенного графа с помощью матрицы смежности и предполагаю, что читатель уже знает, как представлять граф с помощью списка смежности. К концу этого блога ваша цель будет заключаться в том, чтобы вы могли построить Класс Graph , использующий матрицу смежности.
Квадратная матрица
Матрица смежности — это квадратная матрица, которая используется для представления ребер графа. Квадратная матрица представляет собой двумерный массив, массив, который содержит массивы, все равные ему по размеру. Например:
[[0,0,0]
[0,0,0]
[0,0,0]]
Основной массив содержит 3 массива, которые также имеют длину 3. Это квадратная матрица.
Матрица смежности
Итак, чтобы представить граф как матрицу смежности, мы будем использовать пересечения столбцов и строк для представления ребра.
Для невзвешенного графа это пересечение будет просто иметь значение 1, чтобы представить ребро между двумя вершинами. Для взвешенного графика мы просто укажем вес как значение на этом пересечении. Возьмем этот неориентированный взвешенный граф:
Сначала давайте просто посмотрим на это, представленное в виде сетки, чтобы вы могли понять, что я имею в виду, когда говорю «столбец» и «строка».
A B C D
A 0 2 3 0
B 2 0 0 2
C 3 0 0 6
D 0 2 6 0
Теперь в виде фактической матрицы:
[[0, 2, 3, 0], 9 0017 [2, 0, 0, 2],
[3, 0, 0, 6],
[0, 2, 6, 0]]
Вы можете видеть, что неориентированный граф будет симметричным сверху слева направо снизу диагональ. Это означает, что если у нас есть две вершины, i и j, которые соединены ребром, это означает, что matrix[i][j] будет равно matrix[j][i] .
Начнем с конструктора нашего класса.
Отныне весь код будет находиться внутри этого тела класса.
Мы инициализируем его размером нашего будущего графа. Помните, что размер вашего графа должен быть равен количеству вершин в вашем графе.
Теперь нам нужно уметь:
- Добавить вершину
- Удалить вершину
- Добавить ребро
- Удалить ребро
- Распечатайте нашу матрицу смежности
Давайте начнем с добавления ребра, предполагая, что мы инициализировали наш граф с достаточным пространством для размещения всех наших вершин.
Наши вершины представлены индексами нашей матрицы. Итак, нам просто нужно проверить, что ни одна из них не выходит за пределы нашей матрицы, и что они не являются одной и той же вершиной. После этого мы просто присваиваем весам this.matrix[vertex1][vertex2] и this.matrix[vertex2][vertex1] .
Удаление ребра очень похоже.
Мы проверяем правильность вершин, и если да, то просто сбрасываем их на 0.
Теперь нам нужно добавить вершину в нашу матрицу.
Сначала мы увеличиваем размер, затем запихиваем пустой массив в нашу матрицу. Нам нужно добавить 0 в ранее существовавшие массивы и в то же время заполнить наш новый массив нулями.
Теперь мы можем добавить вершину, поэтому нам нужно иметь возможность удалить вершину.
Здесь все немного сложнее. Сначала мы проверяем правильность заданной вершины (должна быть в пределах матрицы). Затем нам нужно сдвинуть каждый элемент в каждой строке влево на 1, записав вершину, которую мы удаляем. Это позаботится о наших рядах! Нам также нужно сдвинуть каждый элемент вверх на единицу поверх записи столбца, представляющего нашу вершину. Наконец, мы удаляем пустой массив и уменьшаем размер.
Теперь нам просто нужно напечатать нашу матрицу смежности.
Красиво и просто. Очень похоже на то, как мы инициализируем нашу матрицу смежности. Мы просто идем по строкам, добавляя каждый элемент в строку для вывода!
Когда я впервые увидел граф, представленный матрицей смежности, я испугался.
Когда я начал программировать, это было не так уж сложно понять. Я обнаружил, что тот факт, что он был ненаправленным, на самом деле упростил задачу. Использование матрицы смежности занимает намного больше места, чем просто использование списка смежности, особенно если ваши ребра разрежены. Однако у него есть преимущество постоянного поиска, чтобы увидеть, есть ли ребро между двумя вершинами. Тем не менее, я рад, что теперь знаю оба наиболее распространенных способа представления графика в JavaScript! 9{-\фракция{1}{2}}
$$
, где $D$ — матрица степеней, а $A$ — матрица смежности. Тогда вроде как делаем
$$ \шляпа{A} X W $$ где $X$ — данные узла, а $W$ — весовая матрица для создания нового графа.
В чем причина предварительной обработки матрицы смежности с использованием матрицы степеней? Почему мы не можем просто сделать $AXW$?
- нейронные сети
- граф нейронная сеть
$\endgroup$
3 9Т х} $$
Это работает, потому что $A$ (и, следовательно, $\tilde A$) симметрична, что является одним из предположений, сформулированных в статье.