Пропускная способность - дуга
Cтраница 4
Обозначим через N т - мерный вектор, описывающий некоторую сеть, удовлетворяющую всем требованиям к потоку в момент времени t, i-я компонента вектора N1 равна пропускной способности дуги i в этой сети. Ясно, что векторы N образуют выпуклое неограниченное многогранное множество в m - мерном пространстве. Обозначим через N крайние точки этого выпуклого множества. [46]
Смысл выражения (5.17) состоит в том, чтобы при использовании парков набирать необходимое значение потока в первую очередь из парков, отбор запаса из которых значительно ограничен пропускной способностью дуг сети. [47]
В этом случае немедленно придем к противоречию, поскольку условия (4.11) - (4.13) при знаках равенства в них представляют условия баланса элементарных потоков, которые не должны превышать соответствующих пропускных способностей дуг. [48]
Сетью обычно называют произвольный ориентированный граф G ( V, E), каждой дуге которого некоторая функция ( поток) ставит в соответствие неотрицательное вещественное число, называемое пропускной способностью дуги. Алгоритмы построения потока с максимальной величиной ( максимального потока), как правило, основываются на последовательном увеличении потока. [49]
Оценка ри мощности дуги и равна взятой с обратным знаком производной от суммарных затрат на реализацию потока Ф ( А, q, с) сх nN w - p q по пропускной способности дуги и: ри - дФ / и хх. [50]
Так как полный поток, входящий в вершину ж, необходимо должен протекать по дуге ( х, х ]) с пропускной способностью Ш, то максимальный поток в графе Сг с пропускными способностями дуг и вершин равен максимальному потоку в графе 00, имеющем только пропускные способности дуг. [51]
 |
Граф 6 из примера. [52] |
Найти путь от я к I с наибольшей приведенной пропускной способностью в графе О, изображенном на рис. 8.8, где каждая дуга имеет пометку ( а, Ъ), причем а является пропускной способностью дуги, а Ь - ее надежностью. [53]
 |
Граф G из примера. [54] |
Найти путь от s к t с наибольшей приведенной пропускной способностью ъ графе G, изображенном на рис. 8.8, где каждая дуга имеет пометку ( а, Ь), причем а является пропускной способностью дуги, а Ъ - ее надежностью. [55]
А - матрица инциденций сети; е, е - единичные векторы размерности т ( т - число узлов сети) с единицей на месте, соответствующем узлу 0 или / V; q - вектор пропускных способностей дуг сети. [56]
Страницы: 1 2 3 4