Основные понятия теории графов. Гладких О.Б - 64 стр.

Определение 1.59. Сетью называется связный          действительно эквивалентна минимаксной задаче
орграф G = (М, R) без петель.                       коммивояжера.
Определение 1.60. Потоком в сети G называется             В вышеупомянутом полном ориентирован-
функция Q : R → Z, которая ставит в соответствие    ном графе G1 мы можем наверняка найти гамиль-
дуге некоторое число – вес дуги.                    тонов цикл. Пусть это будет цикл Ф1, и пусть вес
       В этих задачах фундаментальную роль иг-      самой длинной его дуги равен 1. Удалив из G1 лю-
рают изучение поперечных сечений сети (т.е.         бую дугу, вес которой не меньше 1, получим ори-
множеств дуг, которые соединяют вершины двух        ентированный граф G2. Найдем в ориентирован-
непересекающихся множеств вершин) и нахожде-        ном графе G2 гамильтонов цикл Ф2, и пусть вес его
ние ограниченного поперечного сечения, которое      самой длинной дуги равен 2. Удалим из G2 любую
является самым узким местом. Эти узкие места        дугу, вес которой не меньше 2, и так будем про-
определяют пропускную способность системы в         должать до тех пор, пока не получим ориентиро-
целом.                                              ванный граф Gm+1, не содержащий никакого га-
       Пусть G = (М, R) – неорграф = М {M1, M2} –   мильтонова цикла. Гамильтонов цикл Фm в Gm (с
разбиение множества М.                              весом m) является тогда по определению решени-
Определение 1.61. Разрезом графа G (по разбие-      ем минимаксной задачи коммивояжера, так как из
нию М) называется множество всех ребер, соеди-      отсутствия гамильтонова цикла в Gm+1 следует, что
няющих вершины из М1 с вершинами из М2 (рис.        в G1 не существует никакого гамильтонова цикла,
1.24). Отметим, что в связном графе любой разрез    не использующего по крайней мере одну дугу с
не пуст.                                            весом, большим или равным m.
                                                          Таким образом, алгоритм нахождения га-
                                                    мильтонова цикла в ориентированном графе реша-
                                                    ет также минимаксную задачу коммивояжера. На-
                                                    оборот, если мы располагаем алгоритмом решения
                                                    последней задачи, то гамильтонов цикл в произ-
                                                    вольном ориентированном графе G может быть
             М1       Разрез    М2                  найден с помощью построения полного ориенти-
                                                    рованного графа G1 с тем же самым множеством

                          64                                                 113