Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

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

На главную Математический раздел Криптография и т.д. Новости

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

Пусть есть граф с n вершинами, пронумерованными числами от 1 до n. Составляется матрица A размера n x n со следующими правилами для элементов. I. Если элемент не на диагонали, то элемент (i, j) равен: a) 1, если вершины i и j соединены ребром (для неориентированных графов) или в вершину j заходит дуга из вершины i (для ориентированных графов); b) 0, если условие a не выполнено. II. Если элемент на диагонали (i=j), он равен единице, если вершина i имеет петлю (дугу или ребро с исходом и заходом в одну и ту же вершину), и 0, если петли нет. Эта матрица и называется матрицей смежности.

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

Заметим, что для одного и того же графа может быть не одна матрица смежности - это видно, если менять нумерацию вершин.

Когда матрица смежности симметрична?

Нетрудно заметить, что если граф неориентированный, матрица смежности симметрична относительно главной диагонали, то есть элементы (i, j) и (j, i) равны. Стало быть, можно хранить не всю матрицу смежности, а лишь её верхний треугольник (включая диагональ):

Для ориентированных графов такой номер может и не пройти - матрица смежности тут может быть несимметричной.

Свойство степеней матрицы смежности

Сначала напомним, что такое степень матрицы. Квадрат матрицы A - произведение A на её же саму. Куб матрицы A - произведение квадрата матрицы A на матрицу A. И так далее. То есть степень m будет означать произведение степени m-1 матрицы A на саму матрицу A.

Если матрица смежности A возведена в степень m, то элемент (i, j) матрицы-степени показывает, сколько есть путей из вершины i в вершину j, состоящих ровно из m рёбер или дуг.

Рассмотрим примерчик.

Здесь из вершины 1 в вершину 2 есть три пути длины 2, поскольку элемент (1, 2) куба матрицы смежности равен 2. Первый путь: петля (1, 1) - петля (1, 1) - дуга (1, 2). Второй путь: дуга (1, 2) - дуга (2, 1) - дуга (1, 2). Как видим, в свойстве степеней матрицы смежности учитываются не только простые пути, но и те, где мы можем проходить через одно и то же ребро или дугу много раз.

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

Главное преимущество матрицы смежности перед другими способами представления графов: можно легко ответить на вопрос, если ли дуга (ребро) между заданными вершинами.

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

Обобщение на мультиграфы и взвешенные графы. Матрица весов

Мультиграф - граф, у которого некоторые вершины i, j могут быть соединены двумя или более рёбрами, или из одной вершины в другую может идти более одной дуги. Обобщение матрицы смежности для мультиграфа состоит в том, что вместо элементов, равных 1, пишется количество соответствующих рёбер (дуг) - теперь важен не только факт существования ребра или дуги, но и кратность. Пример матрицы смежности для мультиграфа:

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

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

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X