Маршрут в графе (путь в орграфе) из вершины
i в вершину j – последовательность вершин и ребер (дуг), инцидентных двум соседним вершинам.
Путь = ориентированный маршрут.
Первая вершина последовательности – начальная вершина маршрута (пути). Последняя вершина последовательности – конечная вершина маршрута (пути). Остальные вершины последовательности – внутренние вершины маршрута (пути).
Длина маршрута (пути) – количество ребер (дуг) маршрута (пути).
Вес маршрута (пути) – сумма весов ребер (дуг) маршрута (пути).
Замкнутый маршрут (замкнутый путь) – маршрут (путь), у которого первая и последняя вершины совпадают.
В замкнутом маршруте (замкнутом пути) вхождение последней вершины не учитывается при подсчете числа вхождений вершин графа (орграфа) в маршрут (путь).
Простой маршрут (простой путь) – маршрут (путь) без повторяющихся вершин.
Цепь (орцепь) – маршрут (путь), в котором ребра (дуги) проходятся один раз.
Простая цепь (простая орцепь) – цепь (орцепь) без повторяющихся вершин.
Петля – цепь (орцепь), содержащая один узел и одно ребро (одну дугу).
Расстояние между двумя вершинами графа (орграфа) – длина кратчайшей цепи (орцепи) между этими вершинами.
Цикл – замкнутая цепь.
Контур – замкнутая орцепь.
Простой цикл (простой контур) – замкнутая простая цепь (простая орцепь) с совпадающими начальной и конечной вершинами.
Если две вершины соединены цепью, то существует простая цепь, соединяющая эти две вершины. Для этого надо в цепи удалить внутренние циклы.
Если две вершины соединены орцепью, то существует простая орцепь, соединяющая эти две вершины. Для этого надо в цепи удалить внутренние контуры.
Ациклический граф (орграф) – граф (орграф) без циклов (контуров).
Достижимость вершины
i из вершины j – существование маршрута из вершины j в вершину i.
Каждая вершина достижима сама из себя.
Рис.1. Граф.
Для графа на рис.1:
a (a,c) c (c,d) d (d,f) f (f,g) g (g,d) d (d,b) b и a (a,d) d (d,b) b – два различных маршрута из вершины a в вершину b, причем второй маршрут – простой маршрут, длина первого маршрута 4, а второго – 2;
a (a,d) d (d,f) f (f,b) b (b,d) d (d,g) g – цепь;
a (a,d) d (d,g) g – простая цепь;
a (a,g) g (g,b) b (b,d) d (d,f) f (f,g) g (g,d) d (d,a) a – цикл;
a (a,g) g (g,d) d (d,a) a – простой цикл.
Связный граф – граф, у которого любая пара вершин может быть соединена цепью.
Граф на рис.1 – связный граф.
Соотнесенный (ассоциированный) орграфу граф – граф, полученный из орграфа заменой дуг на ребра (рис.2).
Связный орграф – орграф, для которого соотнесенный граф связный.
|
 
1 2 |
|
Рис.2. |
1 - Ориентированный граф. |
| |
2 – Соотнесенный граф. |
Сильно связный орграф
– орграф, у которого любые две вершины взаимно достижимые одна из другой.
Рис.3. Граф.
Два графа равны, если равны множества вершин и множества ребер
.
Граф на рис.3 несвязный граф.
Собственный подграф – подграф, не равный исходному графу
.
Компонента связности –
связный подграф, не являющийся собственным подграфом никакого другого связного подграфа исходного графа.
У графа на рис.3 три компоненты связности, каждой из которых сопоставлен определенный цвет.
Рис.4. Ориентированный граф.
Компонента сильной связности – сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа исходного орграфа.
У графа на рис.4 три компоненты сильной связности, каждой из которых сопоставлен определенный цвет.
Точка сочленения – вершина графа, удаление которой увеличивает количество компонент связности.
Мост – ребро (дуга), удаление которого увеличивает число компонент связности.
Блок – связный граф (орграф) без точек сочленения.
Для графа на рис.1 ребро (
e,d) – мост, а вершина e – точка сочленения.
