Алгоритмы на графах
Граф называют связным графом, если существует путь из каждой вершины в любую другую вершину.
Несвязный граф состоит из множества связных компонент (подграфов).
Ациклический связный граф называется деревом.
Подграф связного графа, который содержит все вершины этого графа и представляет собой единое дерево,
называется остовным деревом.
9
Алгоритмы на графах
Графы, у которых присутствуют все ребра, называются
полными.
Дополнением графа G называется граф, который получается путем удаления из полного графа, имеющего тоже количество вершин, что и G, всех ребер исходного графа.
Полный подграф называется кликой.
|
0 |
|
0 |
|
|
|
5 |
|
|
||
5 |
1 |
6 |
1 |
||
|
|||||
|
|
|
|||
|
|
|
|
||
4 |
2 |
4 |
3 |
2 |
|
|
3 |
|
|
||
|
|
|
|
10
Алгоритмы на графах
Насыщенность графа – это показатель количества ребер относительно количества вершин.
Обычно ее полагают равной среднему значению степеней вершин графа (2*R/V, R – количество ребер, V - вершин).
Степень вершины – это количество инцидентных ей ребер.
Насыщенный граф – это граф, у которого количество ребер пропорционально квадрату вершин (V2), в противном случае граф является разреженным.
11
Алгоритмы на графах
Графы, ребра которых однонаправлены (ребро представляет упорядоченную пару вершин, т.е. возможность перехода только из первой во вторую) называются
ориентированными (орграфы).
Неориентированный граф – это граф, у которого имеется два ориентированных ребра в противоположных направлениях.
0 |
6 |
0 |
6 |
|
|||
1 |
2 |
1 |
2 |
|
3 |
|
3 |
5 |
4 |
5 |
4 |
|
12