Шаг 1: от вершины а двойственного графа до вершины b по алгоритму Дейкстры найти кратчайший путь, который будет являться минимальным разрезом исходного графа.
Шаг 2: определить численную величину минимального разреза. По теореме Форда-Фалкерсона величина максимального потока равна величине минимального разреза.
15. Сравнение методов определения максимального потока в телекоммуникационной сети: метод насыщения ребер и метод двойственного графа.
Алгоритм двойственных графов не указывает ребра исходного графа, по которому придет максимальный поток, дает только численную величину. Метод двойственного графа можно применять только на плоских графах. Кроме того этот метод рекомендуется использовать, когда вершины S и t находятся при внешних гранях исходного графа.
Метод насыщения ребер универсален, его можно применять в самых разных случаях.
Метод двойственного графа в некоторых частных случаях может более быстро находить результат только величины максимального потока.
Метод насыщения ребер позволяет определить не только величину максимального потока, но и конкретные ребра, по которым тот поток пройдет.
16. Задача о Кёнигсбергских мостах. Теорема Эйлера.
Формулировка задачи.: существует ли циклический маршрут из последовательности ребер, выходящий из любой вершины графа и проходящий по каждому ребру в точности по одному разу?
Теорема Эйлера: конечный неориентированный граф G является Эйлеровым тогда, когда он связан и степени всех его вершин четные. В Эйлеровом графе всегда существует Эйлеров цикл, который можно нарисовать безотрывно, если выйти из любой вершины, пройти по всем ребрам 1 раз и вернутся в исходную вершину. В неэйлеровом графе нет Эйлерова цикла, но может существовать Эйлеров путь. Это бывает в том случае, если только две вершины имеют нечетные степени, при этом Эйлеров путь начинается в одной, а заканчивается в другой вершине с нечетной степенью.
При нахождении эйлерова цикла и пути,в каждую вершину гр.модели можно заходить сколь угодно раз,а по каждому ребру только 1.
(( Для того, чтобы существовал циклический маршрут в графе G, необходимо и достаточно, чтобы граф был связным и степени всех его вершин были четными. Теперь мы можем сформулировать определение графа. Графом называется пара (V, E), где V – множество вершин, E – множество инцидентных им ребер. Под степенью вершины графа понимается число ребер, инцидентных этой вершине (связанных с ней).
Задача о Кенигсбергских мостах решения не имеет. Если изменить условия задачи (например, допустить что по каким-то мостам можно проехать дважды) можно найти решение.
17. Циклы в графовых моделях телекоммуникационных сетей. Эйлеров и Гамильтонов циклы. Эйлеров путь. Гамильтонова цепь. Примеры.
В гамил.циклах все особенности обратные эйлерову циклу.
Гамильтонова цепь – это цепь, в которой все вершины различны, которая содержит все вершины графа моделирования телекоммуникационной сети.
Гамильтонов цикл-гамил.цепь,у которой начальная и конечная вершины совпадают.
Маршрут-Чередующаяся последовательность 
вершин
и ребер графа ,в которой любая пара соседних эл-в инцидентна .
Маршрут также можно задать последовательностью вершин или последовательностью ребер. Число ребер в маршруте называется длиной маршрута.Если все ребра маршрута различны, то он называется цепью. Если все вершины маршрута различны, кроме, возможно, крайних, то он называется простой цепью. Простая цепь, содержащая все вершины графа, называется Гамильтоновой цепью. Маршрут называется циклическим , если v1= vk+1. Циклическая цепь называется просто циклом, циклическая простая цепь – простым циклом. Простой цикл, содержащий все вершины графа, называется Гамильтоновым циклом.Минимальная длина из длин циклов графа называется его обхватом.Путь – это ориентированный маршрут
18. Гамильтоновы циклы и их применение при проектировании оптимального кольца SDH.
Гамильтонов цикл – цепь, у которой начальная и конечная вершины совпадают.
Классическая задача относится к гам.циклам,образуя кольцоSDH
Признаки кольца SDH:1.Минимальная длина2.проходить через каждый пункт(вершину) связи 1 раз.
Матем.постановка задачи:Дано:регион,который должен посетить коммивояжер,неск-ко городов,расстояние между ними известно.Найти:кратчайшую дорогу,проходящую через все пункты,и возвратиться в исх.
Общий подход к решению.Города можно предс-ть как вершины графа G,в кот.каждой паре вершин (хi; xj )приписывается расстояние m(хi; xj ).Если какие-то 2 вершины не соед-ны,то м\полагать,что m(хi; xj )=бесконечности.Дальше нах-ся такой гамил.цикл P,для которого
M(p)= å m(хi; xi+1 ) àmin. Задачу можно решить перебором.Эффективного алгоритма решения задачи нет.Существует только нек-е частные схемы решения для отдельных случаев.
19. Алгоритм Хуанг-Туи для нахождения Эйлерова цикла в сложном Эйлеровом графе, моделирующем телекоммуникационную сеть.
В сложном Эйлеровом графе существует специальный метод, который реализуется с помощью теоремы и соответственно алгоритма вьетнамского математика Хуанг-Туи для нахождения Эйлерова цикла. Этот алгоритм состоит из трех шагов:
Шаг 1. Выйти из вершины х, пройти один раз по каждому из ребер, включаемых в некоторый малый цикл (гораздо более простой, чем весь Эйлеров цикл) и вернуться в вершину х. Она будет считаться не только в исходном Эйлеровом цикле, но и базовой вершине в малом цикле. Все ребра малого цикла отметить одним цикловым индексом (например, 0). Получаем нулевой малый цикл.
Шаг 2. Выбрать в имеющемся малом цикле вершину, смежную с базовой. Эта смежная вершина тоже становится базовой, но уже для следующего малого цикла, который построить аналогично предыдущему, включая в него еще неиспользованные ранее ребра. Ориентировать ребра нового малого цикла и пометить их индексом 1. Получим первый малый цикл. Аналогично построить 2, 3, 4,… малые циклы, пока не будут обойдены все ребра графа. Каждый раз индекс цикла увеличивается на 1.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.