5. Оценка пропускной способности сети между парой пунктов.
5.1 Определить пропускную способность между парой пунктов сети с номерами 10 и 1.
Дано: связывающая сеть, содержащая n=10 пунктов, и матрица пропускных способностей линий связи. В качестве последней воспользуйтесь матрицей весов, полученной при выполнении задания 1, полагая, что значения элементов этой матрицы соответствует пропускным способностям линий.
Данная задача может быть сведена к определению пропускной способности минимального сечения. Наиболее простым способом определения такого сечения для двухполюсной сети является перебор всех возможных сечений, которые разделяют множество вершин N сети на два несвязанных подмножества: N1, которое включает истоки, и N2, которое включает стоки, и выбор среди них сечения, которое имеет наименьшую пропускную способность.
Присвоим истоку (вершине 10) пометку «0», а стоку (вершине 1) – пометку «1». Полагаем значение счетчика сечений С=0.
Образуем двоичное представление числа С и сортируем вершины в соответствии с пометками. Определим пропускную способность сечения для полученного варианта распределения вершин как сумму пропускных способностей ребер, составляющих рассматриваемое сечение Mi(N1N2).
Комбинации пометок вершин и их пропускных способностей сведем в табл.5.1.
|
Номера сечения |
Двоичные комбинации |
Mi(N1N2) | |||||||
|
Номера вершин | |||||||||
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 | ||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
109 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
257 |
|
2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
252 |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
220 |
|
4 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
184 |
|
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
332 |
|
6 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
327 |
|
7 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
295 |
|
8 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
343 |
|
9 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
395 |
|
10 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
450 |
|
11 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
322 |
|
12 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
318 |
|
13 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
370 |
|
14 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
425 |
|
15 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
297 |
|
16 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
218 |
|
17 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
366 |
|
18 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
235 |
|
19 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
203 |
Таблица 5.1 – Метки вершин и пропускные способности их сечений
Как видно из табл.5.1, наименьшей величиной пропускной способности обладает сечение под номером 0. Эта величина и определяет пропускную способность данной сети.
5.2 Дать письменные ответы на следующие ключевые вопросы:
Что называется потоком из источника в сток?
Дайте определение сечения сети.
Какое сечение называется минимальным?
Сформулируйте теорему о максимальном потоке и минимальном сечении.
Какая сеть называется двухполюсной? Многополюсной? Однопродуктовой? Многопродуктовой?
В чем отличие многополюсной сети от многопродуктовой?
В чем заключается основная идея оценки пропускной способности сети?
Ответы:
Потоком Рst, из некоторой вершины s, называемую истоком, в некоторую вершину t, называемую стоком, в сети является множество неотрицательных чисел хij (потоков дуг), если эти числа удовлетворяют следующим ограничениям:
Сечением (разрезом) сети называется неизбыточная совокупность дуг (ребер), при изъятии которых из сети нарушается ее связность.
Сечение, разделяющее s и t и обладающее наименьшей пропускной способностью, называется минимальным.
Величина максимального потока всегда равна минимальной пропускной способности среди всех сечений, разделяющих s и t.
Сеть, имеющая один исток и один сток, называется двухполюсной. Сеть, в которой каждая пара вершин может рассматриваться как исток и сток, называется многополюсной. Если в сети имеется несколько истоков и несколько стоков и поток может идти из любого истока в любой сток, то такой поток называется однопродуктовым. Если в сети с несколькими истоками и стоками поток должен идти из некоторых выделенных истоков в некоторые фиксированные стоки, то такой поток называется многопродуктовым.
В многопродуктовой сети не каждая пара вершин может рассматриваться как исток и сток.
Для оценки пропускной способности связывающей сети достаточно определить величину максимального потока, который она может пропустить, причем вычисление его дуговых компонентов, нахождение путей передачи может оказаться вовсе не обязательным. Согласно теореме о максимальном потоке и минимальном разрезе, указанная задача может быть сведена к определению пропускной способности минимального сечения.
Министерство транспорта и связи Украины
Одесская национальная академия связи им. А. С. Попова
Кафедра сетей связи