что такое матрица смежности графа

Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)

Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор

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

Взвешенный граф (коротко)

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

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

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

Перед чтением материала рекомендуется ознакомится с предыдущей статьей, о смежности и инцидентности, где данные определения подробно разбираются.

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

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

Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Матрица (назовем ее 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-ой строки равна степени вершины.

Одной из особенностей данной матрицы является то, что в столбце может быть только две ненулевых ячейки. Так как у ребра два конца.

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

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

В виде списка это будет выглядеть так:

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

Так как здесь рассматривается смежность, то здесь не обойдется без дублирования вершин. Поэтому сумма длин всех списков считается как:

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

Сумма длин всех списков:

Со списком инцидентности все просто. Вместо вершин в список (массив) вы вставляете рёбра и потом делаете ссылки на те вершины, с которыми он связан.

К недостатку списка смежности (инцидентности) относится то что сложно определить наличие конкретного ребра (требуется поиск по списку). А если у вас большой список, то удачи вам и творческих успехов! Поэтому, чтобы работать максимальной отдачей в графе должно быть мало рёбер.

Взвешенность графа

К примеру, возьмем граф с весами на ребрах:

И сделаем матрицу смежности:

В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.

Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.

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

Если заметили ошибку или есть предложения пишите в комментарии.

Источник

Что такое матрица смежности графа

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

Классификация графов

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

В несвязном графе существует хотя бы одна вершина, не связанная с другими.

Графы также подразделяются на

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

В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.

Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

Способы представления графа

Граф может быть представлен (сохранен) несколькими способами:

Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.

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

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

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

В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.

Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.

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

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

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

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

Алгоритмы обхода графов

Основными алгоритмами обхода графов являются

Поиск в ширину подразумевает поуровневое исследование графа:

Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
Каждая вершина может находиться в одном из 3 состояний:

Фиолетовый – рассматриваемая вершина.

Применения алгоритма поиска в ширину

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

Реализация на C++ (с использованием очереди STL)

Результат выполнения

Задача поиска кратчайшего пути
Реализация на С++

Поиск в глубину – это алгоритм обхода вершин графа.

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

Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:

Каждая вершина может находиться в одном из 3 состояний:

Фиолетовый – рассматриваемая вершина.

Применения алгоритма поиска в глубину

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

Реализация на C++ (с использованием стека STL)

Результат выполнения

Задача поиска лексикографически первого пути на графе.
Реализация на C++

Результат выполнения

Поиск в глубину также может быть реализован с использованием рекурсивного алгоритма.

Реализация обхода графа в глубину на C++ (с использованием рекурсии)

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник