X1ÇX2, X1ÇX2=Æ, x0ÎX1, zÎX2, называемое разрезом сети.
Сумма пропускных способностей множества {(xi,xj), xi из X1, Xj из Х2} определяет пропускную способность разреза R : r(R) = c(u),
uÎ{(xi,xj):xi ÎX1, xjÎX2}
Поскольку для любой дуги u выполняется неравенство ф(u)<=c(u), то Ф<=r(R).
Теорема Форда-Фалкерсона : максимальный поток в сети равен минимальной величине разрезов в этой сети.
Алгоритм нахождения максимального потока, предложенный Фордом и Фалкерсоном, состоит в постепенном увеличении допустимого потока Ф до максимальной величины Ф*. Начальное значение потоков полагается равным нулю. Процесс увеличения потока состоит в поиске путей, на которых возможно увеличение потока, с соответствующей разметкой вершин сети.
Алгоритм Форда-Фалкерсона
Предполагается, что путь из истока в сток с ненулевыми пропускными способностями входящих в него дуг существует.
I. Увеличение потока.
1. Присвоить истоку х0 пометку (+х0, d(x0) = ). Это означает, что вход в исток не ограничен; величина d всегда показывает, на сколько может быть увеличен поток, входящий в помеченную вершину. Здесь символ обозначает достаточно большое число – начальное значение пометки.
2. Взять некоторую вершину xi с пометкой, которая в общем случае имеет вид (+ или – xk, d(xi)), где xk – обозначение вершины, d(xi) – некоторое число. Каждой непомеченной вершине xj из S-(xi), для которой ф(xi,xj)<с(xi,xj), присвоить пометку (+xi, min[d(xi),c(xi,xj)-ф(xi,xj)]). Это означает, что поток в дуге (xi,xj) может быть увеличен (знак плюс) на величину, определяемую минимумом. Каждой непомеченной вершине xj из S+(xi), такой, что ф(xj,xi)>0 присвоить пометку (-xi, min[d(xi), ф(xj,xi)]), что означает возможность уменьшения потока на величину, определяемую минимумом.
3. Если сток не помечен и можно пометить какую-либо вершину, кроме стока, то перейти к п.2.
4. Если оказался помеченным сток z, и в его пометку входит число d(z), то между вершинами x0 и z найдется цепь, все вершины которой помечены номерами предыдущих вершин. Для каждой помеченной вершины х в этой цепи изменить величину потока : ф'(y,x)=ф(y,x)+d(z), если х имеет пометку (+y,d(x)) или ф'(y,x)=ф(y,x)-d(z), если х имеет пометку (-y,d(x)). Пометка вершины х стирается, назначенные потоки запоминаются. При достижении (в процессе стирания пометок вершин цепи) истока х0 перейти к п.1; если же ни одну вершину пометить не удается и сток z не помечен, то перейти к построению разреза.
II.Построение разреза.
Искомый минимальный размер R определяется двумя множествами Х1 и Х2, где Х1 – все помеченные вершины, Х2 – вершины, которые не удается пометить. При этом полный поток Ф=Ф* должен быть равен величине полученного минимального разреза.
2.Сетевые структуры на базе
теоретико-графовых моделей
2.1. Методы построения сетевых структур
Компьютерная сеть состоит из элементов, среди которых выделяют компьютеры, предоставляющие ресурсы в сети (серверы), компьютеры, обеспечивающие доступ к сетевым ресурса серверов (клиенты), среду (media), в которой реализованы соединения, и сами ресурсы – файлы, процессоры, принтеры, и другие элементы. В сетях реализуется принципиальная возможность совместного использования и устройств, и данных.
Соединения компьютеров в сети может осуществляться по-разному, и различным типовым способам присвоены различные наименования.
Различают сети с выделенными серверами и одноранговые сети. В настоящее время наиболее распространенными являются сети с архитектурой клиент-сервер, которые используют центральный сервер для обслуживания запросов клиентов, в то время как одноранговые сети позволяют любой рабочей станции функционировать одновременно в качестве сервера, если этого требуют задачи.
В сетях с архитектурой клиент-сервер специализированный компьютер (выделенный сервер) используется для установки всех разделяемых ресурсов. Такое решение ускоряет доступ пользователей к централизованным ресурсам сети и связано с рядом особенностей :
- сетевое администрирование проще за счет незначительного числа серверов в сети и их узкой специализации;
- предъявляются высокие требования к выделенному серверу : для обеспечения высокой производительности требуется установка на сервере большого количества оперативной памяти, диска большой емкости и использования в сервере производительного процессора;
- при нарушении работы сервера сеть становится практически неработоспособной.
Если в одноранговой сети нет выделенного сервера, все компьютеры равноправны в том смысле, что могут рассматриваться и как серверы, и как клиенты. Обычно одноранговые сети содержат до десяти компьютеров.
Одноранговая сеть на основе сервера содержит выделенный сервер. Сеть может содержать не один, а несколько серверов, имеющих специальное назначение :
- файл-серверы;
- принт-серверы;
- серверы приложений, на которых выполняются прикладные задачи;
- почтовые серверы;
- факс-серверы;
- коммуникационные серверы, управляющие потоком данных и почтовых сообщений между сетью, в которой они размещены, и другими сетями, мэйнфреймами (большими ЭВМ) или удаленными пользователями через модемы и телефонные линии;
- серверы служб каталогов, обеспечивающие поиск, хранение и защиту информации в сети.
В комбинированных сетях совмещаются лучшие качества одноранговых сетей и сетей на основе сервера. Используется сервер, но и другие отдельные компоненты могут разрешать доступ к своим данным.
2.2. Классификация существующих методов организации сетей
Базовые топологии локальных сетей
Базовые топологии локальных сетей – это основные виды конфигураций соединений элементов сетей при помощи кабеля.
Рассмотрим три базовых топологии : шина, звезда и кольцо.
Шина (или линейная шина) – это топология, представленная на рис. 4.
Рис. 4. Простейшая одноранговая сеть.
Передаваемый сигнал распространяется по кабелю – магистрали (сегменту) и поглощается на концах терминаторами (заглушками). В любой момент времени только один компьютер может вести передачу. Данные передаются всем компьютерам сети, однако информацию принимает только тот, адрес которого соответствует адресу получателя, зашифрованному в передаваемых данных.
Говорят, что шина – пассивная топология. Компьютеры только “слушают”, но не регенерируют сигналы. Подсоединение кабеля осуществляется при помощи баррел-коннекторов и репитеров.
Баррел-коннекторы – это специальные металлические соединительные разъемы; они позволяют сращивать кабель, но при большом количестве стыковок сигнал ощутимо затухает. Для решения проблемы сохранения физических параметров сигналов, распространяющихся в компьютерных сетях, применяют специальные устройства.
Репитер – это повторитель-формирователь, просто усиливающий сигнал.
Топология звезда предусматривает подключение всех компьютеров с помощью сегментов кабеля к центральному элементу. Различают два подтипа этой топологии – пассивная звезда, в центре которой нет компьютера-абонента, кабели соединены при помощи концентратора (hub), и активная звезда, содержащая в центре компьютер, управляющий обменом информации в сети. Концентратором (hub) называют устройство, служащее для объединения нескольких сегментов сети и не преобразующее передаваемую информацию. Сигналы от передающего компьютера поступают через концентратор ко всем остальным. Концентраторы бывают активные, пассивные и гибридные.
Активная звезда обеспечивает бесконфликтное управление, но нарушения в работе центра приводят к выходу из строя всей сети, но зато сеть с такой топологией мало чувствительна к выходу из строя участков соединительного кабеля.
Топология кольцо предусматривает передачу сигналов по кольцу в одном направлении, так, что сигналы проходят через каждый компьютер (рис.5). В отличие от пассивной топологии “шина”, здесь каждый компьютер выступает в роли репитера, усиливая сигналы и передавая их следующему компьютеру.
Сервер
Рис.5. Топология “Кольцо”.
Типы кабелей
Тип кабеля, выбранного для соединения сетевых компонентов между собой, определяет максимальную скорость передачи данных в сети и возможную удаленность компьютеров друг от друга. Это связано с частотными свойствами процессов распространения сигналов. Основными и наиболее распространенными являются следующие типы кабелей :
- Коаксиальный (coaxial), подразделяющийся на толстый и тонкий;
- Витая пара (twisted pair), имеющая два типа : неэкранированная (10 Base-T) и экранированная.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
