Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 76
Текст из файла (страница 76)
(1 — 0р! (яΠ— ид)),'т ) О. (4) Тогда кратчайший путь, использующий только дуги д С э () д будет состоять из дуг длины !)ф, (до — тд) = О, идущих от О до дΠ— тд, за которыми следу!от т дуг я длины ту Щ). Общая длина пути будет 0РО (до — шя) -)- ту (д) .= О + ту (я) =- 1. Из (3) следует, что любой другой путь от О до дО будет иметь длину, болыпую либо равную 1. Ы2! можем образовать ! Я ( -'; 1 независимых путей добавлением циклов, каждый нз которых использует 3 (д) дуг, гдо д С Я и у (д) = — О.
1'ассмотрнм элементе Я () д. Если вычисления дают у Я) =— —. О, то мы можем использовать д для образования цикла н добав.!ення его к полученным ранее кратчайшим путин, чтобы получить ) Я ( -'; 2 независимых кратчайших путей. Если вычисления (3) дают у (я) ) О, то путь от О к лΠ— тд будет иметь длину фз, 3 (дΠ— тд) и общая длина от О до до равна Орз,,—, Яо — тЯ) —, !ну(Д) =-1. Поскольку т, вь!бирается нз соотпошепкя (3), л0обые другие пути от О до яО. иснользу!ощие я, будут иметь длину болыпу!о, чем 1. Было показано, что все другие пути, пе использующие 2, име3от длину болыпую, чем 1. Так что зто — кратчайший путь, а поскольку оп использует д, он пе зависит от предыдущих путей. Рассмотрим численный пример нахождения грани многогранника Р (С, ц. уО), где 6 — цнк:шческая группа порядка 6, 3) =— (з! з2 03 00) а 00 = 03.
Тогда 1 — фО (23 — 03 32!) 1 !)!О (О) 1 у (д!) = шах ип 3 3 28 т. ху гл, зо. ГРАни Пклочислкнного многогглнникл 1 — Фв (ез — лгзег) 1 — г)зв (г!) (уг) = и!ах гз ! — 1' 3 фгцв (гз т,сз) 1 $ „(О) ! м! 1 — з)г О!е,цв,(ез- тзгь) 1 — Фв„ц,, Ог (о) 1 у (дь) =- и!ах ! ! Таким образом, 1, 2 — 1! ! — (з — гз-; — (ь~( 3 3 ' ' 3 является гранью многогранника Р (6, т(, уо).
20.3. Многогранники Р (С. до) В предыдущем параграфе мы показали, как получить грань многогранника Р (С, з), уо). Если (у, уо) — грань многогранника Р (6, з), до), накал!ем, что ( у, у,' (й)) будет гранью Р (6, Ч, и) для соответственно выбранных Ь и у,'(Ь). Это означает, что класс многогранников Р (С, Ч, уо) с различными до будет иметь грани, параллельные дРуг другу. Лгммл 2О.Э. Пусть (у, уо) дает грань Р (С, т) уо) такую что уо ~ О, т. е, имеется и' независимых кратчайших путей от О дс )з, проходящих через вершину до в гра4е Н (6, т), у). Тогда существует константа у,' (Й), так я, что (у, у„' (Ь)) определяет грань многогранника Р (6, т(, и).
Доклзлтвдьство. По предположению (у, уо) — грань; значит, имеются решения 1! (ь =- 1,..., и'), которые образуют и' линейно независимых кратчайших путей от О до уо. Пусть 1" соответствует пути от до до и. Тогда резпение 1! + 1 дает и' кратл чайших путей от О до и. Рассуждая от противного, покажем, что кратчайшие пути независимы. Предположим, что решения зависимы, тогда можно найти коэффициенты и и такие, что ~~ ьвг(1';-1л) =-О и г и!; = — 1. Ото!ода у ) ~'ш;(1! -, 1л)) =- О. Поскольку ~;!с!== ( 'и у1! =уо для всех 1, знЪлучаез! у1' ~-у1" =О или уз+у(а=О.
Но у, > О, а у и 1!' неотрицательны, так что получено противоречие. Таким образом, решения 1! + 1" независимы и (у, у,' (Ь)) является гранью многогранника Р (С, з), и). 2О.Э. МНОГОГРАННИКИ Р (О Юи Вместо рассмотрения многогранников Р (6, т~, да) с различными ле рассмотрим многогранники Р (6, т~, яз) с фиксированным лю но с различными возможными подмноисествами д~6.
Подмножество т~ не содержит О. Будет показано, что все зти многогранники Р (6, д, д~) с различными т~ являются пересечекиями главного многогранника чс соответству1ошими подпространствами. Сначала определим многогранник Р (6, 6, лс). Этот многогранник является выпуклой оболочкой неотрицательных целочисленных векторов 1, удовлетворяющих соотношению Х И(а)=ею (1) аео — б Для я, = 0 мы определяем Р (6, 6, 0) как выпуклую оболочку ненулевых неотрицательных целочисленных векторов $, удовлетворяющих (1). Назовем многогранники Р (6, 6, д~) главными лкогограккиками и для простоты будем с етого момента обозначать их Р (6, д,). Пусть Е (г1) есть и'-мерное подпрострапство (П вЂ” 1)-мерного пространства, в котором г (д) = 0 для я (( ц. Мы можем считать Р (6, т~, я,) принадлежащим этому пространству.
Все вектор-решения В дополняются компонентами т'(д) = 0 для всех д ~( ть Следующая теорема утверждает, что все многогранники Р (6, ГО я~) с различными т~ могут быть получены как пересечения главного многогранника Р (6, А',) с Е (ц). Иными словами, можно получить любой многогранник Р (6, т~, Аа) из Р (6, дц), просто полагая некоторые переменные равными нулю. ТвогкмА 20.5. Р (6, Ч До).= Р (6, йз) П Е (Ч). Доказатвльство. 11усть 1 — любой целочисленный вектор, принадлежащий многограннику Р (6, т~, яэ). Тогда 1 принадлежит очевидно Е (11).
Поскольку с удовлетворяет также (1), он принадлежит и Р (6, л~). Таким образом, Р (6, ц, ле) с- Р (6, д,)() Е (т1). Рассмотрим точку $ из Р (6, яа) П Е (д). Поскольку 1 Е Е Р (6, яа), д может быть выражена как выпуклая комбинация целочисленных точек Ф' ч Р (6, А',), где все В удовлетворяют (1). Пусть 1 = ~~Л;1' с Л; э О. Поскольку 1 с Е (т)), все компоненты т' (д) вектора 1 должны равняться 0 для д ч т~. Это означает, что все 1' должны иметь компоненты Р (д) = 0 для я й и.
Иными словами, все $' принадлежат Е (т)). Кроме того, все Г удовлетворяют (1) и, следовательно, В удовлетворяют групповому уравнению, определяющему Р (6, т~, Аэ), и все В принадлежат Р (6, т~, яе). Поскольку 1 является выпуклой комбинацией точек 1' из Р (6, т1, ла), 1 само должно принадлежать Р (6, т1, дэ). Отсюда получаем, что Р(6. ~о)ПЕ(0) ~= Р(6, Ч, й'о) И ДоиааатЕЛЬСГВО ЗаВЕРШЕПО. и Гл. 2О. ГРлпи цвлОчислвннОГО мнОГОГРлнпикл 436 Из связи между многогранником Р (6, дз) и различными многогранниками Р (6, г), уа) вытекают зависимости между гранями и вершинами многогранника Р (6, уа) и гранями и вершинами многогранника Р (6, т), да).
Следу(ощая теорема устанавливает ати зависимости. Ткогвз(л 20.6 (1) 11еравенстео (7, 7а) является (и' — 1)-мерной гранью многогранника Р (6, ц, да) тогда и только тогда, когда существует неравенство (7, уа), которое является (Р— 1)-мерной гранью Р (6, уа) с 7' (у) = 7 (л) для всех д Е 1). (1() Каждая вершина многогранника Р (6, гь уа) является вершиной многогранника Р (6, да). Вершина 1 =- (г (д)1) многогранника Р (6, да) является вершиной многогранника Р (6, г), дь) тогда и только тогда, когда 1 с Е (т)).
Презкде чем приступить к доказательству теоремы, рассмотрим, как этот факт можно использовать для получения граней н вершин многогранника Р (6, г), да), если грани и вершины многогранника Р (6, уа) известны. В табл. 20.1 перечислены грани многогранника 1' (6, да), где 6 — циклическая группа порядка 6 и да = дз.
В табл. 20.2 мы перечислили грани многогранника Р (6 т) ка) г) = (кг ь" уз Ы Таблица 20.2 получается из табл. 20.( простым отбрасыванием столбца 7,. Четвертая строка табл. 20.2 опущена, поскольку соответствующее ей неравенство является следствием других неравенств. В табл. 20.3 перечислены вершины зшогограпника Р (6е, дз), а в табл. 20.4 вершины многогранника Р (6з (у(, кг кз Уз) кз). Заметим. что вершина многогранника Р (6з, г), дз), соответствующая вершине многогранника Е' (6з, дз), существует тогда и только тогда, когда в табл. 20.3 козшонента 1(у,) = 1, = О.
Таблица 20.1. ГРак«Р(йз, ез) 7( 72 73 7( тз Таблиг(а 20,2. Граа«р (См (г(, ег, гз его ез) . 7( 72 72 7з 7о 7о 1 О 1 О 1 2 1 3 2 1 2 3 2 2 3 1 2 О О О О О 1 О О О О О 1 О О О О О 1 О О О О О 1 1 О О 1 О О 20.1. АВТОМОРФизмы г:1Авных мпоГОГРАгм1иков 437 Табаида 20Х Варв1ИИ1'1 ) ( а ба) 11 11 13 11 11 Табаича 20.4. Варшввм Р(га, Ч, ха) 1а 11 Доказлткльство творимы 20 0 (1) По теореме 20.5 Р (6, ть да) .= Р (С, да) П Е (а)).
Поскольку пересечение с Е (т)) в точности равносильно отбрасывани1о переменных 1 (д) для д ( т), а Р (6, т), да) определяется неравенствами 71 ~ ~7а, то должно существовать соответству1ощее неравенство 7 1 -- 7а, для которого 7' (д) = 7 (я) при л с 1). (й) Из теоремы 20.5 следует также, что если ( — вершина многогранника Р (6, уа), такого, что 7 (д) = О, д й т), то 4 принадлежит Е (1)) и автоматически является вершиной многогранпика Р (6, т), да). Допустим, что Г является вершиной Р (6, 1), да) но не является вершиной многогранника Р (6, да).
Тогда 4' должно быть выпуклой комбинацией неотрицательных точек В многогранника Р (6, да). Но все точки 0 должны иметь р (д) = 0 для д й 1). Иначе это будет противоречить' тому, что $' = ~~ Х1(1, ).1 ) О. Отс1ода следует, что В принадлежит и Е (т)), и многограннику Р (С, да), т.
е. 11 принадлежит Р (6, 1), да). Но 4' — вершина многогранника Р (6, да) и пе представима в виде выпуклой комбинации его точек, следовательно, получено противоречие. ° Ввиду важности многогранника Р (6, да) мы посвятим оставшуюся часть этой главы его изучению. 20А. Автоморфнзмы главных многогранников При изучении главного многогранника Р (6, да) мы увидим, что он имеет структуру, позволяющую получать из одной его грани другую, нз одной его вершины другую. Зная многогранник Р (6, да), мы будем знать и другие главные многогранники Р (6, й).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
