На этой странице вы можете задать матрицу смежности и построить по ней граф
© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2015 — 2019
Ответ или решение 1
а) Матрица смежности
A B C D
A 0 1 1 0
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0
Весовая матрица
A B C D
A _ 1 _ 2
B1 _ 4 _
C _ 4 _ 1
D 2 _ 1 _
б) Матрица смежности
A B C D
A 0 1 1 1
B 1 0 1 0
C 1 1 0 1
D 1 0 1 0
Весовая матрица
A B C D
A _ 1 3 4
B1 _ 1 _
C 3 1 _ 2
D 4 _ 2 _
в) Матрица смежности
A B C D
A 0 1 1 1
B 1 0 1 0
С 1 1 0 0
D 1 0 0 0
Весовая матрица
A B C D
A _ 1 2 3
B1 _ 4 _
C 2 4 _ _
D 3 _ _ _
г) Матрица смежности
A B C D
A 0 1 1 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0
Весовая матрица
A B C D
A _ 3 1 2
B 3 _ 1 _
C 1 1_ 4
D 2 _ 4 _
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. Прежде чем отобразить граф через матрицу смежности, рассмотрим простой пример такой матрицы (рис. 1).
Это двоичная квадратная матрица, т. к. число строк в ней равно числу столбцов, и любой из ее элементов имеет значение либо 1, либо 0. Первая строка и первый столбец (не входят в состав матрицы, а показаны здесь для легкости ее восприятия) содержат номера, на пересечении которых находится каждый из элементов, и они определяют индексное значение последних. Имея в наличии лишь матрицу такого типа, несложно построить соответствующий ей граф.
Слева на рисунке изображена все та же матрица смежности, имеющая размерность 4×4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа – того, представлением которого является матрица.
Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе – 0. Немного формализовав только что сказанное, получим: если из i в j существует ребро, то A[i][j]:=1, в противном случае A[i][j]:=0. Как видно, все элементы на главной диагонали равны нулю, это следствие отсутствия у графа петель. Но ни что не мешает, чтобы некоторые или все элементы главной диагонали были единицами.
В программе матрица смежности задается при помощи обычного двумерного массива, имеющего размерность n×n, где n – число вершин графа.
На языке C++, описать ее можно, например, так:
