Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 77
Текст из файла (страница 77)
Точно так я е, как мы использовали граф Н (6, 1), 7) для изучения граней многогранника Р (6, 1), Ра), будем использовать граф ат' (6, 7) для изучения граней многогранника Р (6, да). Сначала рассмотрим результат автоморфизма группы 6. 43В ГЛ. 20. ГРАНИ ЦЮ!ОЧИСЛВННОГО МКОГ(Л'РАННИКА Твогвмх 20.7.
Если (У, Уо) — гуань многогРанника Р (6, Уо), такого, чтв у= [у(у)1 и ф: 6- 6 — любой автсмор(ригм групни 6 то (у уо) с у = [у(к)1= [у(ф ~д)1 — грань многогранника Р(6 ф уо). Прежде чем изложить доказательство этой теоремы, приведем пример. Пусть 6( — циклическая группа порядка 4, уо = уз и ф: (О, у(, уз, уз) - (О уз, уз( у ) Если [у (д(), у (дз), у (уз), уо1 — грань многогранника 1' (6„дз), то [у (уз), у (дз), у (д~), уо1 — грань многогранника Р (6„д(). Доккзлткльство. Мы будем строить доказательство в терминах графа Н (6, у) и покажем, что автоморфизм группы 6 будет переводить и' независимых кратчайших путей в и' независимых кратчай(пих путей.
Пусть р* — путь от 0 до уо в графе Н (6, у), т. е. вектор Г = [з(д)1, такой, что Х г(у) у=уз. гес Применяя автоморфизм ф к этому уравнению, имеем Х 2(у)ф(у)=-Ф(уо)= Х Г(Ф 'у) у. Таким образом, вектор Г=[2(д)1=[~(ф зу)1 дает путь р* от 0 до ф зуо. Если теперь положить у(д) =у(ф зд), то длиной пути р* в терминах у(д) будет Ху(о)(~)з у(ф~)~(ф~у)у(~)г(у)[(р) гес гас гас Итак, при автоморфизме ф путь в графе Н (6, у) дает путь в графе Н (6, у) такой же длины.
Поскольку существует ф ', то устанавливается взаимно однозначное, сохраняющее длину соответствие между путями графа Н (6, у) и путями графа Н (6, у). Кратчайшие пути в Х (6, у) независимы, так как 2 — просто перестановка компонент вектора В, а вектор з предполагается независимым. Следовательно, (у, уо) — грань многогранника Р (6, ф (до)1. ° Так как многогранник полностью определяется своими гранями, теорема 20.7 утверждает, что фактически существует только один многогранник Р (6, уо) для каждого класса автоморфиз- 20.<.
АвтомОРа измы ГНАВных мнОГОГРАнникОВ 439 мов в группе 6. Если при отображении ф: ф (уо) = до, то многогранник Р (6, уо) является достаточно симметричным. Если ф (до) =- Ь Ф уо, то многогранник Р (6, Ь) может быть получен перестановкой координат многогранника Р (6, уо). Если 6— циклическая группа простого порядка, то существует отображение р, переводящее уо в любое ненулевое Ь, так что все различные Р (6, Ь) содержат одинаковое число граней, вершин и т.
д. Ниже описано действие отображения ф на вершины. Слсдствик 20.3. Если С = [г (у)[ — вершина многогранника Р (6, до), то С = [< (д)[ — — [С (ф <у)[ является вершиной многогранника Р (6, Ф (уо)) Это утверждение справедливо, поскольку вершина определяется гранями, грань определяется )л — 1 независимыми кратчайшими путями, а мы доказалн, что прн автоморфизме независимые кратчайшие пути будут отображаться в независимые кратчайшие пути. ТВОРВМА 20.8. Пусть С = [> (д)[ — вершина многогранника Р(6, до), аС' =[У(д)),0(У(у) <>(у), длявсехус6, и Ь=- У (у) ° у. Тогда С' = [У (д)) является вершиной Р (6, Ь).
гго Эта теорема позволяет определить верн>ины многогранника Р (6, Ь), если мы знаем вершины многогранника Р (6, до). Доклаатвльство. По лемме 20.1 С вЂ” кратчайший путь от 0 до уо, если у испольауются как длины соответствующих дуг, .а С' — кратчайший путь от 0 до Ь.
Если С вЂ” верн>нна, то сущестВует <) — 1 независимых векторов у, для которых С вЂ” вершина, минимизирующая целевую функцию у. Для каждого вектора у путь С' — кратчайший в графе Н (6, у); следовательно С'— вершина. ° Елгдствис 20.4. Пусть С вЂ” вершина многогранника Р (6, уо), а С' — точка, такая, что 0 ( У (д) ( У (у) для всех д С 6, и Ь = Г' (у).у.
Если существует автомор<диам ф, такой, что фЬ = = до, то С' = [У (у)[ = [> (ф 'д')) является вершиной многогранника Р (6, уо). Доказательство следует из теоремы 20.8 и следствия 20.3. Используя следствие 20.4 и теорему 20.8, можно 'нз одной вершины многограпнйка получить многие другие его вершины. Рассмотрим, например, многогранник Р (6н, д>о). Если известно, что Г> = 3, Гт = 1 и>; = 0 (1 Ф1,7) ЯвлЯетсЯ веРшиной Р (6н, д>о), то, используя. теорему 20.8, получим различные у ( Г и Ь = = ~ У (у) д. Ння<е указываются порождаемые таким образом 44О ГЛ.
28. ГРЛНИ )4ВЛОЧНСЛКНЦОГО МПОГ))ГРЛНПИКЛ вершины различных многогранников Р (6)), Ь), где Ь новвлвется в последнем столбце (2я! + в, = во = Ь н т. д.): (тФ 1,7) Ь 0 0 0 0 0 0 3 2 2 1 0 Ез = О, все остальные компопепты равны 0; Ео=. 1, все остальные компоненты равны 0; Ео = 2, Ез —— -2, Е4 - - 1 !2=0, все остальные компоненты равны 0; все остальные компоненты равны 0; Ео=-1~ Е4=-0, все остальные компоненты равны 0; Е,о=1, все остальные компоненты равны О. Е„=-1, Е .--О, Твогвззл 20,9. Если (У, Уо) — гРань мивгвгРаниика Р(6, ло), до~О, тв (!) р(д) л у(яо — д) =-уо для всех дЕС. (й) у(д)л-у(д') у(я+д') дяя всех д, д'ЕС. (ш) у(до) =уз для всех доФО.
Донлзлтвльство. Утверждение (!) вытекает из следствия 20.2 нри )) =- С. Но теперь (1) означает, что коэффициенты у груиповык элементов связаны попарно, поскольку (у, у„) обычно нормализовано п уо —.. 1. Зная у (д), непосредственно получаем у (до — д) = 1 — у (ЕЕ). Утверждение (И) вытекает из следствия 20.1 при )) =- 6. 0 ь".з 1 ко 0 кз 1 вз 0 ь".1 1 вз Используя следствие 20.4, мо кно найти д, которое будет отображать Ь в д)о.
Например, в первой строке 7 Х Ь =- 7 Х дз=. . Дз! =- Д)о РезУльтат УмножепиЯ па 7 пеРеводит д! в Яз; таким образом, Ез = 3, Е == 0 (т Ф 7) является вершиной многогранника Р (С„, д)о). Аналогично во второй строке мы имеем 6 Х Ь = =- 6 Х до — д)о. РезУльтат УмножепиЯ па 6 пеРевоДит д! в Дз, а д! в яо. Поэтому Ео = 2, Ео .= 1, Ет =- 0 (т чь 6,9) является вершиной многогранника Р (6,), д)о). Коли бы мы умножили третью строку на 5, четвертую строку па 4, пятую строку па 10, последнюю строну на 3, мы получили бы следующ))е вершины многогранника Р (6)м ь)о): ЗВЯ. ГГЛНИ МКОГОГГЛН ПИКОВ ЦИКЛИЧВСКПХ ГГХ ПП 441 7(У)+7(до У)=7ое УЕР УФУв А'Ф О 7(У); 7(У )~7(У [ У ), Ф, У ЕР, У, У'Ф О, 7(д»О, у ба, у~ О 7(уо) =7о (если уо=-О, зто условие отбрасывается). В отличие от теоремы 20.1, условие (1) можно написать в явном виде.
Разработана программа для вычисления граней 36 много- гранников, использу|ощая зту теорему. Смотрите приложение Р и [86[. Доказательство дано в работе [86[. 20.5. Грани многогранников циклических групп В атом параграфе мы опишем способ получения семейства граней многогранника Р (6, ув), где 6 — циклическая группа. Сначала рассмотрим случай ув Ф О. В графе Н(С, 7) попытаемся получить Р— 1 независимых кратчай~пих путей. Предположим, что ув = д . Будем строить независимые кратчайшие пути следующим образом.
Первый кратчайший путь состоит из т дуг д,. Второй кратчайший путь состоит из одной дуги ув и т — 2 дуг д,. В общем случае, если р ( т, то р-й кратчайший путь состоит из одной дуги ур и из т — р дуг дп если р ь т, то р-й кратчайший путь состоит из одной дуги ун и р — т дуг цо и. Ясно, что все зти пути (р =" 1,..., Р— 1) независимы. Определим козффициенты 7 таким образом, что все зти пути будут иметь общу1о длину 1, а все другие пути будут длиннее. Пусть Р ~> — и д — м' если р (т, если р'- т. Поскольку у~о-и = — уп любой путь в графе П (С, 7) может быть заменен мпожествове д~ или — д~ без изменения общей длины пути.
Ив (1) следует, что эти Р— 1 независимых путей являются крат Утверядепие (И[) следует из теоремы 20.4, если д положить равным ув. ° Используя теорему 20.9, мы мовкем вместо теоремы 20.1, которая формулируется для многогранника Р (С, ц, ув), получить следующую теорему. Тсогвмк 20.10. НеРавенство (7, 7в), 7в ) О, опРеделЯет гРань многогранника Р (б, дв), ув =~ О, тогда и только тогда, ковда оно является допустимым базисным решением следующей системы уравнений и неравенств: 442 ГЛ. 20, ГРА1!И ЦЕЛОЧИСЛЕЦНОГО МНОГОГРАПНИКА чайшими путями. Таким образом, мы имеем способ получения гРани Р (6, ло) длЯ ло = 55о пРи любом т. )(1апРимеР, РассмотРим Р (С„яо) = Р (С„дв).
Тогда, согласно (1), -„з(1!+2(з+З(з-;-4(в ( 5(ь+6(в)=в1 является гранью. Аналогично, используя (1), можно получить грань 1 (С„яь): 7 — 6 — !! + 212 — , 'З(з ! 4(в-) 5(ь —,5 Х 7= (в) ~~1 ° —.-( --' -' Перечислим грани многогранника Р (6„8о) для всех возможнз"х хо. т (з!) т (юз) т (кз) у (81) т (юь) т (ыв) уо Можно использовать эту таблицу для получения граней многогРаппика Р(д„5в), отобРажаЯ соответственно ль, д„..., д! в Яо. Мы,можем отобразить ((ь в д„умножив дь на 4.
Этот автоморфизм 4 будет переводить д! в 4(4д1=4), дз в 1(4 хна=1) и т.д. Таким образом, получаем 2(4-Р 4(1+ 6(ь+ 812+ 10(в+ 5!з~)10, или 41! + 8(з т 512 -1- 2!в+ 6(ь + 10(в) 10, как гРань многогРапника Р (67, дв). Аналогично 5 Х д! = 20д! = = 68! = 5в, и мы полУчаем 91! .1- 412 + 612 + 811 + Зть + 121в ) 12 как грань многогранника Р (С„лв).
Рассмотрим случай Р (С, 0). Мы хотим получить 1) — 1 независимых нетривиальных кратчайших циклов от 0 до О. Это можно сделать, положив у (лр) =- РЮ и построив Р— 1 кратчайших циклов так же, как делали это для кратчайших путей. Танич образом, — ((1+ 2!з —, З(з+ 411+ 5(ь+ 6(в) ) 1 1 является гранью Р (67, до) =- Р(С7, 0). (2) Р (07 В'ь) ( 7 з!) Р (07 Хз) Р(67, Кз) Р(87', а!) 4 6 8 10 5 10 3 6 9 12 8 4 12 4 8 12 9 6 3 12 5 10 8 6 4 2 10 6 5 4 3 2 ' 1 6 20.0.
ГРАни мнОГОГРАнникОв ГОмОмОРФных ГРУ11п 44З Поскольку каждый автоиорфизм будет отображать 0 в О, то любой автоморфизм будет переводить грань Р(С, 0) в другую грань Р(С, 0). Гели рассмотрим автоморфизиы, порождаемые умножением злемептов группы соответственно на 2, 3, 4, 5 н 6, то получим из (2) следующие грани для Р(Сз, 0): 4С1 + 80 + 5гз -'- 2~1 + 6~0 -'; Згв 7, 511 -'; З~з + сз — ' 6~, + 4~0 -'- 210 ) 7, 2сз Ах 4сз + б~з ~- 11 'Г 310 + 5св ~ )7, 311 — ' 6~0 )- 2~0 — ' 5гз+ 10 —; 4гз ) 7, 6зз -Г 5гз — ' 4~0 -,'- ЗС, + 2гз + ~в .~ 7. 20.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
