Потоковые сети

При рассмотрении графов этого вида трафик называется потоком — это абстракт- ная сущность, которая генерируется узлами-источниками, передается по ребрам и поглощается узлами-стоками. Формально сеть движения потока (или потоковая сеть) представляет собой направленный граф G = (V, E) со следующими отличи- тельными признаками:

♦ С каждым ребром e связывается пропускная способность — неотрицательное число, которое будет обозначаться c

♦ Существует один узел-источник 5 V.

♦ Существует один узел-сток t ^ V.

Узлы, отличные от 5 и t, будут называться внутренними узлами.

В отношении потоковых сетей, с которыми мы будем иметь дело, будут дей- ствовать два предположения: во-первых, ни одно ребро не входит в источник 5, и ни одно ребро не выходит из стока t; во-вторых, у каждого узла существует хотя бы одно инцидентное ему ребро; в-третьих, все пропускные способности пред- ставляют собой целые числа. Эти предположения делают модель более стройной и устраняют ряд аномалий, сохраняя практически все интересующие нас свойства.

На рис. 7.2 изображена потоковая сеть с четырьмя узлами и пятью ребрами; рядом с каждым ребром указана его пропускная способность.

Рис. 7.2. Потоковая сеть с источником s и стоком t. Числа рядом с ребрами обозначают пропускные способности


<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Потоковые сети:

  1. 3.5. Подключение к сети
  2. Социальные сети
  3. 4.4. Подключение к сети
  4. В .А. Галкин, Ю .А. Григорьев. Телекоммуникации и сети, 2003
  5. § 3. Интервью в глобальной сети
  6. Э. ТАНЕНБАУМ. КОМПЬЮТЕРНЫЕ СЕТИ 4-Е ИЗДАНИЕ, 2003
  7. 1.7. Порядок подключения к сети
  8. Другие города Сети Агартхи
  9. Д.А. Губанов, Д.А. Новиков, А.Г. Чхартишвили. СОЦИАЛЬНЫЕ СЕТИ: МОДЕЛИ ИНФОРМАЦИОННОГО ВЛИЯНИЯ, УПРАВЛЕНИЯ И ПРОТИВОБОРСТВА, 2010
  10. В. Г. Олифер, Н. А. Олифер. 54 Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд, 2006
  11. А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко. Вычислительные машины, сети и телекоммуникационные системы, 2009