Определение 1
Пусть M и N — два конечных множества.
Тройка {M, N, T}, где T —
отображение множества N в прямое произведение M x M, называется
(конечным) ориентированным графом. Элементы множества M называются
вершинами графа, элементы множества N — дугами графа, отображение
T сопоставляет каждой дуге j
N упорядоченную пару вершин, первая из
которых называется началом дуги, а вторая — концом дуги. Будем
обозначать начало и конец дуги и через 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).