Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задача сочетания с минимальными расстояниями.
|
|
РИСУНОК 22.3. ВОПРОСЫ ТРУДОУСТРОЙСТВА
Предположим, что шесть студентов ищут работу, а шесть компаний намерены принять на работу по одному студенту. Два представленных на рисунке списка (один отсортирован по студентам, другой отсортирован по компаниям) образуют список предложений работы, который отражает взаимный интерес в сочетании студентов и предлагаемых работ. Существует ли способ подыскать каждому студенту работу таким образом, чтобы каждое вакантное место было заполнено, а каждый студент получил работу? Если это не удается, то каково число вакансий, которые могут быть заполнены?
Глава 22. Потоки в сетях
| бится противнику, чтобы лишить войска снабжения? Каждое из указанных выше приложений немедленно порождает многочисленные сопутствующие вопросы, кроме того, существуют и другие родственные модели, такие как задачи календарного планирования, которым была посвящена глава 21. На протяжении этой главы мы будем рассматривать и другие примеры, но все это составит лишь незначительную часть важных, непосредственно взаимосвязанных практических задач. Изучаемая в настоящей главе модель потоков в сети важна не только потому, что она ставит перед нами две четко сформулированные задачи, к которым сводятся многие задачи, возникающие на практике, но еще и потому, что в нашем распоряжении имеются эффективные алгоритмы решения этих двух задач. Подобная широкая применимость стимулировала разработку многочисленных алгоритмов и реализаций. Решение, которое мы будем рассматривать, порождает некоторое противоречие между попыткой достичь универсальной применимости и поиском эффективного решения конкретных задач. Изучение алгоритмов вычисления потоков в сети само по себе является захватывающим заня- |
довательно, можно получить пути следования всех самолетов. К этой схеме можно свести и другие приложения, использующие выборку данных.
В задаче сечения, подобной той, что иллюстрируется рисунком 22.4, мы удаляем ребра с целью разбиения сети на две или большее число частей. Задачи о сечениях непосредственно связаны с фундаментальными вопросами связности графа, которые обсуждались в главе 18. В этой главе мы будем изучать центральную теорему, которая обнаруживает удивительную связь между задачей о сечении и задачей о потоках в сетях, существенно расширяя применимость алгоритмов вычисления потоков в сетях.
Надежность сети. Упрощенная модель представляет телефонную сеть как некоторое множество проводов, которые соединяют телефонные аппараты через коммутаторы так, что существует возможность посредством переключений установить через магистральные линии коммутируемую линию связи, соединяющую любые два заданных телефонных аппарата. Каким будет максимальное число магистральных линий, которые можно отключить без нарушения связи между любой парой телефонных коммутаторов?
Отсечение линий снабжения. Когда та или иная страна ведет военные действия, она осуществляет материальное снабжение войск через систему взаимосвязанных дорог. Противник может прервать снабжение войск, нанося по дорогам бомбовые удары, при этом предполагается, что число бомб пропорционально ширине дороги. Какое минимальное число бомб понадо-
РИСУНОК 22.4. ОТСЕЧЕНИЕ ЛИНИЙ СНАБЖЕНИЯ
На этой диаграмме представлена система дорог, соединяющих базы снабжения армии в ее верхней части с войсками в ее нижней части. Черные точки изображают план бомбовых ударов противника, которые должны отделить войска от их баз снабжения. Задача противника заключается в том, чтобы минимизировать стоимость бомбардировок (возможно, исходя из предположения, что стоимость отсечения ребра пропорциональна его ширине), а целью армии является разработка такой сети дорог, чтобы существенно увеличить минимальную стоимость бомбардировок. Эта же модель полезна для повышения надежности сетей связи и во множестве других приложений.