4551
правка
Отрицательные циклы во взвешенных орграфах: различия между версиями
Материал из WEGA
Отрицательные циклы во взвешенных орграфах (посмотреть исходный код)
Версия от 23:42, 17 января 2016
, 17 января 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть G = (V, E) – ориентированный граф (орграф), имеющий m ребер и n вершин, ребра которого ассоциированы с вещественной стоимостной функцией <math>wt: E \rightarrow \mathbb{R} \;</math>. Стоимость, 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 с ребрами вещественной стоимости, и если существует – вывести этот цикл. | ||
