Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

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

.docx
Скачиваний:
38
Добавлен:
14.08.2013
Размер:
37.09 Кб
Скачать

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

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

Пример

Граф

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

Особенности данного представления

  • Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом.

  • В каждом столбце должны стоять две единицы, а все остальные символы - нули.