Отрицательные циклы во взвешенных орграфах: различия между версиями

Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
== Постановка задачи ==
== Постановка задачи ==
Пусть G = (V, E) – ориентированный граф (орграф), имеющий m ребер и n вершин, ребра которого ассоциированы с вещественной стоимостной функцией wt: E ! R. Стоимость, wt(P), пути P в графе G равна сумме стоимостей ребер, входящих в P. Простой путь C, начальная и конечная вершины которого совпадают, называется циклом. Если wt(C) < 0, то C называется отрицательным циклом. Необходимо определить, существует ли подобный цикл в данном орграфе G с ребрами вещественной стоимости, и если существует – вывести этот цикл.
Пусть G = (V, E) – ориентированный граф (орграф), имеющий m ребер и n вершин, ребра которого ассоциированы с вещественной стоимостной функцией <math>wt: E \rightarrow \mathbb{R} \;</math>. Стоимость, wt(P), пути P в графе G равна сумме стоимостей ребер, входящих в P. Простой путь C, начальная и конечная вершины которого совпадают, называется [[цикл|циклом]]. Если wt(C) < 0, то C называется [[отрицательный цикл|отрицательным циклом]]. Необходимо определить, существует ли подобный цикл в данном орграфе G с ребрами вещественной стоимости, и если существует – вывести этот цикл.




Задача нахождения отрицательного цикла тесно связана с задачей нахождения кратчайшего пути. В последней необходимо найти путь с минимальной стоимостью между двумя вершинами s и t. Легко увидеть, что кратчайший путь s-t существует в том и только том случае, если ни один путь s-t в графе G не содержит отрицательного цикла [1 , 13]. Также известно, что все кратчайшие пути от заданной вершины s до всех других вершин формируют дерево, называемое деревом кратчайших путей [1, 13].
Задача нахождения отрицательного цикла тесно связана с задачей нахождения кратчайшего пути. В последней необходимо найти путь с минимальной стоимостью между двумя вершинами s и t. Легко увидеть, что кратчайший путь s-t существует в том и только том случае, если ни один путь s-t в графе G не содержит отрицательного цикла [1 , 13]. Также известно, что все кратчайшие пути от заданной вершины s до всех других вершин формируют дерево, называемое [[дерево кратчайших путей|деревом кратчайших путей]] [1, 13].
 


== Основные результаты ==
== Основные результаты ==
4551

правка

Навигация