Циклом будем называть граф, у которого одна компонента связности является простым циклом, а остальные – изолированными вершинами.

В пространстве остовных подграфов графа выделим подпространство, содержащее все циклы графа .

Определение. Остовный подграф, у которого степени всех вершин четны, называется квазициклом.

Отметим, что всякий цикл является квазициклом, в том числе и пустой граф.

Покажем, что множество квазициклов замкнуто относительно операции сложения.

Лемма. Сумма двух квазициклов есть квазицикл.

Доказательство. Пусть и – квазициклы. Рассмотрим произвольную вершину , и пусть ее степени в и равны соответственно и . Тогда степень вершины в графе будет равна , где – число вершин, с которыми смежна в обоих графах и . Отсюда видно, что четно, если четны и .

Из леммы следует, что множество квазициклов является линейным векторным пространством над полем {0, 1}, которое называется пространством циклов графа . Обозначим это пространство через . Очевидно, что является подпространством векторного пространства остовных подграфов

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

Теорема. Множество всех фундаментальных циклов относительно любого остова графа образует базис пространства циклов этого графа. Пусть – остов неориентированного графа , а – система фундаментальных циклов графа относительно остова . Матрицей фундаментальных циклов графа называется матрица размера , в которой

25. 
    Задача о максимальном потоке и ее возможные варианты. Определение транспортной сети, потока в сети и разреза. Теорема Форда-Фалкерсона.
    

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

---

Рассмотрим возможные варианты задачи о максимальном потоке.

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

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

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

Граф, некоторые вершины которого выделены, называется сетью. Выделенные вершины называются полюсами сети. Например, дерево с корнем можно рассматривать как однополюсную сеть.

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

Потоком в сети называется целочисленная функция , определенная на дугах сети и удовлетворяющая условиям:

1. 
   , ; (1)
   
2. 
   , ( , , ). (2)
   

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

---

Теорема. Максимальная величина потока в сети равна пропускной способности любого минимального разреза.

Доказательство. Докажем сначала, что величина любого потока не превосходит пропускной способности любого разреза: . Просуммируем уравнения сохранения (2) по всем вершинам . Получим

, (3)

где значения коэффициентов зависят от расположения концов дуги относительно множеств и .

Перепишем уравнение (3) в виде ,

откуда для любого потока и любого разреза

. (4)

Отсюда следует, что максимальное значение потока в сети равно минимальному значению пропускных способностей разрезов этой сети: .

25. 
    Определение прибавляющей цепи.Алгоритм Форда-Фалкерсона построения максимального потока в транспортной сети.
    

Из теоремы Форда-Фолкерсона следует, что максимальный поток в сети не превосходит минимальной пропускной способности разреза, то есть . (1)

Анализ неравенства (1) показывает, что величина потока совпадает с пропускной способностью разреза тогда и только тогда, когда выполняется условие:

Дадим определение прибавляющей цепи. Рассмотрим в сети цепь из источника в сток, то есть последовательность вершин

такую, что между вершинами и есть дуга ( ), которой может оказаться прямой или обратной .

Пусть в сети задан поток . Цепь из в называется прибавляющей, если для каждой ее прямой дуги выполняется строгое неравенство , а для каждой обратной дуги – строгое неравенство .

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

Алгоритм состоит в последовательном просмотре вершин сети и присвоении им отметок. На каждом шаге алгоритма любая вершина находится в одном из трех состояний: а) не помечена; б) помечена, но не просмотрена; в) помечена и просмотрена.

0-й шаг. Зададим какой-нибудь, например, нулевой поток по сети.

1-й шаг. Помети источник любой отметкой, например, звездочкой *. После этого вершина помечена, но не просмотрена. Остальные вершины не помечены.

2-й шаг. Берем очередную помеченную, но не просмотренную вершину . Просматриваем все дуги, инцидентные этой вершине. Если вторая вершины дуги не помечена, то помечаем ее отметкой в следующих двух случаях:

