Проектирование реляционных баз данных. Ковалев А.В - 26 стр.

      При другом способе организации локальной сети терминалы подключаются или к кон-
центраторам, или непосредственно к центральному узлу. Концентраторы и узлы имеют ограни-
чения на число обслуживаемых ими терминалов. В этом случае используется метод соединения
терминалов, в котором терминалы сначала объединяются вокруг концентраторов, затем созда-
ются группы концентраторов, после чего группы концентраторов и оставшиеся свободные тер-
миналы распределяются по узлам. Прежде чем подключать терминал к концентратору, следует
проверить, не будет ли выгоднее с экономической точки зрения присоединить терминал непо-
средственно к узлу.

       2.4. Оптимизация потоков и пропускных способностей

       2.4.1. Алгоритм Форда-Фалкерсона

       Связность и реберная связность стали значительно понятней, а их вычисление значи-
тельно проще после установления связей между теорией связности и расчетами потоков в сетях.
Выделим в ИВС два узла - источник s и сток t. Если бы это была сеть из труб заданного сече-
ния, можно было бы задать вопросом: какой максимальный поток может перенести эта сеть от s
к t?
       Пусть узлы n1, n2, ..., nk соединены ребрами и задана матрица G=|gij| (1≤i,j≤k) пропускных
способностей, соединяющих узел ni с узлом nj, причем в силу дуплексности каналов связи
предполагается симметричность матрицы G. Необходимо для каждой пары (ni, nj) определить
маршрут, обеспечивающий максимальную пропускную способность. Использование теоремы
об (s-t)-разрезе неориентированного графа позволяет сконструировать конечный алгоритм по-
иска оптимальных потоков.
       Согласно теореме Форда-Фалкерсона максимально возможное значение суммарного по-
тока на конечных дугах равно минимальной пропускной способности выбранного разреза. При
этом под пропускной способностью разреза понимается сумма пропускных способностей дуг,
образующих разрез.
       В математической записи соотношение, выражающее содержание теоремы Форда-
Фалкерсона, выглядит следующим образом:

       ∑ ∑ f(vi,vj) = ∑ ∑ c(vi,vj) ,
        i   j           i   j

где f(vi,vj) - значение потока по дугам заданного графа; c(vi,vj)- пропускная способность дуги; i -
все вершины подграфа, образующие разрез; j - дополнение разреза до множества всех вершин
графа.
       На базе теоремы построен одноименный алгоритм, позволяющий найти минимальные
разрезы и оценить соответствующие им значения максимального потока. Принцип, лежащий в
основе алгоритма, состоит в том, чтобы найти все возможные насыщенные пути (цепи), веду-
щие от vs к vt для (s-t)-разреза. С этой целью последовательно, начиная с вершины vs, просмат-
ривается множество смежных вершин vi. Из множества дуг (vs,vi), соединяющих vs с vi, выби-
рают одну, у которой величина потока ближе всех подходит к значению насыщения. Помечают
вершину vi знаком, показывающим, что она была просмотрена, и приписывают ей величину d,
на которую можно увеличить поток по дуге, ведущей в эту вершину. Затем просматривают по-
следующие вершины vj, смежные с vi, и останавливаются на той, в которую ведет дуга с пото-
ком, ближайшим к значению насыщения. По этой дуге переходят в соответствующую вершину
vj. Делают отметку и идут далее в направлении вершины vt. Если путь, на котором будут отме-
чены все пройденные вершины, приведет в вершину vt, то это говорит о том, что найден один
из путей, наиболее близкий к насыщению. Нужно довести поток по нему до насыщения, увели-
чивая тем самым поток на графе. Значение, на которое можно увеличить поток, находится как
минимальное из всех d, найденных ранее для отмеченных вершин. Для выяснения вопроса, яв-
                                                   28