1 1 1 1 1 1 1 1 1 1 Рейтинг 4.90 (45 голосов)

Теория графов. Матрица смежности онлайн.

Описание ненаправленного графа

 
Матрица инцидентности графа
Графическое представление ненаправленного графа
В виде строки

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

В различных областях иногда нужно определять взаимосвязи между различными объектами.  Связи между производствами, между денежными потоками и источниками этих денег, между сотрудниками для определения наиболее оптимальных психологических объединений, или для построения генеалогического древа.

Такие взаимосвязи можно представить в виде сети или графов.

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

Граф может рассматриваться как упорядоченное множество. Для наглядности элементы этого множества можно изобразить в виде точек, а связи между ними—в виде направленных (или ненаправленных) отрезков (называемых «ребрами»), связывающих эти точки. Мы говорим тогда о наглядно-геометрическом представлении графов. При этом важно лишь то, какие точки связаны друг с другом, длина же связующих отрезков не принимается во внимание. Этим способом можно описывать отношения, которые могут иметь место в жизни, например "необходимо для" , "в связи с", "зависит от" и тому подобное.

Даны два множества: множество узловых точек А и множество ребер Б. Если  между двумя узловми точками  А1 и А2 существует ребро Б1, то  говорят что ребро Б1 инцидентно узловым точкам А1 и А2. Таким образом, между элементами из А и Б устанавливаются отношения инцидентности.

Пример построения графа
 
При переводе графа в матричную форму нужно соблюдать следующие правила. 
 
Если существует ребро, ведущее из точки А в точку Б, то элемент матрицы АБ полагается равным 1, если же точки А и Б не связаны, то АБ = 0. При этом полагается, что ни одна точка не соединена сама с собой.
 
Таким образом мы получаем квадратную матрицу, которая называется матрицей инцидентности графа.
 
Хотелось бы заметить что в интернете много определений инцидентности, и в каждом примере  используется почему то какой то свой особенный алгоритм, и матрицы у всех получаются различные. Мы взяли для расчета матрицы информацию из книги Гильберт А. "Как работать с матрицами". 1977 года издания.
 
При вводе  данных наш бот не просит названия ребер. Он основывается на данных об узловых точках: какая точка и какие соседние точки доступны.
 

Синтаксис

Jabber: graf выражение

WEB: выражение

где,

Выражение - строка,  определяющая соответствие связей между узловыми точками, разделенная точкой с запятой.

A(B,C);C(F,A) и так далее

Примеры

Рассмотрим  наш граф 

Пишем

A связан только с B

B связан с точками C A D и F

ну и так далее. Смысл я надеюсь понятен.

и окончательный  запрос будет таким A(B);B(A,C,D,F);C(B,F,E);D(B,F);E(C,F);F(C,E)

Запрос избыточен, так как видно что некоторые ребра записаны дважды, но это не беда.

Сделано именно для упрощения ввода, что бы "не думалось" какие ребра вы ввели а какие еще нет. 

И получаем следующий результат  - это и будет матрицей инцидентности.

 

Если же Вам нужна обратная задача  - по матрице смежности построить граф, то Вам стоит обратится вот сюда Построить граф по матрице

 

\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \end{pmatrix} 

Теперь Вы, основываясь на этой матрице можете легко, определять связи между элементами.