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.