Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

438

ГЛ .

20. ГРА Н И Ц ЕЛ О Ч И СЛ ЕН Н О ГО М Н ОГОГРАННИКА

Теорема

20.7. Если (у, у0) — грань

многогранника Р (G, g0),

такого, что

у = [y(g)]

и Ф : G - + G — любой

автоморфизм

груп­

пы G,

то

(Yi То) с

Y =

[y(g)] = [Т(Ф-1£)] —

грань многогранника

P{G,

ф g0).

Прежде чем изложить доказательство этой теоремы, приведем

пример.

группа порядка 4, g0 = g3 и

Пусть

Сг4

— циклическая

Ф-

(0,

gu ёъ

§-3) ^ ( 0 ,

ёз, ёг, gi)-

Если [у (ё1), Т (Ы- Т (ёз), То! “ грань

многогранника Р

(G4, g3),

то [у (ёз), Т (ёз), Т (Ы,

То1 — грань

многогранника Р

(G4, gt).

Д оказательство.

М ы

будем строить доказательство

в

терми­

нах графа Н

(G, у) и покажем, что автоморфизм группы G

будет

g i G

g £ G

Таким образом, вектор

t= [F(g)] = [t(ф~хё)] дает путь р* от О

2 У (ё)Нё) =

2 Т (Ф~*ё) t (ф-гё) =

2 Т (ё) t (ё) = I (?*)■

g £ G

g £ G

g £ G

20.4. АВТОМ ОРФИЗМ Ы

ГЛ А В Н Ы Х

М Н ОГО ГРА Н Н И КО В

439

мов в группе G. Если при отображении

ф : ф (g0) = got то много­

гранник Р (G , go) является

достаточно симметричным.

Если

Р

(G, h) содержат одинаковое число граней, вершин и т. д. Н и ж е

описано действие

отображения

ф

на

вершины.

Следствие 20.3.

Если

t =

[t

(g)] —

вершина многогранника

Р

(G, go), то t =

[t

(g)] =

[t (ф~1g)] является вершиной многогран­

Теорема

20.8.

Пусть

t = [t (g)] — вершина

многогранника

Р

(G, g0), a t' =

[t' (g)], 0 <

t' (g) <

t (g), для всех g £ G,

и

h

=

=

2

t' (g)-g■

Тогда

t' =

\t' (g)]

является вершиной P

(G,

h).

sec

Эта

теорема

позволяет

определить вершины

многогранника

Р

(G, К), если м ы

знаем вершины многогранника Р (G, g0).

Д оказательство.

По лемме 20.1

t —

кратчайший путь

от 0

до

go,

если

у

используются как

длины

соответствующих

дуг,

Следствие

20.4. Пусть t —

вершина многогранника Р (G, g0),

а V — точка, такая, что 0 ^

(g)

t' (g) для всех g £ G, U h =

—

(g)•g. Если существует автоморфизм ф, такой, что фк =

=

g0,то t' =

[V (g)] = [t(<p_1g')l является вершиной многогранника

Р

(G, g0).

Доказательство следует из теоремы 20.8 и следствия 20.3.

Используя

следствие 20.4

и теорему 20.8, можно из одной

Рассмотрим,

например, многогранник Р (С?и , gio)- Если известно,

что ti = 3, t-j =

1 и tj =

0 (/ ф 1,7) является вершиной Р

(Gn ,g10),

то,

используя

теорему

2 0 .8 , получим различные t ' ^

t и h =

=

(*)•g.

Н и ж е указываются порождаемые таким

образом

и

h

tm ( т ф 1,7)

h

3

0

0

gs

2

1

0

g9

2

0

0

g%

1

1

0

1

0

0

gi

0

1

0

gi

образом, t7 = 3, tm =

0 (т ф

7) является вершиной многогран­

ника Р

= 6 X

ft = gjoРезультат умножения

на 6

переводит gt в ge,

a g7 в g$. Поэтому te =

2, t9 =

1, tm

=

0 (т ф

6,9) является вер­

шиной

многогранника

Р (Gu , g10).

Если бы

м ы умножили тре­

7? = 3,

<5

—

0? все

остальные

компоненты

равны 0

;

h = 2

,

<9

=

1 > все остальные

компоненты

равны 0

;

h = 2

,

<2 = 0 , все

остальные

компоненты

равны 0

;

74= 1 ,

<0=

1) все остальные

компоненты

равны 0

;

^10 = 1 ,

<4 =

0 , все остальные компоненты равны

0 ;

h = 0,

<10 =

1! все остальные компоненты равны 0.

Т е о р е м а

20.9.

Если

(у, Уо)— грань многогранника

Р (G, g0)r

g0^ 0, то

(i) y(g) +

y(go —

g) =

Vo для всех g£G.

(ii) у (g)+

у

(g')> у (g + g') для всех g, g' 6 G.

заны попарно, поскольку (у, у0) обычно нормализовано и у0

= 1 .

Зная у (g), непосредственно получаем у (g0 —

g) = 1 —

у (g).

Утверждение (ii) вытекает из следствия 20.1

при р = G.