Справка

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

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

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

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

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

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

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

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

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

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

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

  1. Матрица должна содержать число строк равное количеству вершин и столбцов равное количеству ребер.
  2. Чтобы задать неориентированную дугу необходимо в строки, соответствующие начальной и конечной вершинам, поставить их вес.
  3. Чтобы задать ориентированную дугу необходимо в строки, соответствующие начальной вершине, поставить её вес, а в соответствующие конечной вершине, её вес со знаком минус.

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

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

Неправильная матрица Причина ошибки Правильная матрица
       
0,1,0
0,0,1
0,0,1
0,0,1
В первом столбце не задана начальная и конечная вершины. В 3 столбце задана дуга, соединяющая 3 вершины, такой формат не поддерживается.
       
1,0,0,0
0,1,0,1
0,1,1,0
0,0,1,1
       
1, 0, 0
1, 1
0,-1
Последний ноль в первой строке лишний
       
1, 0
1, 1
0,-1