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

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

112
нимаются несколько грузовиков, хотя эту задачу
можно также переформулировать как задачу ком-
мивояжера большей размерности. Другие прило-
жения включают составление расписания выпол-
нения операций на машинах, проектирование
электрических сетей, управление автоматическими
линиями и т.д.
Очевидно, что сформулированная выше за-
дача (1) является частным случаем задачи (2). В
самом деле, приписывая случайным
образом дугам
заданного ориентированного графа G конечные
веса, получаем задачу коммивояжера. Если реше-
ние для этой задачи, т.е. кратчайший гамильтонов
цикл, имеет конечное значение, то это решение
является гамильтоновым циклом ориентированно-
го графа G (т.е. ответом на задачу 1). Если же ре-
шение имеет бесконечное значение, то G не имеет
гамильтонова цикла.
С другой стороны можно дать еще одну ин-
терпретацию задачи 1). Рассмотрим снова полный
ориентированный граф G
1
с общей матрицей весов
дуг [c
ij
] и рассмотрим задачу нахождения такого
гамильтонова цикла, в котором самая длинная дуга
минимальна. Эту задачу можно назвать минимакс-
ной задачей коммивояжера. Тогда классическую
задачу коммивояжера в той же терминологии
можно было бы назвать минисуммной задачей
коммивояжера. Покажем теперь, что задача (1)
65
Рис. 1.24.
Определение 1.62. Непустой разрез К неорграфа
G называется простым разрезом или коциклом,
если любое непустое собственное подмножество
К.'
⊂
≠
К не является разрезом ни по какому раз-
биению.
Другими словами, из К нельзя удалить ни
одно ребро с тем, чтобы полученное множество
было непустым разрезом.
Пусть G = (М, R) – неорграф, имеющий п
вершин, т ребер и с компонент связности, Т – ос-
тов графа G и и
i
, ..., u
n – c
, – ветви остова. Удаляя из
остова Т произвольную ветвь и
i
, получаем лес с
(с.+.1) компонентами связности, т. е. каждое ребро
и
i
является разрезом остова Т по некоторому раз-
биению {M
1
, M
2
} (рис. 1.25).
В графе G могут найтись еще какие-то ребра
v
1
i
, v
2
i
,..., v
j
i
(являющиеся хордами Т), которые со-
единяют вершины из M
1
и М
2
.
М
1
М
2
и
i
нимаются несколько грузовиков, хотя эту задачу                               Рис. 1.24.
можно также переформулировать как задачу ком-        Определение 1.62. Непустой разрез К неорграфа
мивояжера большей размерности. Другие прило-         G называется простым разрезом или коциклом,
жения включают составление расписания выпол-         если любое непустое собственное подмножество
нения операций на машинах, проектирование
                                                     К.' ⊂  ≠ К не является разрезом ни по какому раз-
электрических сетей, управление автоматическими
линиями и т.д.                                       биению.
      Очевидно, что сформулированная выше за-                    Другими словами, из К нельзя удалить ни
дача (1) является частным случаем задачи (2). В      одно ребро с тем, чтобы полученное множество
самом деле, приписывая случайным образом дугам       было непустым разрезом.
заданного ориентированного графа G конечные                      Пусть G = (М, R) – неорграф, имеющий п
веса, получаем задачу коммивояжера. Если реше-       вершин, т ребер и с компонент связности, Т – ос-
ние для этой задачи, т.е. кратчайший гамильтонов     тов графа G и иi, ..., un – c, – ветви остова. Удаляя из
цикл, имеет конечное значение, то это решение        остова Т произвольную ветвь иi, получаем лес с
является гамильтоновым циклом ориентированно-        (с.+.1) компонентами связности, т. е. каждое ребро
го графа G (т.е. ответом на задачу 1). Если же ре-   иi является разрезом остова Т по некоторому раз-
шение имеет бесконечное значение, то G не имеет      биению {M1, M2} (рис. 1.25).
гамильтонова цикла.                                              В графе G могут найтись еще какие-то ребра
      С другой стороны можно дать еще одну ин-       v i1 , v i2 ,..., v i j (являющиеся хордами Т), которые со-
терпретацию задачи 1). Рассмотрим снова полный       единяют вершины из M1 и М2.
ориентированный граф G1 с общей матрицей весов
дуг [cij] и рассмотрим задачу нахождения такого
гамильтонова цикла, в котором самая длинная дуга
минимальна. Эту задачу можно назвать минимакс-
ной задачей коммивояжера. Тогда классическую                                     иi
задачу коммивояжера в той же терминологии
можно было бы назвать минисуммной задачей
коммивояжера. Покажем теперь, что задача (1)

                                                                    М1
                          112                                                         65 М2

Страницы