Оценка пропускной способности сети между парой пунктов

5.1Определить пропускную способность между парой пунктов сети с номерами 10 и 1.

Дано: связывающая сеть, содержащая n=10 пунктов, и матрица пропускных способностей линий связи. В качестве последней воспользуйтесь матрицей весов, полученной при выполнении задания 1, полагая, что значения элементов этой матрицы соответствует пропускным способностям линий.

Данная задача может быть сведена к определению пропускной способности минимального сечения. Наиболее простым способом определения такого сечения для двухполюсной сети является перебор всех возможных сечений, которые разделяют множество вершин N сети на два несвязанных подмножества: N₁, которое включает истоки, и N₂, которое включает стоки, и выбор среди них сечения, которое имеет наименьшую пропускную способность.

Присвоим истоку (вершине 10) пометку «0», а стоку (вершине 1) – пометку «1». Полагаем значение счетчика сечений С=0.

Образуем двоичное представление числа С и сортируем вершины в соответствии с пометками. Определим пропускную способность сечения для полученного варианта распределения вершин как сумму пропускных способностей ребер, составляющих рассматриваемое сечение M_i(N₁N₂).

Комбинации пометок вершин и их пропускных способностей сведем в табл.5.1.

Номера сечения	Двоичные комбинации	Mi(N1N2)
Номера вершин

Таблица 5.1 – Метки вершин и пропускные способности их сечений

Как видно из табл.5.1, наименьшей величиной пропускной способности обладает сечение под номером 0. Эта величина и определяет пропускную способность данной сети.

5.2Дать письменные ответы на следующие ключевые вопросы:

1. Что называется потоком из источника в сток?

2. Дайте определение сечения сети.

3. Какое сечение называется минимальным?

4. Сформулируйте теорему о максимальном потоке и минимальном сечении.

5. Какая сеть называется двухполюсной? Многополюсной? Однопродуктовой? Многопродуктовой?

6. В чем отличие многополюсной сети от многопродуктовой?

7. В чем заключается основная идея оценки пропускной способности сети?

Ответы:

1. Потоком Р_st, из некоторой вершины s, называемую истоком, в некоторую вершину t, называемую стоком, в сети является множество неотрицательных чисел х_ij (потоков дуг), если эти числа удовлетворяют следующим ограничениям:

2. Сечением (разрезом) сети называется неизбыточная совокупность дуг (ребер), при изъятии которых из сети нарушается ее связность.

3. Сечение, разделяющее s и t и обладающее наименьшей пропускной способностью, называется минимальным.

4. Величина максимального потока всегда равна минимальной пропускной способности среди всех сечений, разделяющих s и t.

5. Сеть, имеющая один исток и один сток, называется двухполюсной. Сеть, в которой каждая пара вершин может рассматриваться как исток и сток, называется многополюсной. Если в сети имеется несколько истоков и несколько стоков и поток может идти из любого истока в любой сток, то такой поток называется однопродуктовым. Если в сети с несколькими истоками и стоками поток должен идти из некоторых выделенных истоков в некоторые фиксированные стоки, то такой поток называется многопродуктовым.

6. В многопродуктовой сети не каждая пара вершин может рассматриваться как исток и сток.

7. Для оценки пропускной способности связывающей сети достаточно определить величину максимального потока, который она может пропустить, причем вычисление его дуговых компонентов, нахождение путей передачи может оказаться вовсе не обязательным. Согласно теореме о максимальном потоке и минимальном разрезе, указанная задача может быть сведена к определению пропускной способности минимального сечения.

Министерство транспорта и связи Украины

Одесская национальная академия связи им. А. С. Попова

Кафедра сетей связи

Комплексное задание

на тему:

„Элементы синтеза и анализа телекоммуникационных сетей”

Выполнила:

студент гр. ИС-

Одесса 2009г.