38 lines
2.9 KiB
Markdown
Executable File
38 lines
2.9 KiB
Markdown
Executable File
Граф - это совокупность множеств (V, E), где:
|
||
$V=\{u_1,u_2,...,u_n\}$ - непустое множество вершин
|
||
$E=\{e_1,e_2,...,e_n\}$ - множество ребер (дуг)
|
||
каждое ребро $e_k$ - это неупорядоченая пара различных вершин $(u_i,u_j)$ множество E антирефлексивное симитричное отношение на множестве V.
|
||
|
||
### Основные определения
|
||
|
||
Если основное отношение не симметричное, то есть E - множество упорядоченных пар. То G - ориентированный граф.
|
||
|
||
Если отношение не антирефлексивное, то есть E - множество пар не обязательно различных вершин, то G - псевдограф (граф с петлями).
|
||
|
||
Если E - мультимножество, то G - мультиграф.
|
||
|
||
Если каждое ребро $(u_i,u_j)$ имеет числовую характеристику $p(u_i,u_j)$ называемую длиной или весом ребра то G - взвешаный граф.
|
||
|
||
В более общем случае ребро может иметь набор атрибутов, тогда G - нагруженный граф.
|
||
|
||
Пусть $e_k=(u_i,u_j)$, тогда:
|
||
$u_i,u_j$ - концы ребра $e_k$
|
||
$u_i$ и $u_j$ смежны
|
||
ребро $e_k$ инциндентно вершинам $u_i,u_j$
|
||
|
||
### Представление графов
|
||
1. Графический
|
||
2. Пересечение множеств
|
||
3. Матрица смежности. Это квадратный массив A размерности nxn. $A=\{a_{i,j}\},a_{i,j}=\begin{cases}0,\ если\ (u_i,u_j)\not\in \\ 1\ если\ (u_i,u_j)\in\end{cases}$
|
||
свойства матрицы смежности:
|
||
1. На главной диагонали - нули
|
||
2. симметрична относительно главной диагонали
|
||
3. Сумма числ в i строке равна сумме чисел в i столбце и равна $deg(u_i)$2
|
||
4. Матрица инцидентности. Это прямоугольный массив B размерности nxn.
|
||
$B=\{b_{i,j}\},b_{i,j}=\begin{cases}0,\ если\ ребро\ e_j\ не\ инциндентно\ u_i\\ 1\ если\ e_j\ инциндентно\ u_i\end{cases}$
|
||
Свойства матрицы инцидентности:
|
||
1. Сумма чисел в i - строке равна $deg(u_i)$
|
||
2. Сумма чисел а j - столбце равна 2
|
||
5. Списки смежности. Это одномерный массив C длины n, элементами которого являются списки. i - элемент массива содержит списков номеров вершин, смежных с вершиной $u_i$
|
||
6. $\sum^n_{i=i}deg(u_i)=2m$
|
||
7 |