3.1 Основные понятия

 

Определение 1 Пусть M и N — два конечных множества. Тройка {M, N, T}, где T — отображение множества N в прямое произведение M x M, называет­ся (конечным) ориентированным графом. Элементы множества M называются вершинами графа, элементы множества N — дугами гра­фа, отображение T сопоставляет каждой дуге jN упорядоченную пару вершин, первая из которых называется началом дуги, а вторая — концом дуги. Будем обозначать начало и конец дуги и через beg и и end и соответственно. Говорят, что эти вершины и дуга инцидентны (присущи) друг другу.

Граф можно изобразить рисунком (само название имеет графиче­ское происхождение), на котором каждая вершина представлена точкой или ее более крупным заменителем, а каждая дуга — линией, соеди­няющей начало и конец дуги. Стрелка на дуге или рядом показывает направление от начала к концу. Форма линии несущественна, важен только сам факт соединения вершин.

Например, граф с множеством вершин M = {A,B,C,D}, множе­ством дуг N = {1, 2, 3, 4, 5, 6} и отображением T, задаваемым табли­цей может быть изображен чертежом на рис. 1.

 

 

Рис.1. Пример графа.

 

Определение 2 Пусть х– вершина графа {M, N, T}, поставим ей в соответствие три числа:

 –  число входящих в х дуг,

 – число выходящих из  х дуг,

.

Число  называют полустепенью захода в вершину х,  – полустепенью исхода из вершины х,  называют степенью вершины х.

Если , то вершина х называется изолированной. Если

beg и= end и = х, то дуга и называется петлей в вершине х. Если beg и= end w и beg w= end u, то дуги u и w называются противоположными. Если beg и= beg w и end w= end u, то дуги u и w называются параллельными (кратными).

Полным графом  называется граф с n вершинами без петель, кратных и противоположных дуг, у которого любые две вершины соединены дугой (рис. 2):

Рис. 2.

 

Множество (M, N', T), где N' — подмножество N, называется ча­стичным графом графа (M,N, T).

Пусть M' — какое-либо подмножество M. Обозначим через N(M') множество всех дуг, у которых, и начала и концы принадлежат M'.

Граф (M',N(M'), T) называется подграфом графа (M,N, T). Граф {M', N', T}, где N' С N{M'), называется частичным подграфом графа (M,N,T).