Автор работы: Пользователь скрыл имя, 12 Марта 2014 в 15:16, курс лекций
Эйлеров цикл содержит не только все ребра (по одному разу), но и все вершины графа (возможно, по несколько раз). Ясно, что эйлеровым может быть только связный граф. С эйлеровым циклом как раз связана задача о кенигсбергских мостах, приведшей к исторически первой попытке развития теории графов как самостоятельного предмета. Чтобы решить данную задачу потребуется сначала сформулировать и доказать теорему. Эта теорема справедлива также и для мультиграфов, и для псевдографов, исключая тот случай, когда псевдограф имеет только одну вершину.
Видим, что на сети исток I и сток S связаны дугами. Значит, можно добавить какое-то количество потока по ненасыщенным дугам, при этом придется перераспределить поток.
Этап 2.
На построенной сети помечаем вершины. Вершину пометим . Смежную ей вершину помечаем , так как эти вершины соединяет ненасыщенная дуга . Вершину помечаем , так как вершины и соединяет ненасыщенная дуга . Вершину помечаем , так как вершины и соединяет непустая дуга . Вершины и помечаем , так как они соединены с вершиной ненасыщенными дугами и . Вершина смежная вершине , и эти вершины соединены ненасыщенной дугой , поэтому вершину помечаем . Вершина смежная вершине , и эти вершины соединены ненасыщенной дугой , поэтому вершину помечаем .
Вершина оказалась помеченной. Значит, существует последовательность помеченных вершин от к : . В этой последовательности каждая последующая вершина помечена буквой предыдущей вершины. Перераспределим поток на этом пути. Определим число : . Увеличиваем на 1 единицу поток на дугах, имеющих направление от к : , , , . Уменьшаем на 1 единицу поток на дугах, имеющих обратное направление: . Получаем следующую сеть с новым сформированным потоком, который изображен на рисунке.
Проверим, будет ли построенный поток максимальным. Изобразим сеть, на которой отметим все вершины и ненасыщенные дуги, как сделали выше.
Вновь помечаем вершины. Вершину пометим . Смежную ей вершину помечаем , так как эти вершины соединяет ненасыщенная дуга . Все остальные вершины, в том числе и вершина , остаются непомеченными. Значит, поток на сети максимальный.
Этап 3.
Как видно на последней сети исток и сток не связны дугами. Значит, поток, изображенный на предпоследней сети, является максимальным.
Строим разрез на сети. Разбиваем множество вершин на два подмножества: A и B. Помеченные вершины образуют множество , непомеченные – множество .
Проводим разрез , который состоит из дуг , , , :
Определяем величину максимального потока :
(ед.)
Информация о работе Лекции по "Развитию операционных систем"