---

а) дуга выходит из вершины и поток по ней строго меньше пропускной способности;

б) дуга входит в вершину и поток по ней строго больше нуля.

После завершения этого шага вершина объявляется помеченной и просмотренной, а вершины, получившие при просмотре отметку , объявляются помеченными, но не просмотренными.

Шаг 2 циклически повторяется до тех пор, пока не произойдет одно из двух событий, рассматриваемых далее на 3-ем и 4-ом шагах.

3-й шаг. Сток получил отметку, например, . Переходим из в вершину , по отметке вершины отыскиваем следующую вершину и т. д. до тех пор, пока не дойдем до вершины . В результате получаем прибавляющую цепь, с помощью которой увеличиваем текущий поток. Далее стираем отметки всех вершин и повторяем выполнение алгоритма с 1-го шага.

---

4-й шаг. Процесс расстановки отметок закончился тем, что все помеченные вершины просмотрены, но сток при этом не помечен. Пусть – множество помеченных вершин. Так как , а , то можно определить разрез . Для , то есть дуги, идущей из помеченной вершины в непомеченную, , иначе другой конец этой дуги был бы помечен. По той же причине для . Следовательно, для построенного потока и разреза , образованного помеченными вершинами, выполняются условия (1). В таком случае имеем максимальный поток.

25. 
    Определение сетевого графика. Алгоритм отыскания критического пути. Определение резервов времени и коэффициентов напряженности работ
    

Последовательность различных дуг, в которой начало каждой дуги совпадает с концом предыдущей, называется путем. Замкнутый путь называется контуром или ориентированным циклом. Если в сети нет ориентированных циклов, она называется ациклической. Дуги сетиизображают отдельные работы, а вершины – события, состоящие в завершении одной или нескольких работ. Каждой дуге в сетевом графике приписано целое неотрицательное число – продолжительность соответствующей работы.

Обозначим – продолжительность работы ( , ). Рассмотрим некоторый путь на сетевом графике: . Длиной пути назовем сумму продолжительностей входящих в него работ: .

Рассмотрим все пути из начальной вершины в конечную. Путь наибольшей длины называют критическим. Длина критического пути – основная характеристика сетевого графика, смысл которой состоит в том, что если каждая работа ( , ) будет начинаться в тот момент, когда произойдет событие (раньше она начинаться не может), и выполняться точно за время , то вся совокупность работ будет выполнена за время, равное длине критического пути.

Опишем алгоритм для нахождения критического пути в сетевом графике. В процессе работы алгоритма для каждой вершины рассчитывается величина – максимальная длина пути из начала в вершину .

1°. Правильная нумерация сети. Нумерация вершин сети называется правильной, если номер начала любой дуги сети меньше, чем номер ее конца. Правильная нумерация ациклической сети всегда возможна и производится следующим образом. Нумеруем начальную вершину сети нулем и удаляем ее из сети вместе со всеми выходящими из нее дугами. В получающейся сети непременно образуются вершины, не имеющие входящих дуг (это следует из ацикличности), которые назовем вершинами первого ранга и занумеруем их числами 1, 2, … Далее удалим все вершины первого ранга и выходящие из них дуги. Появившиеся вершины без входящих дуг назовем вершинами второго ранга и дадим им очередные номера. Этот процесс продолжается до тех пор, пока не будут занумерованы все вершины сети.

---

Смотрите также файлы

• Правила проектирования и оформления проектов стандартизованы в Единой системе конструкторской документации (ескд), которая устанавливает пять стадий разработки конструкторской документации.pptx

• Министерство образования и науки государственное образовательное учреждение высшего профессионального образования.docx

• Закон противоречия и споры вокруг него.docx

• Основная образовательная программа начального (основного) общего образования. 1)срок получения ооо 5 лет (не установлено сокращение).docx

• Темам 4 Тема Практическое занятие Требования к соблюдению основных принципов работы психолога Ситуация 4.docx