|
|
так, чтобы не образовалось никакого цикла) - BC (его цена равна 14) (рис. 3). Таким образом стоимость строительства равна 38 (11+13+14=38)
Задана сеть, каждое ребро которой имеет вполне определенную ограниченную пропускную способность. Требуется определить максимально возможный поток в этой сети из заданного узла в другой узел.
Чтобы пояснить основную идею метода решений этой задачи, предположим, что исходный и конечный пункты, пункт А и пункт В, находятся на разных берегах разделяющей их реки (рис. 4) Множество мостов через реку образуют так называемое разделяющее сечение (если все мосты по каким-либо причинам выйдут из строя, попасть из пункта А в пункт В будет просто невозможно). Пропускная способность разделяющего сечения складывается из пропускных способностей всех мостов. Подобных сечений, разделяющих пункты А и В, может быть несколько, и каждое из них обладает своей пропускной способностью. Из того, что поток из пункта А в пункт В должен проходить через каждое разделяющее сечение, вытекает, что максимально возможный поток не может превосходить пропускной способности ни одного из этих сечений.
Таким образом, отыскание макси-потока (максимально возможного потока) сводится к отысканию мини-сечения (разделяющего сечения с наименьшей пропускной способностью).
Предположим, что требуется проанализировать проект с точки зрения минимальных временных затрат на его выполнение. Для этого проект разбивают на отдельные работы, или действия, оценивают время, необходимое на проведение каждой из них, и записывают последовательность операций, показывающую, какие работы должны быть закончены. Прежде чем начнутся другие. Затем вычерчивается диаграмма работ, на которой каждая работа изображается направленным ребром, и определяется критический путь, имеющий наибольшую общую продолжительность. Он и определяет минимум временных затрат на выполнение проекта.
ВКЛАД Х.ГЮЙГЕНСА В РАЗВИТИЕ ТЕОРИИ ВЕРОЯТНОСТЕЙ
D
С
РисЗ
р и с , 4
Жупбаева Л.А. гр. 49-71 (Юдина Г.Е.)
Сейчас трудно установить, кто впервые поставил вопрос о возможности количественного измерения возможности появления случайного события. В течение долгого периода исследователи ограничивались рассмотрением
|
