Маршрутизация: различия между версиями

Пусть дана сеть с учетом пропускной способности G = (V, E, c), где V– множество вершин, а E – множество дуг с функцией пропускной способности <math>c: E \to R^+</math>. Пусть |V| = n, |E| = m. Можно предположить, что сеть G является ориентированной, поскольку в противном случае для каждого неориентированного ребра e = (u, v) можно добавить к графу две новых вершины x, y и четыре новых ориентированных ребра <math>e_1 = (u, x), e_2 = (v, x), e_3 = (y, u), e_4 = (y, u)</math> с бесконечной пропускной способностью. Если e рассматривается как неориентированное ребро с той же пропускной способностью, то получается ориентированная сеть, эквивалентная исходной.

'''Дано''': Сеть с учетом пропускной способности G = (V, E, c).