Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждой дуге ставится в соответствующем столбце: «1» в строке вершины x и «-1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».
Содержание
Пример [ править | править код ]
| Граф | Матрица инцидентности |
|---|---|
 |
( 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 ) <displaystyle <egin |
Строки соответствуют вершинам от 1 до 6, а столбцы — рёбрам e1–e7. Например, единицы во втором столбце во 2-й и 3-й строчках означают, что ребро e2 соединяет вершины 2 и 3.
На данной странице вы можете задать матрицу инцидентности и построить по ней граф
© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2015 — 2019
На рис. 1,2 изображено множество точек 
и множество линий 
, соединяющих эти точки, которые все вместе образуют граф 
.Если линии имеют стрелки, то граф называется ориентированным или орграфом 
(рис. 2).
Рис. 1. Граф 
. Рис. 2. Орграф 
.
Графы 
и 
можно представить в аналитической форме либо матрицей смежности 
,либо матрицей инцидентности 
.
Для нашего конкретного неориентированного графа 
матрицы 
и 
выглядят следующим образом:
Матрица смежности для неориентированного графа всегда симметрична.
Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1.
В матрице инцидентности сумма единиц по столбцам указывает на степень вершины vi. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа матрицы 
и 
выглядят существенно иначе:
В общем случае матрица смежности для ориентированного графа 
уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и —1, если дуга заходит в нее.
Матрица смежности и матрица инцидентности
Есть два стандартных способа представить граф G = (V,E)
– как набор списков смежных вершин
как матрицу смежности.
Первый обычно предпочтительнее, ибо дает более компактное представление разреженных графов– тех, у которых |E| много меньше |V| 2 .
Большинство стандартных алгоритмов используют именно это представление. Но в некоторых ситуациях удобнее пользоваться матрицей смежности – например, для плотных графов, у которых |EG| сравнимо с |VG| 2 .
Матрица смежности позволяет быстро определить, соединены ли две данные вершины ребром. Алгоритмы отыскания кратчайших путей для всех пар вершин, используют представление графа с помощью матрицы смежности.
Определение Матрицей смежностиграфа G = (V, E) называется квадратная булева матрицаAпорядкаn,элементы которой определяются следующим образом:
А – симметрическая матрица
На главной диагонали матрицы смежности всегда стоят 0.
Число единиц в строке равно степени соответствующей вершины.
Матрицей инцидентностиграфаGназывается булева матрица размера |V|´|G| вида
В каждом столбце матрицы ровно две единицы
Равных столбцов нет.
Например, на следующем рисунке граф задан графически, списком смежных вершин, матрицей смежности и матрицей инцидентности.
Загрузка...
