Матрица инцидентов
Еще один способ представить график - положить его в матрицу инцидентности. Матрица инцидентности представляет собой двумерный (2D) массив. Вообще говоря, матрица инцидентов связывает два разных класса объектов между двумя его измерениями. Такая матрица подобна матрице смежности. Тем не менее, строки и столбцы означают что-то еще здесь. В графах мы имеем ребра и узлы. Это будут наши «два разных класса объектов». Эта матрица будет содержать строки, в которых узлы и столбцы будут ребрами. Это означает, что мы можем иметь нечетное количество строк и столбцов. Каждый столбец будет представлять собой уникальный ребро. Кроме того, каждое ребро соединяет два узла. Чтобы показать, что существует ребро между двумя узлами, вы поместите 1 в две строки определенного столбца. Ниже приведен граф из 3 узлов с одним ребром между узлом 1 и узлом 3.
1Ниже приведен пример
---
1 | 1
2 | 0
3 | 1
incidence matrix с 4 ребрами и 4 узлами. Помните, что столбцы - это ребра, а строки - сами узлы. 1 2 3 4Ниже приведена реализация JavaScript того же самого.
--------
1 | 0 1 1 1
2 | 1 1 0 0
3 | 1 0 0 1
4 | 0 0 1 0
var incMat = [Чтобы создать ориентированный граф, используйте
[0, 1, 1, 1],
[1, 1, 0, 0],
[1, 0, 0, 1],
[0, 0, 1, 0]
];
-1 для края, оставляющего определенный узел, и 1 для края, входящего в узел. var incMatDirected = [Графики также могут иметь веса по краям. До сих пор у нас есть невзвешенные края, где только наличие и отсутствие ребра двоично (
[0, -1, 1, -1],
[-1, 1, 0, 0],
[1, 0, 0, 1],
[0, 0, -1, 0]
];
0 или 1 ). Вы можете иметь разные веса в зависимости от вашего приложения. Другой вес представлен как числа больше 1.Создайте матрицу инцидентности неориентированного графа с пятью узлами и четырьмя ребрами. Эта матрица должна быть в многомерном массиве. Эти пять узлов имеют отношения, следующие за отношениями. Первое ребро находится между первым и вторым узлами. Второе ребро находится между вторым и третьим узлами. Третий край находится между третьим и пятым узлами. И четыре края расположены между четвертым и вторым узлами. Все весовые коэффициенты ребер имеют один и порядок ребер.