графов. Графом называется [1] совокупность множества V то-
чек, называемых вершинами, и множества R простых (т. е.
самонепересекающихся) кривых, называемых ребрами, удов-
летворяющих следующим условиям: 1) каждое незамкнутое
ребро содержит ровно две тачки множества V, которые явля-
ются граничными точками ребра; 2) каждое замкнутое ребро
содержит только одну точку из V (граничные точки совпада-
ют); 3) ребра (кривые из множества R) не имеют общих точек,
за исключением точек из множества V.
На рисунке вершина изображается точкой или окружно-
стью. Граф обозначают одной буквой G или парой букв (V, /?),
где V — множество вершин, R — множество ребер графа.
Если множества V и R состоят из конечного числа элементов,
то граф (У, R) называется конечным. Граф Gi — (V
l9
Ri)>
который состоит из части вершин (Vi cz V) и части ребер
(/?! сI R) графа G = (V, /?), называется подграфом G. При
этом G называется подграфом G
x
. Если вершины v
h
и v
t
явля-
ются граничными точками ребра г, то говорят, что г инцидент-
но каждой из вершин v
k
и v
t
и, обратно, каждая из вершин
v
k
и v
t
инцидентна г. Граничные точки ребра г, очевидно,
можно определить как вершины, т. е. точки из множества V,
инцидентные г. Если ребро замкнуто, т. е. оно имеет только
одну граничную точку, то ребро называется петлей.
Если ребра ориентированы, т. е. на каждом ребре задано
направление, то граф называется ориентированным графом,
или орграфом. Ориентированные ребра называются дугами.
Поэтому ориентированный граф, или орграф, можно опре-
делить как совокупность множества V вершин и множества
D дуг, удовлетворяющих перечисленным выше трем услови-
ям. Вершина, являющаяся начальной граничной точкой ду-
ги d
u
называется ее начальной вершиной, а вершина, являю-
щаяся конечной граничной точкой дуги d
if
— ее конечной вер-
шиной.
Последовательность дуг^,..., d
n
(не обязательно разных),
для которой конечная вершина v% дуги d
t
является началь-
ной вершиной дуги d
i+1
, i = 1, п — 1, называется ориен-
тированным маршрутом (ормаршрутом). Ориентированный
маршрут называется замкнутым, если конечная вершина
v
n
дуги d
n
совпадает с начальной вершиной v
0
дуги d
x
. В против-
ном случае ормаршрут называется незамкнутым. Ормаршрут,
в котором нет повторяющихся дуг (все дуги разные), называет-
ся путем от вершины v
Q
к вершине v
n
, если он незамкнут, и
контуром (ориентированным циклом), если он замкнут. Если