Матрица инцидентности неориентированного графа.
Матрица инцидентности графа
Матрица достижимости ориентированного графа.
Случай орграфа ничем не отличается от случая неориентированного графа. Если G – орграф с р вершинами и А – его матрица смежности, то элемент матрицы Ап равен числу ориентированных маршрутов длины п, соединяющих вершину vi с вершиной vj.
Граф G сильно связен тогда и только тогда, когда каждый элемент его матрицы достижимости равен 1.
Пусть – неориентированный граф с р вершинами и q ребрами. Произвольно переномеруем его вершины и ребра.
Определение. Матрицей инцидентности графа называется матрица с р строками (каждая строка соответствует одной из вершин графа) и q столбцами (каждый столбец соответствует одному из ребер графа), элементы которой определяются правилом
Пример графа и его матрицы инцидентности приведен на рис. 11
j i | |||||||||
Рис. 11