I. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ
Будем придерживаться терминологии из [1].
Ориентированным графом (орграфом) G=(Х, Г) называется пара (X, Г) , где X – множество элементов, называемых вершинами,
а Г -многозначное отображение Х =>Х . Многозначное отображение Х=>Х есть закон, по которому каждому элементу x принадлежащему Х ставится .в соответствие некоторое подмножество Гx множества Х . Дугами орграфа называется упорядоченные пары (x, y) принадлежащие Х*Х, y Î Гх. Если обозначить через U множество всех дуг графа, то граф можно определить, как G= (X,U ) Вершина x называется началом дуги u = ( x , y ), а вершина y – ее концом. Дуга ( x , x ) , начало и конец которой совпадают, называется петлей. Две различные вершины x и y называются смежными, если существует соединяющая их дуга.
Полустепенью захода вершины называется число дуг, заходящих я вершину, а полустепенью исхода – исходящих из вершины. Вершина S с нулевой полустепенью захода называется входом орграфа, а вершина t с нулевой полустепенью исхода – выходом орграфа.
Путем L (a, б) из вершины а, в вершину b называется последовательность вершин и дуг a, (a, x1), x1, (x1, x2)…,(xn-1, b),b. Заметим, что в орграфе путь однозначно определяется последовательностью вершин или дуг. Путь называется простым, если вершины не, повторяются. Если существует путь L(a, 6) , то говорят, что вершина b достижима из вершины a . Орграф называется связным, если для любой пары вершин одна достижима из другой.
Путь L (a, a), начала и конец которого совпадают, называется контуром.
Пусть X1, X2 Ì X,