Справка

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

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

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

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

Граф из 3 соединённых вершин Граф с ориентированной дугой Граф из 4 вершин без дуг
       
0, 1, 1, 
1, 0, 1, 
1, 1, 0, 
0, 1, 
0, 0, 
0, 0, 0, 0, 
0, 0, 0, 0, 
0, 0, 0, 0, 
0, 0, 0, 0, 
Ссылка на граф Ссылка на граф Ссылка на граф

Использование Матрицы смежности в сервисе Граф Онлайн

Сервис Граф Онлайн предоставляет вам возможность создать Создать граф по матрице смежности.

Также вы можете редактировать существующую матрицу смежности. Для этого вам необходимо выбрать меню Граф -> Матрица смежности.

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

Формат ввода матрицы смежности

Вводя матрицу смежности вам необходимо руководствоваться следующими правилами:

  1. Матрица должна быть квадратная - число строк равно числу столбцов.
  2. Каждая новая строка вводится с новой строки.
  3. Каждое значение разделяется замятой (,)
  4. Вес дуг должен быть положительным числом. Значение 0 значит что дуги не существует.

А теперь рассмотрим основные ошибки ввода матриц смежности

Основные ошибки ввода матриц смежности

Неправильная матрица Причина ошибки Правильная матрица
       
5,5,5,5,5
5,5,5,5,5
5,5,5,5,5
Матрица не квадратная: число строк - 3, а число столбцов - 5
       
5,5,5,5,5
5,5,5,5,5
5,5,5,5,5
5,5,5,5,5
5,5,5,5,5
       
0,1,1,1,0,1,0,0,0
1,0,1,0,0,1,1,1,0
1,1,0,1,1,0,1,0,0
1,0,1,0,1,1,1,1,0
0,0,1,1,0,1,0,0,0
1,1,0,1,1,0,1,1,1
0,1,1,1,0,1,0,0,1
0,0,0,0,0,1,1,1,0
Матрица не квадратная: число строк - 8, а число столбцов - 9
       
0,1,1,1,0,1,0,0,0
1,0,1,0,0,1,1,1,0
1,1,0,1,1,0,1,0,0
1,0,1,0,1,1,1,1,0
0,0,1,1,0,1,0,0,0
1,1,0,1,1,0,1,1,1
0,1,1,1,0,1,0,0,1
0,0,0,0,0,1,1,1,0
0,0,0,0,0,0,0,0,0
       
1, 0, 0
1, 2, 0
-2, 1, 0
0, -2, 0
1, 3, 0
Матрица не квадратная, также содержит отрицательные значения
       
1, 0, 0
1, 2, 0
2, 1, 0
       
1 2,
1 3,
1 4,
4 5,
5 2,
6 3,
Введена не матрица смежности, а отношение между вершинами. Необходимо ввести матрицу смежности для этого графа.
       
0, 1, 1, 1, 0, 0, 
0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 1, 0, 
0, 1, 0, 0, 0, 0, 
0, 0, 1, 0, 0, 0, 
       
∞,10,9,10
10,∞,∞,∞
∞,5,∞.8
10,∞,∞,∞
Вместо символа ∞ используйте 0.
       
0,10,9,10
10,0,0,0
0,5,0.8
10,0,0,0
       
-, 8, -, 1, -, -, 
-, -, 4, 7, 2, -, 
-, -, -, -, 4, 2, 
-, -, 9, -, 7, -, 
-, -, -, -, -, 6, 
inf , -, -, -, -, -, 
Вместо символа - или inf используйте 0.
       
0, 8, 0, 1, 0, 0, 
0, 0, 4, 7, 2, 0, 
0, 0, 0, 0, 4, 2, 
0, 0, 9, 0, 7, 0, 
0, 0, 0, 0, 0, 6, 
0, 0, 0, 0, 0, 0,