1
Основные понятия и определения теории графов
Графы бывают
двух типов – неориентированные и ориентированные. В нашем курсе мы будем в
основном заниматься ориентированными графами (они чаще встречаются в приложениях).
Определение
1 Ориентированным графом (
орграфом
графом) будем называть
тройку G(X,U,f), где Х (≠Æ) – множество, называемое множеством вершин графа, U – множество (возможно, и пустое ), называемое
множеством дуг, f – отображение, действующее из U в Х
Х, называемое отображением инцидентности.
Пример
1 Рассмотрим граф, изображенный на рис.
1.

Рис. 1
![]()
;
![]()
![]()
Введем в рассмотрение стандартные отображения
и ![]()
следующими
правилами: ![]()
Определение
2 Пусть G(Х,U, f) – граф , u(ÎU) – дуга. Назовем вершину
началом дуги
, вершину
концом дуги
.
Дуги u(ÎU) и v(ÎU) называются параллельными (кратными), если
.
Дуги u(ÎU) и w(ÎU) называются противоположными, если
.
Дуга t (ÎU) называется петлей в вершине х, если
.
Если
, то говорят, что дуга u инцидентна вершинам х и у. Вершина
называется
изолированной, если
.
Для графа на
рис. 1 дуги V и VI параллельны, IX и X - противоположны , III - петля в
вершине 2, вершина 6 - изолированная вершина. Вершина 2 инцидентна дугам II, III,IV, IX, X и VII.
Определение
2 Граф G(Х,U, f) называют конечным, если
, т.е. у него конечное число вершин и дуг.
В дальнейшем
мы будем рассматривать только конечные графы (не оговаривая это дополнительно).
Определение
3 Граф
с n вершинами называется помеченным, если его множество
вершин
.
Во многих
задачах теории графов (особенно решаемых на ЭВМ) графы удобно описывать
матрицами.
Определение 4 Пусть G(Х, U, f) –
помеченный конечный граф с n вершинами и m дугами (дуги тоже занумерованы). Матрицей смежности
графа G называется
матрица А(G) размера n ´ n, определенная следующим:

Определение 5 Матрицей инцидентности графа называется матрица В(G) размера n ´ m, определяемая следующим:

В случае неориентированного графа
матрица инцидентности В(G) определяется следующим:

Пример 2 Построим матрицу смежности для
графа на рис. 1.
;
.
Определение
6 Путем длины n (ÎN ) на графе G(Х, U, f) называется
отображение
такое, что
![]()
Вершина
называется началом
пути
, вершина
– концом пути
.
Если
, то путь называется контуром.
Если
отображение
инъективно, то путь
(контур) называется простым.
Определение
7 Цепью длины n (ÎN) на графе G(Х, U, f) называется
отображение
такое, что у любой
дуги
одна инцидентная вершина
общая с дугой
, а другая – общая с дугой
.
Вершина дуги
, не являющаяся общей с дугой
, называется началом пути, вершина дуги
, не являющаяся общей с дугой
, называется концом цепи.
Если начало цепи совпадает с её концом, цепь
называется циклом.
Если отображение
инъективно, то цепь
(цикл) называется простой (простым).
Пример 3
Рассмотрим граф, приведенный на рис. 2, и отображение
, заданное таблицей 1.
Таблица 1
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
m(i) |
I |
II |
III |
IV |
V |
VI |
VII |
VIII |
IX |

Рис. 2
Ясно, что m – путь длины 9 из 2-ой вершины в 7-ю
вершину. Рассмотрим отображение h, заданное
правилом
![]()
Ясно, что h – цепь длины 4 из 2-й в 8-ю вершину.
– контур длины 3.
– цикл длины 4.