4446
правок
Маршрутизация: различия между версиями
Перейти к навигации
Перейти к поиску
→Нотация и определения
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
Пусть дана сеть с учетом пропускной способности G = (V, E, c), где V– множество вершин, а E – множество дуг с функцией пропускной способности c: E | Пусть дана сеть с учетом пропускной способности 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 рассматривается как неориентированное ребро с той же пропускной способностью, то получается ориентированная сеть, эквивалентная исходной. | ||
'''Определение 1.''' Множество функций | '''Определение 1.''' Множество функций <math>f := \{f_{ij} | i, j \in V, f_{ij}: E(G) \to R^+ \}</math> называется ''задачей о многопродуктовом потоке'', если соотношение <math>\sum_{e \in E^+_k} f_{ij}(e) = \sum_{e \in E^-_k} f_{ij} (e)</math> выполняется для всех <math>k \ne i, k \ne j</math>, где <math>k \in V</math>, а <math>E^+_k, E^-_k</math> – множества ребер, выходящих из k и входящих в k, соответственно. Каждая функция <math>f_{ij}</math> определяет ''однопродуктовый поток'' из i в j. | ||