Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 171
Скачиваний: 0
20.2. В Ы Ч И С Л ЕН И Е |
ГРА Н И |
433 |
|
(2) Используем это значение |
у (g) вместе с у (g), g £ S, |
для |
|
вычисления ipg(j- (h) при всех |
h £ G |
аналогично тому, как |
это |
делалось в гл. 19. Когда S = т), переходим к шагу (3); в против ном случае возвращаемся к шагу (1 ), при этом число элементов множества S возрастает на 1.
(3) |
Когда |
у (g) найдены для всех g £ г), |
неравенство |
2 у (g) |
t (g) > i |
определит грань многогранника |
Р ( G , ц, g0). |
Чтобы доказать, что эти вычисления приводят к цели, надо показать, что они дадут п' линейно независимых кратчайших путей в графе Н (G, т}, у ). Не теряя общности, можно считать,
что все у (g) = 0 |
для |
g 6 S |
и мы |
хотим вычислить |
у (g). |
|
Предположим, |
что |
|
|
|
|
|
Т (^) = |
t1 — |
Ы ё о — |
mg)]/m>0. |
|
(4) |
|
Тогда кратчайший путь, использующий только |
дуги |
g £ S |J g, |
||||
будет состоять из |
дуг |
длины ф 8 (g0 — mg) = 0 , |
идущих от 0 до |
|||
go — mg, за которыми следуют т дуг g длины т у (g). Общая дли |
|||||||
на пути |
будет |
(go — mg) |
+ |
т у (g) = |
0 + т у (g) = 1 . |
Из (3) |
|
следует, |
что любой другой |
путь от 0 |
до |
g0 будет иметь |
длину, |
||
большую |
либо |
равную 1. М ы |
можем |
образовать |S | + |
1 неза |
||
висимых путей добавлением циклов, каждый из которых исполь зует s (g) дуг, где g 6 s и у (g) = 0 .
Рассмотрим элемент g $ S (J g- Если вычисления дают у (g) =
=0 ,то мы можем использовать g для образования цикла и добав
ления его к полученным ранее кратчайшим путям, чтобы полу чить |S |+ 2 независимых кратчайших путей. Если вычисле
ния (3) дают у (g) > 0 , то путь от 0 |
к g0 — m g будет иметь длину |
||
фяив (#о— |
m g) |
и общая длина от 0 |
до g0 равна |
|
|
— т 8) + т У (8) = 1 • |
|
Поскольку |
m t выбирается из соотношения (3), любые другие |
||
пути от 0 |
до g0, использующие g, будут иметь длину большую, |
||
чем 1. Было показано, что все другие пути, не использующие g,
имеют длину большую, чем 1. Так что это — кратчайший путь,
а поскольку он использует g, он не зависит от предыдущих путей.
|
Рассмотрим численный пример нахождения грани многогран |
||||||
ника Р (G, |
ц, go), где G |
— циклическая |
группа порядка 6 , т) = |
||||
= |
{gi, g2,g3,gb}, a go = |
gz- Тогда |
|
|
|
||
|
Y |
Ы |
= max 1 — фо (g3 — mj g j ) |
1 — Фо (0 ) |
1 |
||
|
3 ’ |
||||||
|
|
i |
mi |
3 |
|
||
28 |
т. x y |
|
|
|
|
|
|
434 |
ГЛ . |
20. |
ГРА Н И |
Ц Е Л О Ч И С Л Е Н Н О ГО М Н ОГОГРАННИКА |
|||
|
|
|
|
— |
1 — ^ |
fe l) |
9 |
? ( Ы = т а х ------ ^ ------ = ---- i----= Т |
|
||||||
|
|
|
1— |
1)1 |
|
|
|
У (#з) = |
нпах- |
»» . |
|
4 |
’ |
||
|
|
|
г |
|
|
|
|
У Ш |
= max |
|
|
|
|
||
|
|
|
г |
|
|
|
|
Таким |
образом, |
|
|
|
|
||
|
|
|
|
+ f ^ + |
^3 + Т h ^ |
1 |
|
является гранью многогранника Р (G, т), g0).
20.3. Многогранники Р (G, д 0)
В предыдущем параграфе м ы показали, как получить грань многогранника Р {G, т], g0). Если (у, То) — грань многогранника Р {G, г), g0), покажем, что (у, То (hj) будет гранью Р (G, т), К) для соответственно выбранных h и То (h). Это означает, что класс многогранников Р {G, г), g0) с различными g0 будет иметь грани,
параллельные друг другу.
Л емма |
20.3. Пусть (у , у0) дает грань Р (G, т), g0), такую, |
||||||
что То > |
0 , т. е. имеется п' независимых кратчайших путей от |
||||||
О до h, проходящих через вершину g0 в графе |
Н |
(G, |
т), у)- Тогда |
||||
существует константа уа’ (h), такая, что |
(у, уп (h)) определяет |
||||||
грань многогранника Р (G, т), h). |
|
|
|
|
|
||
Д о к а з а т е л ь с т в о . |
По предположению |
(у, |
у0) — |
грань; зна |
|||
чит, имеются решения |
В (г = 1, . . ., п'), |
которые |
образуют |
п' |
|||
линейно |
независимых |
кратчайших путей |
от |
0 |
до |
g0. Пусть |
В |
соответствует пути от g0 до h. Тогда решение В |
+ |
В |
дает п' крат |
||||
чайших путей от 0 до h. Рассуждая от противного, покажем, что
кратчайшие пути независимы.
Предположим, что решения зависимы, тогда можно найти
коэффициенты w t, такие, что 2 |
т г(В + В1) = 0 и 2 ы;г = 1- Отсюда |
||||||
Поскольку 2 w i= 1 и |
У 1 2 |
(t{+ t ,l)] = 0 . |
|||||
уВ = у0 для |
всех г, получаем |
||||||
|
уВ + |
у В = |
0 |
или |
|
у0 + |
у В = 0 . |
Н о у0 > |
0 , а у и В неотрицательны, так что получено противоре |
||||||
чие. Таким образом, |
решения |
В |
+ |
В |
независимы и (у, у' (h)) |
||
является |
гранью многогранника |
Р |
(G, |
т), К). |
|||
436 |
ГЛ . 20. ГРА Н И Ц ЕЛ О Ч И С Л Е Н Н О ГО М Н О ГО ГРА Н Н И КА |
Из связи между многогранником Р (G , go) и различными мно гогранниками Р (G, т), g 0) вытекают зависимости между гранями и вершинами многогранника Р (G , g0) и гранями и вершинами многогранника Р (G , тр g0). Следующая теорема устанавливает
эти зависимости.
Теорема 20.6
(i) Неравенство (у, у0) является (п' — 1)-мерной гранью мно гогранника Р (G , тр go) тогда и только тогда, когда существует неравенство (у', Уо)-, которое является (D — i)-мерной гранью
Р(G, go) с у' (g) = у (g) для всех g 6 тр
(ii)Каждая вершина многогранника Р (G, тр g 0) является вер
шиной многогранника Р (G, go). Вершина t = [t (g)]J многогран ника Р (G, go) является вершиной многогранника Р (G ,т), g0) тогда и только тогда, когда t 6 Е (т}).
Прежде чем приступить к доказательству теоремы, рассмотрим, как этот факт можно использовать для получения граней и вер
ши н многогранника |
Р (G, тр |
g 0), |
если |
грани и |
вершины много |
|||
гранника Р (G, go) известны. В |
табл. |
20.1 перечислены грани |
||||||
многогранника Р (G, |
g 0), |
где G — |
циклическая группа порядка 6 |
|||||
и go — |
g3- В табл. |
2 0 . 2 |
м ы |
перечислили |
грани |
многогранника |
||
Р (G, |
тр go), г) = [gi, g2, g3, g5 l. Таблица |
2 0 . 2 |
получается из |
|||||
табл. 20.1 простым отбрасыванием столбца у4. Четвертая строка
табл. |
2 0 . 2 |
опущена, |
поскольку соответствующее |
ей |
неравенство |
|||||||
является |
следствием |
других |
неравенств. |
|
|
|
|
|||||
В табл. 20.3 перечислены вершины многогранника Р |
(G e, g3), |
|||||||||||
а в табл. 20.4 вершины многогранника Р |
(G e, {gb |
g2, g3, g5}, g3}. |
||||||||||
Заметим, что вершина многогранника Р |
(Ge, тр g3), соответствую |
|||||||||||
щая вершине многогранника Р |
(Ge,g3), существует тогда и только |
|||||||||||
тогда, когда в табл. 20.3 компонента |
t (g4) = |
г4 |
= |
0. |
|
|||||||
|
Таблица 20.1. |
|
|
|
|
Таблица 20.2. |
|
|||||
|
Грани Р (G6, g 3) |
|
Грани Р (G6, {g i, g 2, g 3, g5}. ?з) |
|||||||||
Yi |
Yz |
Ys |
Y4 |
Y5 |
Yo |
|
Vi |
Тг |
Уз |
|
Ye |
Yo |
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
l |
2 |
1 |
3 |
2 |
1 |
3 |
|
2 |
1 |
3 |
|
1 |
3 |
1 |
2 |
3 |
2 |
1 |
3 |
|
1 |
2 |
3 |
|
1 |
3 |
1 |
2 |
3 |
1 |
2 |
3 |
|
X |
X |
X |
|
X |
X |
1 |
0 |
0 |
0 |
0 |
0 |
|
l |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
l |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X |
X |
X |
|
X |
X |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
|
l |
0 |
20.4. АВТОМОРФИЗМЫ ГЛ А ВН Ы Х М Н О ГО ГРА Н Н И КО В |
437 |
||||||||
|
Таблица 20.3. |
|
Таблица 20.4. |
|
|||||
Вершины Р (Ge, ёз) |
Вершины Р (g6, т], g3) |
|
|||||||
<1 12 £3 <4 15 |
ti |
h |
tз |
h |
|
||||
3 |
0 |
0 |
0 |
и |
3 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
2 |
0 |
|
|
|
1 |
|
0 |
2 |
0 |
0 |
1 |
0 |
2 |
0 |
|
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
|
|
0 |
0 |
0 |
0 |
3 |
0 |
3 |
|
||
Д оказательство |
теоремы 20.6 |
|
|
|
|
|
|||
(i) По теореме 20.5 |
Р |
(G ,тр g0) = Р |
(G , g0)П Е |
Сп)- Поскольку |
|||||
пересечение с Е (г|) в точности равносильно отбрасыванию пере менных t (g) для g ^ г|, а Р (G , тр g0) определяется неравенствами
yt ^5= Tot |
то должно существовать |
соответствующее |
неравенство |
||||
y't > Yo, |
для |
которого |
у' (g) = у (g) при |
g 6 |
тр |
|
|
(ii) Из |
теоремы 20.5 |
следует |
также, |
что |
если |
t — вершина |
|
многогранника |
Р (G , g0), такого, |
что t (g) — |
0, g $ г), то t при |
||||
надлежит Е (ц) и автоматически является вершиной многогран ника Р (G ,т), g0). Допустим, что t' является вершиной Р (G ,тр g0), но не является вершиной многогранника Р (G ,go)- Тогда t' должно
быть выпуклой комбинацией неотрицательных точек О многогран
ника Р |
(G ,go). Н о |
все точки В должны |
иметь Р (g) = |
0 для g $ тр |
||
Иначе |
это будет |
противоречить1 тому, |
что t' = |
^ |
> 0. |
|
Отсюда |
следует, |
что t* принадлежит |
и |
Е (ц), и |
многограннику |
|
Р (G, go), т. е. И принадлежит Р (G, ц, g0)- Н о t' — вершина мно гогранника Р (G , go) и не представима в виде выпуклой комбина ции его точек, следовательно, получено противоречие. ш
Ввиду важности многогранника Р (G , g0) м ы посвятим остав
шуюся часть этой главы его изучению.
20.4. Автоморфизмы главных многогранников
При изучении главного многогранника Р (G , g0) м ы увидим,
что он имеет структуру, позволяющую получать из одной его грани другую, из одной его вершины другую. Зная многогранник Р (G, go), м ы будем знать и другие главные многогранники Р (G ,h). Точно так же, как м ы использовали граф Н (G, тр у) для изучения граней многогранника Р (G, тр g0), будем использовать граф
Н(G, у) для изучения граней многогранника Р (G, g0). Сначала рассмотрим результат автоморфизма группы G.