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

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

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

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

Граф из 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

       
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