Меню

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



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

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

Бинарная матрица

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

matrix_smeghnost

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

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

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

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

Источник

Уроки 27 — 28 §17. Графы

Содержание урока

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

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

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

Единица на пересечении строки А и столбца В означает, что между вершинами А и В есть связь. Ноль указывает на то, что связи нет. Такая таблица называется матрицей смежности. Она симметрична относительно главной диагонали (см. закрашенные клетки в таблице).

Исследуйте матрицу смежности и сравните её с графом на рис. 3.17, б. Что означает единица на пересечении столбца С и строки С?

В этом графе есть петля — ребро , которое начинается и заканчивается в одной и той же вершине.

Читайте также:  5 1 Форма правления государства

Степенью вершины называют количество рёбер, с которыми связана вершина. При этом петля считается дважды (с вершиной связаны оба конца ребра!).

Подсчитайте по матрице смежности, сколько ребёр в графе. Определите степени всех вершин. Как вы рассуждали?

Строго говоря, граф — это математический объект , а не рисунок. Конечно, его можно нарисовать на плоскости (например, как на рис. 3.17, б), но матрица смежности не даёт никакой информации о том, как именно располагать вершины друг относительно друга. Для таблицы, приведённой выше, возможны, например, такие варианты (рис. 3.19).

Нарисуйте по матрице смежности (рис. 3.20) два разных изображения графа.

Граф имеет 4 вершины, причём каждая вершина связана рёбрами со всеми остальными. Нарисуйте этот граф. Сколько всего рёбер в этом графе?

Граф имеет N вершин, причём каждая вершина связана рёбрами со всеми остальными. Сколько всего рёбер в этом графе?

Граф имеет 4 ребра. Чему равна сумма степеней вершин в этом графе? Зависит ли она от количества вершин?

Граф имеет N рёбер. Чему равна сумма степеней вершин в этом графе?

Попробуйте нарисовать граф с пятью вершинами, где все вершины имеют степень 3. Получилось ли у вас? Почему?

Источник

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

Содержание урока

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

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

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

Единица на пересечении строки А и столбца В означает, что между вершинами А и В есть связь. Ноль указывает на то, что связи нет. Такая таблица называется матрицей смежности. Она симметрична относительно главной диагонали (см. закрашенные клетки в таблице).

Исследуйте матрицу смежности и сравните её с графом на рис. 3.17, б. Что означает единица на пересечении столбца С и строки С?

В этом графе есть петля — ребро , которое начинается и заканчивается в одной и той же вершине.

Степенью вершины называют количество рёбер, с которыми связана вершина. При этом петля считается дважды (с вершиной связаны оба конца ребра!).

Подсчитайте по матрице смежности, сколько ребёр в графе. Определите степени всех вершин. Как вы рассуждали?

Строго говоря, граф — это математический объект , а не рисунок. Конечно, его можно нарисовать на плоскости (например, как на рис. 3.17, б), но матрица смежности не даёт никакой информации о том, как именно располагать вершины друг относительно друга. Для таблицы, приведённой выше, возможны, например, такие варианты (рис. 3.19).

Читайте также:  Таблица для проверки зрения животные

Нарисуйте по матрице смежности (рис. 3.20) два разных изображения графа.

Граф имеет 4 вершины, причём каждая вершина связана рёбрами со всеми остальными. Нарисуйте этот граф. Сколько всего рёбер в этом графе?

Граф имеет N вершин, причём каждая вершина связана рёбрами со всеми остальными. Сколько всего рёбер в этом графе?

Граф имеет 4 ребра. Чему равна сумма степеней вершин в этом графе? Зависит ли она от количества вершин?

Граф имеет N рёбер. Чему равна сумма степеней вершин в этом графе?

Попробуйте нарисовать граф с пятью вершинами, где все вершины имеют степень 3. Получилось ли у вас? Почему?

Источник

Графы: представления, достижимость и связность

Матрица (таблица) смежности

Определение 9.5. Матрицей смежности ориентированного (или неориентированного ) графа G=(V,E) с n вершинам и V= < v1, . , vn> называется булева матрица AG размера n x n с элементами

a_<ij data-lazy-src=

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

Определение 9.7. Пусть G=(V,E) — ориентированный граф , v — вершина из V . Список смежности Lv для вершины v включает все смежные с ней вершины , т.е.

L_v = w_1, \ldots , w_k ,\ где \<w_1, \ldots , w_k\ data-lazy-src=