Построить матрицу инцидентности по матрице смежности

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

В случае ориентированного графа каждой дуге ставится в соответствующем столбце: «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 <egin1&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\end>>

Строки соответствуют вершинам от 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| вида

В каждом столбце матрицы ровно две единицы

Равных столбцов нет.

Например, на следующем рисунке граф задан графически, списком смежных вершин, матрицей смежности и матрицей инцидентности.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector