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

Пусть дана сеть с информацией о пропускной способности 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 = (x, u), e_4 = (y, u)</math> с бесконечной пропускной способностью. Если e рассматривается как неориентированное ребро с той же пропускной способностью, то получается ориентированная сеть, эквивалентная исходной.

''Нагруженность'' спроса D по маршруту r составляет <math>con(r, D) = max_{e \in E} \; con(e, r, D)</math>.