Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Задача сочетания с минимальными расстояниями.





РИСУНОК 22.3. ВОПРОСЫ ТРУДОУСТРОЙСТВА

Предположим, что шесть студентов ищут работу, а шесть компаний намерены принять на работу по одному студенту. Два представленных на рисунке списка (один отсортирован по студентам, другой отсортирован по компаниям) образуют список предложений работы, который отражает взаимный интерес в сочетании студентов и предлага­емых работ. Существует ли способ подыскать каждому студенту работу таким образом, чтобы каждое вакантное место было заполнено, а каждый студент получил работу? Если это не удается, то каково число вакансий, которые могут быть заполнены?


Глава 22. Потоки в сетях



 


бится противнику, чтобы лишить войска снабжения? Каждое из указанных выше приложений немедленно порождает многочисленные со­путствующие вопросы, кроме того, существуют и другие родственные модели, такие как задачи календарного планирования, которым была посвящена глава 21. На протяжении этой главы мы будем рассматривать и другие примеры, но все это составит лишь незна­чительную часть важных, непосредственно взаимосвязанных практических задач. Изучаемая в настоящей главе модель потоков в сети важна не только потому, что она ставит перед нами две четко сформулированные задачи, к которым сводятся многие за­дачи, возникающие на практике, но еще и потому, что в нашем распоряжении имеются эффективные алгоритмы решения этих двух задач. Подобная широкая применимость сти­мулировала разработку многочисленных алгоритмов и реализаций. Решение, которое мы будем рассматривать, порождает некоторое противоречие между попыткой достичь уни­версальной применимости и поиском эффективного решения конкретных задач. Изуче­ние алгоритмов вычисления потоков в сети само по себе является захватывающим заня-

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

В задаче сечения, подобной той, что иллюстрирует­ся рисунком 22.4, мы удаляем ребра с целью разбиения сети на две или большее число частей. Задачи о сече­ниях непосредственно связаны с фундаментальными вопросами связности графа, которые обсуждались в главе 18. В этой главе мы будем изучать центральную теорему, которая обнаруживает удивительную связь между задачей о сечении и задачей о потоках в сетях, существенно расширяя применимость алгоритмов вы­числения потоков в сетях.

Надежность сети.Упрощенная модель представля­ет телефонную сеть как некоторое множество прово­дов, которые соединяют телефонные аппараты через коммутаторы так, что существует возможность посред­ством переключений установить через магистральные линии коммутируемую линию связи, соединяющую лю­бые два заданных телефонных аппарата. Каким будет максимальное число магистральных линий, которые можно отключить без нарушения связи между любой парой телефонных коммутаторов?



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


РИСУНОК 22.4. ОТСЕЧЕНИЕ ЛИНИЙ СНАБЖЕНИЯ

На этой диаграмме представлена система дорог, соединяющих базы снабжения армии в ее верхней части с войсками в ее нижней части. Черные точки изображают план бомбовых ударов противника, которые должны отделить войска от их баз снабжения. Задача противника заключается в том, чтобы минимизировать стоимость бомбардировок (возможно, исходя из предположения, что стоимость отсечения ребра пропорциональна его ширине), а целью армии являет­ся разработка такой сети дорог, чтобы существенно увеличить минимальную стоимость бомбарди­ровок. Эта же модель полезна для повышения надежности сетей связи и во множестве других приложений.




mylektsii.ru - Мои Лекции - 2015-2018 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал