Алгоритмы решения задач на графах и сетях

Алгоритмы решения задач на графах и сетях

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,

Комментарии к записи Алгоритмы решения задач на графах и сетях отключены

Рубрика: Программирование

Обсуждение закрыто.