yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.2  Способы задания графов

Дискретная математика

4.2  Способы задания графов

 

Множество вершин и множество рёбер для конечных графов задаются как правило перечислением. Возможно задание графа описанием отношения инцидентности.

 

1.Отношение инцидентности задано матрицей смежности:

- столбцы и строки матрицы - вершины графа;

- для смежных вершин - элемент матрицы - 1, для остальных - 0;

- для неориентированного графа эта матрица всегда симметрична;

- число рёбер равно числу единиц выше или ниже главной диагонали матрицы, включая и диагональ.

2.Отношение инцидентности задано матрицей инцидентности:

- столбцы матрицы соответствуют вершинам графа,а строки-рёбрам;

- если ребро e(i)  инцидентно  вершине  v(j),то  элемент  матрицы E(i,j)=1,в противном случае  E(i,j)=0.

Таким образом в каждой строке одна или две единицы, остальные  - нули (если петля, то две единицы).

Для ориентированного графа при заполнении матрицы:

E(i,j)=-1,если v(i)-начало ребра.

E(i,j)=1,если  v(i)-конец ребра.

E(i,j)=a(где a-любое число, кроме -1,1,0),если ребро-петля в вер-

шине v(i).

В остальных случаях E(i,j)=0.

 

3.Список рёбер.

---------T-----------¬

¦  e(i)  ¦   v1,vn   ¦       e(i)-ребра

+--------+-----------+ v1,vn-пара вершин, соединяемых ребрами.

¦  1.    ¦           ¦

¦  2.    ¦           ¦

¦ ...    ¦           ¦

L--------+------------

 

 

21