Аналитическое и компьютерное исследование комбинаторных конусов и многогранников тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Центральный Экономико-Математический институт РАН

Р Г Б ОД

2 8 АВГ 1995 пРавах рукописи

ГРИШУХИН Вячеслав Петрович

АНАЛИТИЧЕСКОЕ И КОМПЬЮТЕРНОЕ ИССЛЕДОВАНИЕ КОМБИНАТОРНЫХ КОНУСОВ И МНОГОГРАННИКОВ

(Специальность: 01.01.09. - Математическая кибернетика)

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва 1995

Работа выполнена в Центральном экономико-математическоь институте РАН.

Официальные оппоненты: академик РАН Шуравлев Ю.И.

Ведущая организация: Институт проблем передачи информации

в ФО часов на заседании диссертационного совета по математической кибернетике и экономико-математическим методам Д 002.27.02 при ЦЗМИ РАН по адресу: 117418, Москва, ул. Красикова 32, ЦЭМИ РАН, комн. 520.

С диссертацией можно ознакомиться в библиотеке ЦЭМИ РАН.

доктор физико-маематических наук, профессор Рышков С.С. доктор физико-математических наук, A.C.Немировский.

РАН.

Защита диссертации состоится

Автореферат

Ученый секретарь специализированного совета к.ф.-м.н.

В.А.Скоков

Актульность_темьк Как видно из заглавия, работа посвящена следованию комбинаторных конусов и многогранников. Уже на ачальных этапах своего развития дискретная оптимизация толкнулась с комбинаторикой и комбинаторной оптимизацией. Более зго, дискретная оптимизация явилась стимулом бурного развития змбинаторного анализа в последние десятилетия.

Дискретная оптимизация часто имеет дело с многогранниками и югогранными множествами, чьи экстремальные элементы (вершины, зайние лучи или грани максимальной размерности, называемые в шьнейшем, ради краткости, фасетами) тем или иным способом зязаны с комбинаторными объектами. Я называю такие многогранники конусы комбинаторными.

Следует отметить, что проблема определения фасет югогранного конуса, заданного как конусная оболочка своих 'чей, является типичной и важной для дискретной оптимизации, юйственная проблема нахождения крайних лучей с алгоритмической >чки зрения идентична прямой. Для комбинаторного конуса нудности этих проблем уменьшаются возможностью использовать ■руктурные его особенности, например, такие как симметрия или (мкнутость лучей или фасет относительно некоторых операций.

Можно выделить несколько направлений исследования мбинаторных конусов и многогранников.

1. Нахождение и изучение целочисленных многогранников, личных от многогранников с вполне унимодулярной матрицей раничений. Обычно такие многогранники связаны с некоторыми ассами комбинаторных объектов, например, матроидами, вершенными графами, субмодулярными функциями.

2. Многие условия или ограничения на существование некоторых ъектов в физике, экономике, комбинаторике и т.п. описываются нейными неравенствами в пространстве параметров. Например, трики выделяются среди всех функций на парах точек равенствами треугольника, субмодулярные функции - линейными ловиями субмодулярности, и т.п. В этих случаях фасеты ответствующего многогранного множества дают необходимые и

з

достаточные условия принадлежности данного объекта выделенному классу.

3. Выше названные системы неравенств могут иметь очень большое, иногда бесконечное, число неравенств. Поэтому возникает вопрос, достаточно ли конечного числа неравенств, и если да, тс определения минимального множества необходимых неравенств. -Е случае конечности системы неравенства минимальной системы определяют фасеты соответствующего полиэдрального конуса.

4. Двойственность - типичное явление комбинаторики. Если класс комбинаторных объектов описывается конусом, то двойственный конус определяет класс двойственных комбинаторных объектов. Системы неравенств, определяемые крайними лучами прямого конуса, дают необходимые и достаточные условия принадлежности классу двойственных комбинаторных объектов. Например, крайние лучк конуса метрик определяют необходимые и достаточные условия допустимости параметров многопродуктовой задачи.

5. Частичное описание фасет комбинаторного конуса ведет, с одной стороны, к выделению некоторых необходимых услови? принадлежности, а с другой стороны, выделяет новый класс объектов, для которых эти условия являются и достаточными. Чаете эти новые классы более обозримы, чем исходные. Например, разрезные крайние лучи конуса метрик выделяют разрезные многопродуктовые задачи.

6. Обычно у комбинаторного конуса грани произвольной размерности соотнесены с некоторыми комбинаторными объектами. Е этом случае фасеты и крайние лучи комбинаторного конуса выделяют класс экстремальных комбинаторных объектов, а классификация фасет и крайних лучей дает естественную классификацию экстремальный объектов.

7. В современной комбинаторике важную роль играют компьютерные вычисления. С давних времен, вычисления - эте своеобразный эксперимент в математике, подтверждающий юл опровергающий выдвинутые предположения. Но в наше врем? вычисления приобретают новую роль. С одной стороны, эте

инструмент решения задач больших размеров, а с другой - это порой единственная возможность полного перечисления неэквивалентных комбинаторных объектов, а иногда и единственный способ цоказательства комбинаторных теорем.

Для наиболее типичных функций, определенных на парах элементов некоторого л-элементного множества, значение л=7 является критическим. Экстремальные элементы конусов таких функций для л^б, когда размерность конуса $15, обычно вычисляются пегко, часто даже вручную. Для п=7 или п=8 (размерность равна 21 л 28) вычисления возможны с помощью современной ЭВМ, но не в прямую, а с некоторыми ухищрениями. Для больших значений л, вычисления до конца практически невозможны.

Эти и другие проблемы исследования комбинаторных чногогранных множеств и комбинаторной оптимизации привлекают все эольшее внимание и получают все большее развитие.

Все выше сказанное, а также неослабевающий интерес к данной эбласти, позволяют сделать вывод об актуальности темы настоящей заботы.

Цель_работы - построение крайних лучей и фасет комбинаторных -сонусов, а также комбинаторных объектов, определяющих эти лучи и фасеты. Основные результаты работы состоят в решении ряда проблем толиэдральной комбинаторики. В частности,

объяснена природа целочисленности субмодулярных многогранников;

доказана экстремальность ранговой функции связной юлумодулярной решетки и даны две конструкции построения экстремальных решеток из геометрических решеток;

- решена проблема Ловаса об описании фасет конуса графских зазрезных функций, как частный случай описания фасет конуса эазрезных функций в однородном гиперграфе;

- доказана полиэдральность конуса альтернирующих функций,

- дано явное доказательство конечности числа ¿-типов >многогранников, на основе которого доказана полиэдральность <онуса гиперметрик, исходно определяемого бесконечным числом

неравенств;

- дано конкретное описание ¿-многогранников, соответствующие-фасетам гиперметрического конуса, на основе чего доказанг принадлежность классу соИР задачи определения гиперметричност> данной метрики; показана связь экстремальных ¿-многогранников с совершенными решетками; доказана экстремальность нескольким ¿-многогранников;

- с помощью компьютера доказана полнота списка типов фасет 21-мерного конуса разрезных (т.е. хэмминговых) метрик на 1 точках;

- найден список всех типов крайних лучей 21-мерного конусг метрик на 7 точках, и доказана полнота списка крайних луче{ 15-мерного конуса метрик на 6 точках.

Аппробация_работы. Результаты диссертации докладывались ш республиканских, всесоюзных и международных конференциях, симпозиумах и школах-семинарах: - IV цикл заседаний Всесоюзногс семинара по дискретной математике в г.Одессе, 1977г., - Семина| по дискретной оптимизации в ЦЭМИ, 1975-1985гг. - Всесоюзны! симпозиум "Системы программного обеспечения решения зада* оптимального планирования", Минск, 1986г. - III Всесоюзная школг "Дискретная оптимизация и компьютеры", Гаштагол, 1987г. 2-я Международная конференция "Кодирование и вычисления", Париж 1989г. - Семинар Института анализа систем и информации (1АБ1) Рим, 1990г. - Международная конференция по алгебраическое комбинаторике, Владимир, 1991г. - Семинар ИМАГ "Дискретна; математика и приложения", Гренобль, 1992.

Публикации. Результаты диссертации опубликованы в работа: [1]-[22].

Структура и объем работы. Диссертация состоит из введения 1 четырех глав, каждая из которых разбита на разделы и подразделы и занимает 140 страниц машинописного текста. Нумерация лемм, предложений, теорем и следствий следующая: первая цифр; соответствует номеру главы, вторая - подразделу, последняя

номеру в разделе. Список литературы содержит 65 наименований.

Перейдем к подробному изложению работы по главам.

Езава_1. В первой главе изучаются субмодулярные конуса и субмодулярные многогранники, являющиеся сечениями субмодулярных конусов некоторой гиперплоскостью. Основной результат этой главы (Теоремы 1.8 и 1.9) состоит в доказательстве того, что каждый субмодулярный многогранник есть такое пересечение более простых многогранников, что каждая вершина исходного многогранника есть некоторая вершина простого многогранника.

Полиматроид, интенсивно изучавшийся Эдмондсом в 70-х годах, а также субмодулярно-графовый многогранник Эдмондса и Джайлса, являются частными случаями субмодулярного многогранника.

Специальный тип субмодулярного многогранника, связанного с решеткой, рассматривался Хоффманом и Шварцем. В своей статье 1973 г. Хоффман поставил вопрос о едином описании этих многогранников. Такая единая точка зрения дается в первой главе.

Субмодулярные конуса ограничиваются гиперплоскостями, направляющие векторы которых являются субмодулярными вектор-функциями, определенными на решетке (или более общо, на квазирешетке).

Квазирешетка определяется через понятие параллельности (иногда называемое ламинарностью) элементов дистрибутивной решетки, обобщающее понятие сравнимости элементов произвольной решетки. Элементы а и Ь конечной дистибутивной решетки называются параллельными (обозначается а|b), если выполнено хотя бы одно из следующих условий

аЛ b=0, aVb=l, а<Ь, (т.е. аКЬ=а) , а}Ь, (т.е. аЛЬ=Ь). (1) Если 1 не дистрибутивна, то a,b?L называются параллельными, если они сравнимы, т.е. если для них выполнено одно из двух последних условий в (1).

Чтобы иметь возможность рассматривать решетки и квазирешетки одновременно, к каждой недистрибутивной решетке добавляются такие новые ноль 0° и единица 1°, что CP<0<1<10. Тогда, подразумевая в

(1) под о и 1 эти новые ноль и единицу, получим, что для измененной решетки первые два условия в (1) никогда не выполняются. Аналогично изменяется дистрибутивная решетка, есл!-ее нужно рассмотреть как квазирешетку.

Пусть L - произвольная решетка. Подмножество SQL называется нвазирешеткой, если

(l) OjfS, lj[S, (2) a£S => a ¿S, (3) a,biS И а не | b =» аЛЬ, aVbiS, где а есть дополнение а в L. Если все элементы квазирешетга попарно параллельны, то она называется параллельным семейством.

Множество дуг D ориентированного дерева т можно снабдить частичным порядком следующим образом. Любые две дуги а и t соединены в г единственной цепью с(а,ь). Пусть a,biD. Тогда

1) акь=ь, т.е. äzb, если в цепи с(а,ь) дуги а и ь имеют одинаковое направление, и дуга а стоит раньше Ь, идя в эток направлении: а-* —b.

2) аЛЬ=о, если в цепи c(a,b) дуги а и ь имеют противоположное направление и направлены друг от друга: а<-—>ь.

3)aVb=l, если в цепи c(a,b) дуги а и b имеют противоположное направление и направлены друг к другу: а-><~-ь.

Нетрудно проверить, что замена дуги а на противоположнун

эквивалентна замене а в £>, рассматриваемом как параллельное

*

семейство, на его дополнение а .

Теорема 1.4. Пусть D - квазирешетка. Следующие утверждение эквивалентны.

(i) D - параллельное семейство,

(ii) D - множество дуг некоторого дерева Т.

Функция f, определенная на квазирешетке s, называется субмодулярной, если для любых a,bes таких, что аЛЬ, avbes. выполнены следующие неравенства субмодулярности

f(a)+f(b)-f(aVb)-f(aAb)zo. (2)

Функция f называется супермодулярной, если -f субмодулярна. : называется модулярной, если она одновременно суб- i супермодулярна.

Следующие две в некотором смысле двойственные друг друп

теоремы обусловливают основные свойства субмодулярных конусов и многогранников.

Теорема 1.6. Пусть D есть максимальное параллельное подсемейство в квазирешетке S. Тогда для любой субмодулярной функции f на S справедливы соотношения

f<a> ? 2hcnhn(a.b)f(b). (3)

btD D

Для коэффициентов h^(a,b) выполнены условия

h f* h)-i° или iX яля biD (a), nBia,Dj |0 или 1 для biDhD^(a)t

где D (a)=[c(D:с не \ а]. Если f - модулярна, то неравенства (3) выполняются как равенства.

Теорема 1.7. Пусть y:S—»[R есть произвольная неотрицательная ограниченная функция на квазирешетке S. Существует параллельное семейство DSS и неотрицательная функция у^ на S с носителем в D, т.е. Ур(а)=0 для af[D, такие что

для всех субмодулярных функций на S. Неравенство (4) выполняется как равенство для всех модулярных функций.

Отметим связь между теоремами 1.6 и 1.7. Если умножить (3) на у(и просуммировать по всем ats, то мы получим (4) с yD(a)=Eb^sy(b)hD(b,а). Доказать, что для этой функции yD существует семейство D такое, что уд неотрицательная, удается только для квазирешетки S, которая является дистрибутивной решеткой, когда D есть цепь сравнимых элементов. (См. [6]).

Субмодулярный конус C(f,s)QjRE, связанный с квазирешеткой s, определяется следующим образом

= ,_/(а,е)х 5=0, aiS, х eiE],

е(.Е е е

где f(•,е) субмодулярна на s для всех е.

Теорема 1.8. Пусть V есть множество всех максимальных параллельных подсемейств IXS. Тогда конус C(f,S) есть такое пересечение конусов C(f,D), DiV, т.е. С (f, S)=f) (f ,D) , что каждый крайний луч конуса C(f,S) есть крайний луч конуса C(f,D) для некоторого DiV.

Субмодулярный многогранник лежит в сечении субмодулярного

конуса C(f,s) гиперплоскостью для некоторого e'tE:

где £'=£-(e'), g(a)=-f(a,e').

Теорема 1.9. P(f,S)=flI}ç£)P(f,D), и каждая вершина P(f,S) есл вершина P(f,D) для некоторого Did.

Из Теоремы 1.9 вытекает

Следствие 1.10. Если все вершины многогранника P(f,L целочисленны для любого Did, то все вершины P(f,S) тон целочисленны.

В частности многогранник p(f,D) целочисленен, если ег матрица A (f) ограничений f(a)xïg(a) вполне унимодулярна. Строк матрицы A^if) нумеруются элементами aiD, а столбцы - элементам etE, т.е. (а,е)-ый элемент матрицы A (f) есть f(a,e).

Скажем, что вектор-функция f=f(a,e) обладает цепнь свойством, если f(а,е) принимает значения 0 или ±1 удовлетворяет следующему условию. Для каждого eiE пересечена Ce=SeílB носителя s ={ aiS:f(a, е)/0) функции f(°,e) с любь параллельным семейством D есть связная цепь в дереве соответствующем D. При этом можно выбрать направление Tai-чтобы f (а,е)=1, если направления дуги а и цепи Cg совпадают, f (а,е)=-1, если эти направления противоположны.

Если f обладает цепным свойством, то для любого D матри1. AD(f) есть матрица инциденций дуг и цепей [Ce:eiE] в дереве i Хорошо известно, что такая матрица вполне унимодулярна. Вс известные целочисленные субмодулярные многогранники определяютс вектор-функциями f, обладающими цепным свойством.

В разделе 1.5 приведены 5 субмодулярных многогранникон (1) полиматроид, (2) пересечение к полиматроидов, которс целочисленно лишь при 2, (3) многогранник Хоффмана-Шварца, (< многогранник Эдмондса-Джайлса, (5) многогранник корневь ветвлений.

Подобную причину целочисленности могут иметь и многогранни? другого типа, например, многогранник паросочетаний. Этс

многогранник также есть пересечение простых многогранников того же типа. Все эти многогранники определяются ограничениями, которые являются функциями на некоторой алгебре. Эти функции обладают свойством подобным субмодулярности. Здесь простые многогранники имеют нецелые вершины, но пересечение таково, что нецелые вершины отсекаются, (см. [2]).

Глава_П- Из первой главы видно, какую важную роль играют субмодулярные функции в дискретной оптимизации и полиэдральной комбинаторике. Субмодулярные функции имеют многочисленные приложения в комбинаторной математике (где они возникают как ранговые функции матроидов и, общее, полумодулярных решеток), в теории игр (в которых супермодулярная функция определяет выпуклую кооперативную игру), в теории оптимизации (в особенности, в сетевых задачах).

Так как субмодулярные функции выделяются, среди всех функций множеств конечным числом линейных неравенств субмодулярности (2), то они заполняют в пространстве в(]/)=2у, всех функций

множеств многогранный конус С (V).

В второй главе рассматриваются подконусы конуса С (V), соответствующие некоторым подклассам субмодулярных функций. А именно, заостренный конус С (.V) монотонных субмодулярных функций, принимающих значение 0 на пустом множестве " 0, конус Л(у) альтернирующих функций, имеющий в качестве крайних лучей субмодулярные (0,1)-функции, и конус П{у) разрезных субмодулярных функций, определяемых разрезами в гиперграфах. -

В первом разделе этой главы показано, что крайние лучи конуса С (V) определяются классом К связных экстремальных решеток, и доказано, что всякая связная полумодулярная решетка принадлежит а ее ранговая функция экстремальна. Даны две конструкции построения решеток класса К из геометрических.

Во втором разделе доказана полиэдральность альтернирующего конуса Л(у). Используя этот результат, в третьем разделе решена

проблема Ловаса об описании фасет конуса графских разрезны? функций, как частного случая описания фасет конуса разрезнш функций в однородном гиперграфе.

Густав Шоке в 1955 г. первым затронул проблему нахождения крайних лучей конуса С (ь) монотонных субмодулярных функций нг бесконечной решетке I. Он описал крайние лучи подконусг Л(1)сС0(ь) альтернирующих функций на I.

В 1970 г. в своей замечательной работе "Субмодулярные функции, матроиды и некоторые многогранники" Дж. Эдмондс впервые явно поставил проблему нахождения крайних (экстремальных) луче! конуса С (V) монотонных субмодулярных функций на булевой алгебре в(V) всех подмножеств множества V.

Неявно эта проблема поставлена Л.Шэпли в 1971г., которьп изучал выпуклые кооперативные игры, определяемые супермодулярным! функциями. М.Розенмюллер и Х.Вайднер (1974г.), побуждаемые исследованиями Шэпли, описали некоторые свойства систе» уравнений, определяющих крайние лучи конуса монотонны; супермодулярных функций.

В разделе 2.1 изучаются крайние лучи конуса С СV) монотонны; субмодулярных функций, выделяемых из конуса С (V) условиям! монотонности

/(0)=О И /(я)^/(т), если 5£Х£У.

Проблема нахождения крайних лучей С (V) сводится к изученш крайних лучей конусов С0(ь) монотонных субмодулярных функций н; произвольной конечной решетке I и сюръективных У-морфизмо1 решеток, т.е. таких отображений <р:Ь— Ь', что ф(аУЬ)=ф(а)уф( ь) дл! любых а,ЬЦ. Это связано с тем, что всякая функция /еС (V определяет сюръективный У-морфизм а булевой алгебры 2У н; решетку /-замкнутых множеств:

0 (5)=тах{Т: ГЭ^, Г)=^Сз)} . Сюръективные У-морфизмы решеток рассматриваются в разделе 2.1.2.

Любую (0,1)-функцию пС0(ь) можно рассматривать ка] монотонное отображение решетки ь в двухэлементную решетк; 2=[СМ1] .

Предложение 2.1.2. Для монотонной (О,1)-функции £ на решетке Ь следующие утверждения эквивалентны:

(1) £ есть V-морфизм I в 2,

(2) £ субмодулярна на I.

Функция, лежащая на крайнем луче С (ь) называется экстремальной. Связь экстремальных функций и \/-морфизмов отражает следующая основная теорема раздела 2.1.

Теорема 2.1.4. Пусть (р:Ь—>Ь' есть сюръективный V-морфизм, £':Ь'—>К - произвольная функция и Тогда

(1) ££С0(1) тогда и только тогда, когда £'(.С0(Ь'),

(2) £ и £' одновременно экстремальны или нет.

Так как гс С 0(V) строго монотонна на ь(£), то задача классификации экстремальных функций конуса С (V) сводится к задаче определения класса К решеток ь, для которых конус С0(ь) имеет строго монотонные экстремальные функции. Вторая часть раздела 2.1 посвящена изучению и построению некоторых решеток класса £. Так как С0(2) есть луч, то простейшая решетка 2 этого класса определяет (0,1)-экстремальные лучи С0С V"), принимающие с точностью до множителя значения 0 и 1.

Для решеток класса К важно понятие связности, которое изучается в разделе 2.1.4.

Скажем, что пара элементов с(, с^ решетки ь образует фактор с(/с2, если с2<с(. Факторы вида а/аЛЬ и аУЬ/Ь называются перспективными. Фактор а/ь называется простым, если а покрывает ь (обозначается ауЬ). Транзитивное замыкание отношения перспективности на множестве простых факторов называется отношением проективности. Отношение проективности есть эквивалентность, разбивающая множество всех простых факторов на непересекающиеся классы проективности Р. Назовем решетку связной, если . все ее простые факторы принадлежат одному классу проективности.

Решетка называется простой, если она допускает лишь две конгруэнции: нулевую, когда все элементы эквивалентны, и единичную, когда каждый элемент составляет класс эквивалентности.

Нетрудно показать, что если конгруэнция 9 сжимает фактор а/ь, т.е. а=ь(9), то 6 сжимает все факторы, проективные а/Ь. Отсюда следует, что связные решетки просты.

Поскольку модулярная решетка проста тогда и только тогда, когда все ее простые факторы проективны друг другу (Биркгоф, Теория решеток, 1967), то понятия связности и простоть: эквивалентны для модулярных решеток. В разделе 2.1.5 показано, что это верно и для геометрических решеток. В общем случае это не так. Из теоремы Дилуорса следует лишь, что два простых факторг простой решетки слабо проективны друг другу (Гретцер, Общая теория решеток, 1983). Действительно, существуют простые несвязные полумодулярные решетки. В [11] приведен пример простор несвязной полумодулярной решетки с двумя классами проективности.

В разделе 2.1.5 доказывается следующая

Теорема 2.1.12. Полумодулярная решетка имеет строгс монотонную экстремальную функцию тогда и только тогда, когда онг связна, и в этом случае такая функция единственная и совпадав1 с ранговой функцией этой решетки.

Эта теорема является обобщением следующего результата Нгуенг (1978)

Следствие 2.1.13. Ранговая функция матроида экстремальш тогда и только тогда, когда этот матроид связен.

В разделе 2.1.6, исходя из геометрических решеток, построено два подкласса класса К. В конце этого раздела приведе! список из 6 решеток класса определяющих 41 экстремальный луч конуса С0(У4) для 4-элементного множества V Эти функции бьш подсчитаны С.А.Куком, и приведены в работе Шэпли (1971).

В разделе 2.2 второй главы рассматривается конус А{у\ альтернирующих функций. Альтернирующие функции на бесконечны: решетках (и даже на более общих образованиях - упорядочении: коммутативных полугруппах) рассмотрел Г.Шоке (1955). Исходнс конус Л(у) определяется равенством /(0)=О и бесконечньп множеством альтернирующих неравенств

Етез(-1)'г1Г(Ж1Л(Г))«0, (5)

где л(г)=и А(, A^V, для любых хк v и произвольных индексирующих множеств s. Легко видеть, что Л(v)cC (V). Доказывается, что крайние лучи конуса A(v) есть (0,1) -экстремальные функции q €C„(V) такие, ЧТО q,(X)=l, если ХП Ait, и q ( А")=0 в противном

АО Л А

случае. Это уточняет результат Шоке для бесконечных решеток Так как (0,1)-субмодулярные функции образуют базис всех функций множеств с f{0)=0, то конус Aiv) симплициален. Поэтому легко находятся его фасеты. Это зафиксировано в следующей теореме.

Теорема 2.2.2. Конус A(V) альтернирующих функций имеет 2п-1, п=| V\ , крайних лучей, которыми являются все 2п-1 функций qA для 0J-AZV. Фасеты конуса A(V) определяются 2^-1 неравенствами

,r%ru(-l)\B~A I f(B) $ О, А с V, A t V,

которые эквивалентны всем неравенствам (5) для f с f(0)=O.

В разделе 2.3 находятся фасеты конуса 1i2(v) разрезных субмодулярных функций. Разрезные функции - это наиболее известные и часто встречающиеся субмодулярные функции. На Боннской конференции по математическому программированию 1982г. Л.Ловас высказал удивление, что так мало известно о конусе разрезных функций, и поставил вопрос о нахождении неравенств, которым удовлетворяют разрезные функции. В диссертации сделано больше, а именно, найдены неравенства, определяющие фасеты этого конуса:

Если G есть граф, ребра (ij) которого имеют неотрицательный вес c(ij), то разрезная функция, порожденная графом G, имеет значение f(s) = 2 у.c(ij') на подмножестве s множества вершин v

I ч Ь f j ft Ь

графа g. Крайними лучами конуса R (V) являются . функции m

с. I J

порожденные графами лишь с одним ребром (ij) единичного веса, так

что f(s)=2..,.c(ij)w (s). 11■ j ) i j

Проблема была сразу же решена, как только было осознано, что подпространство, натянутое на w , где лежит конус R2(v), вырезается во всем пространстве функций множеств альтернирующими равенствами

Srss(-i)lrlf(r)=0 для |s|?3. ' (6)

Частный случай этих равенств для |s|=3 был найден Каннингхэмом

(1983). Выполнение равенств (6) обусловлено тем, что функции иг являются линейными комбинациями альтернирующих (0,1)-функций д^ для л= {!}, и [iJ] из раздела 2.2., т.е. (х)=2я^ (х)--д((х)-д (х).

Разрезный конус К (у) есть частный случай конуса разрезных функций, порожденных разрезами в однородно; ш-гиперграфе. Крайний луч п этого конуса порождается гиперграфо1 только с одним ребром А мощности |А| = т. Для /{К (V) равенств; (6) справедливы при | >т, если т четно, и при если >

нечетно. Кроме того £еЯ (V) симметричны, т.е. /(х)=/(у-х). Пуст]

VI

Я(у) есть пространство симметричных функций множеств, и пуст) £> (V) есть подпространство в V), определенное равенствами (6 при |5|>т, если т четно, и при если т нечетно.

Случаи четных и нечетных т существенно различны, чт( обусловлено следующим фактом.

Теорема 2.3.1. Функции VI^ для всех четных А£ V линейн независимы и образуют базис пространства Б СУ).

В лемме 2.3.2 доказано, что функции кА для всех множеств . мощности 2к образуют базис пространства £>2к(у). Так как иг линейно независимы, то конус симплициален и его фасет;

легко определяются.

Теорема 2.3.4. Конус К (У) для четных т порождает пространств

т

Ю^СУ) . Фасеты конуса Я(V) описываются неравенствами

2Г£4 (-1) 111 /СШО для всех А таких, что |А|=т. (7)

Чтобы убедиться, что £ не принадлежит конусу К (у) . достаточн указать множества 5 в (6) и А в (7), для которых нарушаютс равенство в (6) и неравенство (7). Для фиксированного ш эт проверка (для данных я и л) требует вычисления полиномиальног числа значений функции £. Поэтому задача определени принадлежности £ конусу К (у) лежит в соЫР. Иными словами, дл

т

га=2к=сопБЪ Теорема 2.3.4. дает со№ описание конуса 7? (V), есл основной параметр есть мощность V.

Отметим, что неравенства (7) для являются чисто

субмодулярными неравенствами £(1)+£{^)-£{1^)>0 для Таки

образом, если субмодулярная функция лежит в пространстве о (V), то она есть разрезная функция.

Следствие 2.3.5. Конус (V) графических разрезных функций есть пересечение пространства В (V) с конусом С (V) всех

С 5 у

субмодулярных функция, определенных на булевой алгебре 2 . Пространство 02 (V) определяется уравнениями

<и>чв ^ <и>св цв.лв

где Ь=|В| , Ь=л-Ь=| В| . Фасеты конуса К^СУ) определяются неравенствами £(±)+Т(¿)-£(1 для всех пар (ij]■

В случае нечетных л? проблема определения фасет Я (у) становится практически неразрешимой. В качестве примера в конце раздела 2.3 рассмотрен конус Я3(и).

Предложение 2.3.6. К (у)яЦ (у) .

С помощью техники поднятия граней можно найти некоторые классы граней К^Су). Это проделано в [8].

Глава_1II. В этой главе доказывается полиэдральность конуса гиперметрик, исходно определяемого бесконечным числом гиперметрических неравенств, обобщающих неравенства треугольника. Доказательство основано на явном доказательстве конечности числа ¿-типов ¿-многогранников, введенных Вороным. В разделе 3.2 дано конкретное описание ¿-многогранников, соответствующих фасетам, на основе чего получена оценка на максимальные коэффициенты гиперметрических неравенств, определяющих фасеты. В разделе 3.3 доказана экстремальность некоторых ¿-многогранников.

Конус гиперметрик является аппроксимацией конуса хэмминговых метрик. Значение хэмминговой метрики на паре точек равно

^^')=20а(я)»г. . (5), где а(з)>о и к, Лб) есть элементарная разрезная функция множеств, определенная в главе 2. Но теперь множество величин иг. Лб) рассматривается как 2" функций с? (1 ^)

( »/ о

пар параметризованные множествами я. (Для дальнейлего

удобно считать, что У=[о,1, . . .,п]). Поэтому хэмминговые метрики заполняют в м-мерном пространстве (ы=п(п+1)/2) функций /:V2—»к

конус Cut(v)=Cut j, крайними лучами которого являются функции ds(ij).

Хэмминговые метрики иногда называются разрезными метриками. Значение разрезной метрики dg(ij) равно 1, если (ij) есть ребро разреза r{s), и равно о в противном случае. Конус разрезных метрик имеет важное значение для приложений. Это обусловлено в частности тем, что существует взаимно однозначное соответствие между ним и конусом квадратичных псевдобулевых функций.

Конус Сиt(v) разрезных метрик задается своими крайними лучами. Для приложений необходимо знать его фасеты. Большой класс фасет Cut(v) определяется следующими гиперметрическими неравенствами

h(z)d=Zl¿HVzlz}d(i,j)i!o, T,iíVz=l, z(€Z, UV. (8)

Эти неравенства называются гиперметрическими потому, что они обобщают метрические неравенства треугольника, которые есть неравенства (8) с z таким, что z{=-l, z¡=z-k~1 и zj=0 Для

Линейные относиительно d неравенства (8) определяют в пространстве ir" конус fíypn, который называется гиперметрическим. Очевидно включение tfyp^eMet^. Всякая метрика, лежащая в Нурп, называется гиперметрикой.

Гиперметрические неравенства (8) впервые были определены (не не названы так) М.Дэза в 1960 г. Дж.Келли (1970) независимо е 70-х годах переоткрыл их и ввел термин "гиперметрика".

Разрезный конус Cut^ лежит в Яурп. Более того, так кап крайние лучи dg разрезного конуса Cutn есть крайние лучи метрического конуса Metn, то они являются и крайними лучами гиперметрического конуса Нурп •

Одно время предполагалось, что каждая фасета Cutn

определяется некоторым гиперметрическим неравенством, т.е. чте

Cut =Нур . И, действительно, это равенство справедливо для п^6. п п

Для л=7 была обнаружена гиперметрика, не лежащая в Cut , v метрика, не лежащая в Нур? . Таким образом включения Cut^c Нурпс Me t^ для л>7 строгие.

Подчеркнем, что изначально конус Нурп определяете?

бесконечным числом неравенств (8).

В последнее десятилетие гиперметрический конус Нур( I') привлек особое внимание благодаря его связи с геометрией чисел, открытой Ассуадом (1985). Эта связь обусловлена тем, что %(Нур )сРп, где ?п есть конус положительно полуопределенных квадратичных форм, а %-.с!—а есть следующее линейное обратимое преобразование пространства

а1{=сИо,1), ККп, а 1 )+с/( О,ЬсК 1 ,,;)), Н1<Мп (9)

Гиперметрические неравенства для новых переменных принимают вид

21а, , г.а.ЛО, глг. (10)

Кг^^Кп I 3 13 { И {

Отметим, что здесь на г не налагаются никакие ограничения, кроме целочисленности. Так как из этих неравенств следует положительная

полуопределенность формы Еа х.х , то матрица (а ) есть матрица

ъ / \

Грама для п векторов а(ек , где к - ранг матрицы

Положив а0=о, а(^=а{а^, и используя (9), получаем

1 > а. -а )2 , О^К^п, (11)

т.е. гиперметрическое пространство СV,с?) представимо точками в к так, что <1(1^) есть квадрат эвклидового расстояния между этими точками. Для дискретного множества Хсшь через (х,6 ) обозначается метрическое пространство с расстоянием б (х,у)= (х-у)2 равным квадрату эвклидова расстояния между точками х,у(Х. Подстановка а =а а в (10) дает неравенство

(2>,а. )2-2>,аЬо, 2,(2. (12)

111 /11 (

Ассуад (1985) доказал, что неравенства (12) влекут два важных факта. Во-первых, существует вектор такой, что 2са.=а2 для

всех 1, так что (12) эквивалентно неравенству

(аЫ-с)2^с2, (13)

где Во-вторых, неравенство (13) влечет, что вектора

а. порождают в кк дискретную решетку ь(с1).

Странно, что Ассуад не сделал последнего шага и не доказал полиэдральность конуса Нур(У). Может быть, это обусловлено тем, что неравенства (13), являющиеся преобразованиями

гиперметрических неравенств (8), связаны с ними не очень наглядно. Если взять начало координат в центре с сферы (13) и положить cpd(i)=v{=at-c i€v, r2=c2, v( zbS^z, v< , lliYz=l, тс

получим d(i,j)=(v -v ) и ^ j

v(z)z>r2, Z(ZV, (14)

где v(z) есть точка аффинной решетки La(d), аффинно порожденной векторами v , V.

Пусть v(La(d) есть произвольная точка решетки la(d)■ Тогда i представима в виде суммы v(z)=S(iVz{(pd(i), которую назове!* реализацией v относительно V. Если размерность к решетки ¿о(с0 меньше n=|V|-l, т.е. {(pd(i):i£Vj есть лишь порождающее множество, но не аффинный базис £a(d)> то v имеет бесконечно многс реализаций viz) относительно v.

Предложение 3.1.1. Существует взаимно однозначное

соответствие между гиперметрическими неравенствами (8) и

неравенствами (14), соответствующими реализациям точек решетки

L (d) относительно V. a

Неравенство (14) означает, что внутри сферы sd радиуса г нет ни одной точки решетки La(d), т.е. Sd есть пустая сфера. Выпуклая оболочка всех точек решетки, лежащих на пустой сфере, называется L-многогранником. Пусть Ресть L-многогранник, вписанный в S1.

Исторически, L-многогранники и соответствующие L-разбиения пространства были введены Г.Ф.Вороным в начале нашего столетия. Затем они интенсивно изучались главным образом русской школой, i особенности Б.Н.Делоне, С.С.Рышковым и Е.П.Барановским, а также Р.М.Эрдалом из Канады. Б.Н.Делоне (1937) осознал важность понятия пустой сферы для задач покрытия.

Подмножество vcv(p) есть порождающее подмножество веришь некоторого многогранника Р, если V аффинно порождает решетку L (р), имеющую р в качестве своего l-многогранника.

Теорема 3.1.2. (Ассуад, 1985) Метрическое пространство (V,d, гиперметрично тогда и только тогда, когда существуе'. изометрическое отображение ф^ его в пространство (V(P),Ь2) дл>

некоторого Ь-многогранника р, и образ V есть порождающее множество

Простейший пример доставляют метрики с] (lJ), являющиеся крайними лучами Нур Легко проверить, что матрица тсс?3 имеет ранг 1. Поэтому решетка ь{ё) одномерна и имеет в качестве

¿-многогранника отрезок длины 1. Векторы V с точностью до знака

1 1

таковы: для для ¿/Б. Отображение <рй отображает

в одну вершину отрезка, а ЦУ-Б в другую его вершину.

В разделе 3.1.3. рассматриваются некоторые свойства ¿-многогранников и доказывается конечность числа арифметических типов ¿-многогранников данной размерности. Утверждения этого раздела не новы, но они дают явное доказательство результатов Вороного.

Предложение 3.1.3. Пусть Р есть к-мерный Ь-многогранник и У(Р) есть множество его вершин. Тогда число \У(Р)\ его вершин лежит в гранцах |У(Р) | .

Обе оценки Предложения 3.1.3 достижимы: к+1 вершину имеет ¿-мерный симплекс, а 2к вершин имеет ¿-мерный ящик, являющийся прямым произведением к ортогональных отрезков. При ;г=1 оба эти многогранника совпадают.

Два этих ¿-многогранника являются представителями 2х классов ¿-многогранников: асимметричных и симметричных. Так как ¿-многогранник вписан в сферу, то каждая его вершина имеет антипод - противоположную точку на этой сфере. Многогранник назывется симметричным (асимметричным), если антипод всякой его вершины есть вершина (не есть вершина, соответственно).

Предложение 3.1.5. (Делоне, 1937) Пусть Р есть к-мерный р-вершинный Ь-многогранник решетки Ь, и пусть уо1Р есть его объем. Тогда

йеЬЬ 2к_ЧеЬЬ

к] ^ ерр -

где £р=1, если Р симметричен, и £если Р асимметричен.

Как и в Предложении 3.1.3, нижняя оценка объема достигается на ¿-симплексе, а верхняя на ¿-мерном ящике Р , для которого

р=2к, 8р— 1 и уо1ря=с!е^.

Пусть Множество всех ¿-многогранников решетки ¿,

имеющих V в качестве вершины, называется звездой (¿-многогранников). Центры всех ¿-многогранников звезды в точке уЦ являются вершинами многогранника Вороного, состоящего из всех точек пространства, более близких к V, чем к другим точкам решетки ¿. Наибольший из радиусов сфер, описанных вокруг ¿-многогранников звезды, есть радиус решетчатого покрытия пространства шарами.

Из Предложения 3.1.5 вытекает

Следствиие 3.1.6. Число ¿-многогранников в ¿-звезде, равное числу вершин многогранника Вороного, не больше чем ^к! .

Арифметический класс (или тип) ¿-многогранника Р определяется классом унимодулярно эквивалентных целочисленных матриц, строками которых являются координаты вершин Р в некотором базисе решетки, его содержащей.

Теорема 3.1.7. Число арифметических классов к-мерных Ь-многогранников конечно.

Конечность числа арифметических типов ¿-многогранников неявно следует из доказанной Г.Вороным конечности числа ь-типов решеток, ¿-тип ¿-мерной решетки ¿ определяется аффинным типом ¿-разбиения пространства на ¿-многогранники решетки ¿.

¿-разбиение двойственно к хорошо известному разбиению на многогранники Вороного. Решетки и соответствующие им положительные формы имеют один ¿-тип, если определяемые ими ¿-разбиения аффинно эквивалентны.

Вороной показал, что действие группы G¿(n,z) индуцирует разбиение конуса положительно определенных форм Рп на непересекающиеся открытые выпуклые многогранные конусы, названные им областями 1-типов. Они имеют размерность 1,2,...,ЛГ.

Вороной доказал, что число различных, с точностью до арифметической эквивалентности, решеток данной размерности конечно. Поэтому число ¿-типов конечно, и данному ¿-типу соответствует бесконечно много областей. Конечность числа ¿-типов

немедленно вытекает из Предложения 3.1.5 и следствия 3.1.6.

Основная теорема раздела 3.1, т.е.

Теорема 3.1.10. Гиперметрический конус Нурп+1 полиэдрален. вытекает из многогранности областей L-типов и следующих двух лемм

Лемма 3.1.8. Если конус 7t(Hypn+J) пересекается с некоторой областью L-типа, то он содержит эту область целиком.

Лемма 3.1.9. Конус %(Hyp ,) содержит конечное число

п + I

областей фиксированного L-типа.

В следующем разделе, без использования L-разбиений, еще раз доказывается эта теорема.

В разделе 3.2 показывается, что существует более тесная связь между ¿-многогранниками и гиперметриками, а именно, каждая грань конуса Яур(v) определяется некоторым аффинным типом ¿-многогранников.

Пусть (v,d) есть гиперметрическое пространство, ba(d) и Pd -соответствующие решетка и ¿-многогранник. Для каждой реализации v(z) вершины к v(Pd) неравенство (14) выполняется как равенство. Поэтому Предложение 3.1.1 имеет следующее уточнение.

Предложение 3.2.1. Существует взаимно однозначное соответствие между гиперметрическими равенствами, которым удовлетворяет гиперметрика d, и реализациями относительно V вершин L-многогранника Р.

Итак h(z)d=o тогда и только тогда, когда v{z) есть реализация вершины Pd. Пусть

S(v,d) = [h(z)x=0-. h(z)d=0, X6RW]

есть система равенств, которые удовлетворяет d. Она определяет подпространство 5d={xeiRff:x удовлетворяет всем равенствам S(v,d)]. Пересечение F(V,d)=Hyp(v)ftQd называется гранью конуса Hyp(v). В разделе 3.2.1 доказывается, что число этих граней конечно.

Следующее Предложение утверждает, что ¿-многогранники ассоциировании с гранями гиперметрического конуса.

Предложение 3.2.2. Пусть ,d2(HypCV) , P(=Pd и (f(:b№J

отображение, опреляемое d{ , i=1,2. Следующие утверждения

равносильны:

(i) S(V,dt)=S(V,d2) ,

(ii) F(V,d()=F(V,dz),

(iii) существует аффинная биекция T между Р^ и Ртакая, что Тф( Ш=ф2 Ш, iiV.

Поскольку каждый, аффинный тип есть объединение арифметических типов, то из конечности числа последних вытекает конечность числа граней, и, следовательно,

Теорема 3.2.3. Конус Hyp(V) полиэдрален.

В разделе 3.2.3 изучается ранг гиперметрического пространства (v,d), равный размерности грани F(v,d).

Рангом rk{p) L-многогранника Р называется ранг гиперметрического пространства (v(p),6 ). L-многогранник ранга 1 называется экстремальным.

Следующая теорема показывает, что ранг гиперметрического

пространства есть инвариант ассоциированного L-многогранника,

т.е. rk(v,d)=rk(p ).

а

Теорема 3.2.6. Пусть V есть порождающее подмножество в V(P) для L-многогранника Р. Тогда rk(V, d)=rk(V(Pd),62).

L-многогранник Р называется базисным, если множество его вершин содержит аффинный базис в решетки, порожденной Р.

Предложение 3.2.7. Пусть Р есть базисный к-мерный L-многогранник с р вершинами. Тогда

Если Р симметричен, то нижнюю границу можно увеличить.

Предложение 3.2.8. Пусть Р есть симметричный базисный к-мерный L-многогранник. Тогда

гкР>[^2*)-Р/2+1-

В разделе 3.2.2 рассматриваются L-многогранники, соответствующие фасетам Яур(v).

Если гиперметрика d^Hypi v) на множестве V является внутренней точкой Hyp(v), то ни одно гиперметрическое неравенстве не выполняется как равенство, в частности, d(i,j)>0 для все^ itjiV. Поэтому справедливо

Предложение 3.2.9. Если diHypn+1 есть внутренняя точка, то Р ее ' n-мерный симплекс.

С С.Рышков и Е.П.Барановский (1976) называют телом ,череделчвания следующий L-многогранник Рр изучавшиийся еще Г.Вороным.

Пусть k=n-{p+q), и 2г есть симплекс размерности г (и имеющий г+1 вершин). Если к=О, то многогранник + ^ есть выпуклая оболочка вершин двух симплексов 2р и расположенных так, что пространства, натянутые на них, пересекаются в одной точке. Поэтому размерность равна p+q. Если к?О, то р™ q есть

Jc-кратная пирамида над ^ + к-кратная пирамида над

многогранником Р есть пирамида над (й-l)-кратной пирамидой над Р. Пирамида над р есть выпуклая оболочка вершин Р и некоторой точки, не лежащей в пространстве, натянутом на Р. Поэтому р£ q имеет п+2 вершин и размерность п.

Теорема 3.2.10. Пусть гиперметрика d принадлежит фасете Hyp 1, определяемой равенством

и пусть V+ = ( i(. V: z( >0) , У_ = {i£ V: z{ <0) и VQ=(içV:z{= 0) . Тогда L-многогранник Pd базисный и Pd=Pn ■ гДе P=lI . 4=1 v_ I и

Mv0\.

Класс целочисленных матриц, соответствующих арифметическому типу l-многогранника Р , ассоциированного с фасетой h(z)d=o, содержит матрицу (l,z)T, где I есть единичная | v\ » | v| матрица.

Пример. Неравенству треугольника соответствует двумерный L-многогранник P^ (, являющийся прямоугольником, диагонали которого есть одномерные симплексы.

Теорема 3.2.11 дает верхнюю границу на наибольшие коэффициенты гиперметрических неравенств, определяющих фасетй. Пусть

zn =maxA. . {I z, I : zçzn + ' , s'z,=l и неравенство mai i 1 { 1 0 I r

j)<0 определяет фасету Яурп+().

Теорема 3.2.11. Дляп>4, zn <2n~1n!/(п+2).

mai

Как следствие этой теоремы, получаем, что Яур имеет не

более, чем (z )'Ч2(П ' (л!/п+2)п фасет. Это снова пока:?ьм>от,

max

что. гиперметрический конус полиэдрален.

Неравенство h(z)x$0 называется к-гональным, если 2{ |z.|=к. Так как z. целые и S z{=l, то 2 | z{|=1 (mod 2), т.е. i может быть только нечетным числом.

Второе следствие Теоремы 3.2.11 состоит в том, что задача определения гиперметричности произвольной метрики лежит в классе coNP. К сожалению не известно, является ли эта задача NP-трудной. Известно, что следующая задача NP-трудна: для данной метрики определить, является ли она гиперметрикой, и если нет, то найти наименьшее к, для которого нарушается Jc-гональное неравенство [18] .

Так как гиперметрический конус Яурп совпадает с разрезным конусом Сиtn для л^б, а фасеты конуса Сиt известны для 7, то известны и фасеты конуса Нурп Для п^б. Нур2 есть луч, а Нур3 есть трехмерный симплициальный конус, фасеты которого определяются равенствами треугольника. Аналогично, все фасеты Hyp тригональны. Конус Нур5 имеет только тригональные и 5-гональные фасеты. Конус Hypg кроме 3-гональных и 5-гональных фасет имеет 7-гональные фасеты, определяемые (с точностью до перестановки индексов) двумя такими z и z', что z =2, z{=l, ic(2,3), z{=-l, ic(4,5,6} и z'=1, icf1,2,3,4], z'=-2, z'=-1.

t DO

Любопытно, что фасеты конуса Cut6=Hyp6 были установлены относительно, недавно, в 1989г.(Авис), хотя в действительности они были известны еще в 1971г. Е.П.Барановский (1971) нашел полнук систему неравенств, которым должны строго удовлетворять квадрать: длин сторон л-мерного симплекса 2, для того, чтобы 2 бьи:

L-симплексом, порождающим решетку, в которой он лежит.

Заметим здесь, что фасеты Нурп , согласно Лемме 3.1.9, являются фасетами некоторых областей L-типов. Эти фасеть определяются неравенствами (10) для некоторых наборов целых z , l^i^n. Неравенства (10) линейны относительно коэффициентов а

1J

квадратичных форм. Б.Н.Делоне (1971) очень красочно описывает,

как был возбужден Г.Вороной, когда он нашел, что уравнения поверхностей, разделяющих области ¿-ипов, линейны по параметрам а , т.е. эти поверхности являются гиперплоскостями, а сами области ¿-типов - многогранными конусами.

В разделе 3.3 рассматриваются экстремальные ¿-многогранники, т.е. ¿-многогранники ранга 1, ассоциированные с крайними лучами гиперметрического конуса. Более того, если ф:V— л) есть такое отображение, что ф(у)еу(р) есть порождающее множество, то, согласно Лемме 3.2.5 и Теореме 3.2.6, с(=б2ф есть гиперметрика, лежащая на крайнем луче конуса Нур(у).

Согласно Предложению 3.2.2, если б и d' лежат на одном и том же крайнем луче Нур(у), то d'=Гd для некоторой аффинной биекции т. Но у экстремального ¿-многогранника расстояния между вершинами определены однозначно, с точностью до множителя, т.е. d'=td для <;>0. Поэтому единственное допустимое аффинное преобразование

экстремального ¿-многогранника есть гомотетия т, растягивющая р

1/2

в ь раз.

Отметим аналогию с крайними лучами конуса С0(у) монотонных субмодулярных функций на 2У. Каждый крайний луч определяется некоторой связной решеткой ¿е£ вместе с экстремальной feC0(¿) и сюръективным у-морфизмом о:27--»¿. Простейшая решетка 2 определяет .экстремальные субмодулярные (0,1)-функции.

Простейшим экстремальным ¿-многогранником является отрезок, одномерный ¿-многогранник одномерной решетки. Этот ¿-многогранник определяет разрезные крайние лучи ds (см. конец раздела 3.1.2).

Экстремальные ¿-многограннки примечательны в частности своей связью с совершенными решетками. Понятие совершенной решетки ввел Г.Вороной, показав, что решетки, дающие максимальные плотности упаковки шаров, совершенны.

Совершенные решетки определяются совершенными формами. Пусть т есть минимальное значение формы <(<^<па1}х{х} на Целых и гт = [ г<Е2п есть множество представлений минимальных

векторов решетки ¿(г), соответствующей форме Число т есть минимальная норма ¿Ш. Форма / называется совершенной, если

система уравнений

a.,z,z,=m, zíZ (15)

l^i^j^n ij i j m

однозначно определяет коэффициенты а , т.е. ее ранг относительно

N=n(n+l)/2 переменных а еIR , равен N. Напомню, что

* j

коэффициенты совершенных форм есть вершины многогранника Рышкова,

определяемого системой неравенств a,,z,z,}m, гежп.

I^IU^n ¡J i J ,

Так как a{J=a{a^ есть матрица Грама векторов а{ек ,

то уравнения (15) принимают вид

(2%.г;)2=т, . (16)

Iii т

Это. значит, что 2a{z{ есть минимальный вектор решетки l(f).

Выпуклая оболочка концевых вершин минимальных векторов решетки l

называется контактным многогранником L. Контактный многогранник

совершенной решетки назовем совершенным.

Экстремальная гиперметрика определяется системой равенств,

аналогичной (16). Всякая гиперметрика dii,j) на множестве V имеет

вид d(i, j)=(v.-v, )г, где удк3®, СККл, есть вершины некоторого i j i

¿-мерного L-многогранника Р решетки Lid). Вектор

решетки Lid) удовлетворяет неравенству (14). Для вершин Р

неравенства (14) выполняются как равенства.

Пусть Р - базисный и v=Bf={vQ,v(,...,v } есть аффинный базис Р, а значит и решетки Lid), т.е. к=п. Тогда равенство в (14) принимает вид

^z,(bp,p), (17)

где Zf(ñ ,р) есть множество z-координат вершин Р в базисе вр. Так как v{ связаны с dii,j) соотношением dii,j)=2(r2-v(Vj), то равенства (17) эквивалентны однородным равенствам

V«<^nd(i-J')zizj=°' (18)

Гиперметрика d называется экстремальной, если равенства (18) определяют N=nir¡+l)/2 переменных d(i,j), ооднозначно с точностью до множителя, т.е. если ранг системы (18) равен W-1. В этом случае L-многогранник р экстремален.

Используем аналогию равенств (15), (16) и (18), (19). Пусть я есть л-мерное пространство, натянутое на Р, а значит и на решетку L(d), которую переобозначим через l(p). Рассмотрим точку

№£КП+', квадрат эвклидового расстояния которой от всех вершин г равен т. Если ш>г2, то ш лежит вне пространства Я и порождает вместе с ь(р) (л+1)-мерную решетку ¿.

Теорема 3.3.1. Пусть Р есть базисным экстремальный 1-многогранник, порождающий решетку Ь(Р) с минимальной нормой т и

аффинным базисом В ={ V :У(Р). Пусть существуют вершины

2 3 2

(У(Р) многогранника Р такие, что (у-у') -т. Если п&-г , то

решетка Ь, порожденная тн и Р, совершенна.

Экстремальный ¿-многогранник Теоремы 3.3.1 есть сечение совершенного контактного многогранника. Заметим, что любое сечение контактного многогранника есть ¿-многогранник некоторой решетки. К сожалению утверждение Теоремы 3.3.1 нельзя обратить, так как не каждая совершенная решетка порождается своими минимальными векторами. Поэтому сечение совершенного контактного многогранника, дающее экстремальный ¿-многогранник, существует не всегда. Тем не менее многие симметричные экстремальные ¿-многогранники могут быть получены как сечение совершенных контактных многогранников.

В Лемме 3.3.1 описываются условия, когда асимметричный экстремальный ¿-многогранник может быть получен как сечение симметричного экстремального ¿-многогранника. Эта лемма формулируется для многогранников произвольного ранга. Она используется для доказательства экстремальности некоторых симметричных ¿-мерных ¿-многогранников, имеющих асимметричные экстремальные (¿-1)-мерные подмногогранники.

Для того, чтобы быть экстремальным, ¿-многогранник Р должен иметь достаточно много вершин. Используя нижние оценки для гкР из Предложений 3.2.7 и 3.2.8, получаем при гкР=1 следующие нижние оценки на число вершин экстремальных ¿-многогранников.

Предложение 3.3.2. Пусть Р есть базисный экстремальный Ь-многогранник с р вершинамии. Тогда

к(к+3)/2, если Р асимметричен, \ к(к+1), если Р симметричен.'

Для доказательства экстремальности ¿-мерного ¿-многогранника

Р использовалась следующая процедура.

1) Найти к+1 вершин, образующих аффинный базис всу(р), в котором каждая вершина имеет целочисленную реализацию,

2) Вычислить эти реализации zviZt (в,Р), у£У(р),

3) Показать, что ранг системы бСв.р) максимально возможен, т.е. равен к(к+1)/2-1.

Некоторые экстремальные ¿-многогранники строились как сечения выпуклой оболочки минимальных векторов решетки. С помощью этой конструкции, исходя из корневой решетки Еа, построена пара

О

экстремальных ¿.-многогранников: симметричный ¿-многогранник корневой решетки Е? и асимметричный ¿-многогранник корневой решетки Е^ . Аналогично, исходя из решетки Лича, построены

о

симметричный и асимметричный ¿-многогранники размерностей 23 и 22, соответственно. Экстремальность корневых ¿-многогранников доказывается явным выписыванием системы Б(.В,(]) полного ранга. Для подрешеток Лича ранг системы 8(в,с1) вычислялся с помощью ЭВМ. Аналогично, с помощью ЭВМ ЕС-1055, доказывалась экстремальность 4-х ¿-многогранников, связанных с 16-мерной решеткой Варнеа-Уолла.

Глава_1У. Компьютерное исследование играет важную роль в комбинаторике, особенно при классификации комбинаторных объектов. Очень часто комбинаторные объекты группируются в серии (или типы), задаваемые некоторым параметром. Но если распознавание этих объектов ЫР-трудно, то при достаточно больших значениях параметра кроме сериальных появляются спорадические объекты, а также объекты, начинающие новые серии.

Компьютерное исследование позволяет перечислить все серии при данном значении параметра. В этой главе диссертации описанс такое компьютерное перечисление всех типов фасет конуса сиъ? разрезных метрик на 7 точках и всех типов крайних лучей конусг МеЪ метрик на 7 точках.

Алгоритмически задачи нахождения крайних лучей и фасет идентичны. Для вычислений использовался алгоритм двойногс

описания Т.Моцкина и др. (1953г.). Достоинство этого алгоритма состоит в том, что он не требует деления, так что все операции производятся в рамках целочисленной арифметики. Этим снимается проблема точности (но зато повышаются требования к памяти).

Конусы Cut и Me¿n имеют размерность N=n(n-l)/2. Группой симметрии этих конусов является группа, индуцированная симметрической группой S . Элемент oes индуцирует преобразование

^ ^ W

о:х(i,j) —х(о(i),0(j)) пространства r , являющееся симметрией

Cut и Met . п п

Под действием этой группы множество всех крайних лучей и фасет распадается на орбиты перестановочно эквивалентных лучей и фасет. Но кроме этой симметрии множества крайних лучей и фасет разрезного и метрического конусов обладают "скрытой" симметрией, которая наследуется ими от симметрий разрезного СРп и метрического МРп многогранников.

Разрезный многогранник СРп=СР(v)cCut(v) есть выпуклая оболочка разрезных метрик c¡s, Ss v, лежащих на крайних лучах Cut(v) и определенных в начале главы 3. При этом множество 5=0, которому отвечает вершина d^-O конуса Cut(v), не исключается.

Метрический многогранник MPn=MP(.v)cMet(v) отсекается от конуса Met(v) гиперплоскостями, соответствующими неравенствам ■ d(i,j)+d(i,k)+d(j2 для всех неупорядоченных троек Другие фасеты

многогранника МРп задаются неравенствами треугольника, являющимися фасетами и метрического конуса Met ,

Л* .d=d(i J)~d(i ,k)-díj ,к)ф, П (19)

t J

для всех упорядоченных троек (ijk)sv.

Очевидно, каждая фасета Cutn порождает фасету срп, и каждый крайний луч Metn порождает вершину МРп. Обратное, конечно, не верно.

Оба многогранника СРп и МРп имеют одну и ту же группу симметрий, состоящую из преобразований ir™, порожденных перестановками из s^ и так называемыми "переключениями". Эта группа есть факторизация по центру группы симметрий п-мерного

куба.

Пусть Sc V, |V|=n, xeiRm, m=n(n-l)/2, л=(x(i,j), Определим отображения и rg пространства Rm в себя следующим образом

Линейное В5 и аффинное rg преобразования называются переключениями относительно S. Отображения rs , S£V, образуют подгруппу переключений группы симметрий многогранников CP(v) и MP(v). При этом гзгт=гздт> гДе SA т есть симметрическая разность множеств S и Т, а для 0€S имеем ог„=г ,а.

ft Ь О ( О J

Если d есть вершина М?п, то rg d тоже есть вершина МРп. Не если d есть вершина МРп, лежащая на крайнем луче Me tn, то rgd не всегда лежит на крайнем луче. Но все-таки случается, что rg переводит вершину с одного крайнего луча на другой. Поэтому переключения объединяют орбиты перестановочно эквивалентных крайних лучей в более1 крупные классы перестановочно v переключательно эквивалентных крайних лучей. Так, например, Met? имеет 41 орбиту перестановочно эквивалентных крайних лучей, которые переключениями объединяются в 13 классов.

Аналогично, орбиты перестановочно эквивалентных фасет разрезного многогранника CP объединяются в классы перестановочнс

п

и переключательно эквивалентных фасет. Переключательная эквивалентность фасет определяется с помощью преобразования .

Отмечу некоторое различие между СРп и МРп . Поскольку каждая вершина dg многогранника СРп лежит на крайнем луче конуса Сиtn v может быть с помощью переключения rs переведена в нулевую вершину dß, являющуюся вершиной Сиtn, любая фасета СРп переключательнс эквивалентна некоторой фасете Cut^. Поэтому знание фасет Cut^ достаточно для определения всех фасет СРП . '

К сожалению, для метрического многогранника не известно, любая ли его вершина переключательно эквивалентна некоторо{ вершине, лежащей на крайнем луче метрического конуса Met .

если I {ij}ПsI=1, если I {ijinsl^i,

Известно только, что это так для

В разделе 4.3 описано вычисление фасет конуса СиЬ?.

Направляющими векторами крайних лучей си<; являются разрезные метрики с1д. Они однозначно определяются множествами .«V с точностью до дополнения У-й.

Авис (1989) первый вычислил все фасеты конуса Ci.it . Он нашел, что все фасеты СиЬ^ гиперметрические, тем самым доказав равенство СиЬ6=Нурб. Алгоритм, с которым работал я, прямо выдал все фасеты СиЬ6 .

Крайние лучи СиЬ? определяются

а) 7-мью одноэлементными множествами (Л, КК7,

б) 21-ой парой [¿Л, и

в) 35-тью тройками Изк], líi<j<^c$7.

Назовем множество л, определяющее метрику б , лежащую на фасете Ьх^О, а также саму с/ , корнем этой фасеты.

В разделе 4.3 перечислено 5 таких семейств корней (А1)-(А9), (Б), (в), (г) и (Д), что для каждого семейства оказалось возможным вычислить (на ЕС-1055) все фасеты, содержащие корни этих семейств. Затем доказано, что с точностью до перестановок и переключений каждая фасета СиЬ? содержит корни одного из этих семейств. Конечно, эти семейства тоже рассматриваются с точностью до перестановок и переключений.

Любая фасета, содержащая в качестве корней корни одного из этих семейств, с точностью до перестановок и переключений, есть одна из и фасет, 6 из которых есть гиперметрические фасеты.

10 фасет были известны до машинных вычислений. 11-ая фасета была обнаружена в результате вычислительного эксперимента.

Теорема 4.1. Фасеты конуса СиЬ, как и фасеты СР^ , с точностью до перестановок и переключений, принадлежат одному из упомянутых выше 11 типов.

Эта теорема вытекает из следующей леммы.

Лемма 4.2. Любая фасета конуса СиЬ^ содержит, с точностью до перестановки и переключения, корни одного из семейств (А1)-(А9), (Б) , (В) , (Г) и (Д) .

В разделе 4.4 описывается вычисление всех типов крайних лучей конусов МеЪ^ и МеЬ?.

Исследованию крайних лучей метрического конуса МеЬ посвящено много работ, см., например, Ломоносов (1978), Карзанов -Певзнер (1979), Авис (1980, 1989), Шлык (1984), Лоран (1991). Компьютерное перечисление крайних лучей МеЬ показало, что большинство типов его крайних лучей не были обнаружены при теоретических исследованиях.

Так как размерность конуса МеЬ6 не очень велика и равна 15, то вычисление всех крайних его лучей оказалось возможным без ухищрений, в лоб. Найденные типы крайних метрик, т.е. метрик, лежащих на крайних лучах, МеЬ были известны давно, но не было известно, исчерпываются ли ими все крайние лучи. Конус имеет 296 крайних лучей, принадлежащих 5 орбитам перестановочно эквивалентных лучей, которые объединяются в 3 класса переключательно эквивалентных метрик.

Как и в случае разрезного конуса СиЬ?, перечисление до конца крайних лучей МеЬ? оказалось возможным только для крайних метрик, лежащих как минимум в пересечении 4х фасет.

Обозначим символом Л^ фасету, определяемую неравенством треугольника (19). Если метрику б описывать полным графом, ребрак (¿л') которого приписаны длины то длиной любой цепи ь,

соединяющей две вершины 1 и з, называется сумма длин ребер этой цепи. Если длина цепи Ь равна длине 1, ^) ребра (¿.у), ее замыкающего, то ь называется геодезической метрики б. Каждой геодезической длины q, проходящей через вершины ,...,

1 , соответствует выполнение как равенств неравенств (15),

определяемых Л,2. , Л,3,, К,4, ,..., Л,4, . Существуют

111з 1114 15 11V)

метрики, например к в которых все геодезические имеют длину 1.

Наибольшее число геодезических имеют метрики, лежащие на крайни?

лучах (крайние метрики).

Подобно семейству (Б) для СиЪ7, здесь существуют пары фасет такие, что крайние лучи, лежащие в этой паре, лежат и еще в одно£

паре.

Лемма 4.3. Ак , +Л] =Л! ,+Ак, , 11 3 к 1} II

и любая метрика, лежащая в пересечении зтих Ах фасет, имеет геодезическую длины не меньше 3.

В качестве первого семейства фасет было взято следующее семейство (А), удовлетворяющее этой лемме.

(А) К]3, Кгы< к3ы, К324.

Назовем метрику с* положительной, если с}(1^)>0 для всех пар {ij). Все 18 типов перестановочно не эквивалентных положительных крайних метрик, имеющих хотя бы одну геодезическую длины не меньше 3, т.е. лежащих в пересечении фасет семейства (А), приведены в Таблице 1.

Выло найдено 643 крайние метрики конуса МеЬ?, содержащиеся в пересечении 4х фасет семейства (А). Конечно, некоторые из этих метрик были не положительны.

Затем рассматривались метрики, все геодезические которых имеют не более 2х ребер.

Лемма 4.4. Если положительная крайняя метрика не имеет геодезических, содержащих более 2х ребер, то эта метрика графическая и принимает только 2 значения, равные с точностью до множителя 1 и 2.

Для вылавливания всех (1,2)-метрик перебирались крайние лучи, лежащие в пересечении 5 фасет следующих семейств:

(Б) А32 У1г ,А% ,К134 ,А234 , (В) А% ,А523 ,А534,А*2 Л134 ,

(Г) ^гЛ523 Л534 Л*3Л:*2.

Машинное перечисление дало 721, 468 и 358 крайних лучей, лежащих в семействах фасет (Б), (В) и (Г), соответственно.

Найденные метрики вместе с графами, порожденными ребрами длины 2, показаны в таблице 2.

Лемма 4.5. Кроме метрик 15 типов, перечисленных в Таблице 2, не существуют другие крайние (1,2)-метрики конуса МеЬ?.

Найденные крайние лучи конуса Меь объединяются в 13 классов переключательно эквивалентных лучей.

Приведенный подсчет крайних лучей конуса МеЪ7 метрик на 7

точках позволил сделать следующие выводы.

Крайние метрики конуса Me t устроены сложнее, чем это предполагалось. Некоторые крайние метрики конуса Metмогут быть подняты из крайних метрик конуса техникой, описанной в

[8]. Крайняя метрика d конуса Met является поднятием,' если существуют такие л-1 точек, что ограничение на эти точки метрики de Me t есть крайняя метрика Afetft_(. Поднятиями являются все двудольные метрики (кроме К2 3) и все неположительные метрики (в том числе и разрезные). Одна и та же метрика может быть поднята из разных метрик, и наоборот, из одной метрики можно получить несколько разных поднятий.

Но большая часть нетривиальных (23 из ЗЗх) крайних метрик конуса Met? не может быть поднята из крайних метрик конуса Afetg . Эти метрики трудно предугадать. И, действительно, все эти крайние метрики были найдены только с помощью ЭВМ.

Полное вычисление крайних метрик конуса Met для л> 7 в настоящее время на ЭВМ типа ЕС-1055 проблематично, -так как лавинообразно увеличивается потребность либо в промежуточной памяти, либо во времени, в зависимости от используемого алгоритма.

Основные положения диссертации опубликованы в следующих работах:

1. Гришухин В.П. Многогранники, связанные со структурами и минимаксные комбинаторные соотношения. // Графы, гиперграфы и дискретные оптимизационные задачи (Материалы VI цикла заседаний Всесоюзного семинара по дискретной математике в г. Одессе), ред. А.А.Зыков, Киев: Знание. - 1977. - С. 14-16.

2. Гришухин В.П. Еще раз о многограннике паросочетаний // "Комбинаторные методы решения потоковых задач". - М.:ВНИИСИ, 1979. - вып. 3. - С.103-113.

3. Grishuhin V. Polyhedra related to a lattice // Math. Progr. - 1981. - V.21, N 1, - P.70-89.

4. Гришухин В.П., Папернов Б.А. Субмодулярные задачи, алгоритмы их решения и смежные вопросы // Препринт ЦЭМИ АН СССР.

- M., 1982. - 66c.

5. Гришухин В.П. Субмодулярные задачи и алгоритмы их решения // Известия АН СССР, Техническая кибернетика. - 1983. - N 1. - С.188-193.

6. Гришухин В.П. Две теоремы о субмодулярных функциях // Алгоритмы дискретной оптимизации и их применение в вычислительных системах. - Ярославль, 1983, - С.102-113.

7. Гришухин В. П. Конусы альтернирующих и разрезных субмодулярных функций // "Кибернетика и вычислительная техника".

- М.: Наука, 1988. - вып.4. - С.217-231.

8. Гришухин В. П. Поднятие граней многогранников // Optimization. - 1986. - V.17, N.4. - Р.487-499.

9. Grishuhin V.P. Cones of alternating and cut submodular functions // Combinatorica. - 1989. - V.9, N1. - P.21-32.

10. Гришухин В.П. Образующие конуса субмодулярных функций // Препринт ЦЭМИ АН СССР. - М.,1982. - 35с.

И. Гришухин В.П. Экстремальность ранговой функции связной полумодулярной решетки // "Задачи дискретной оптимизации и методы их решения". - М.:ЦЭМИ, 1987. - С.218-223.

12. Гришухин В.П. Разрезные субмодулярные функции и их минимизация // "Задачи дискретной оптимизации и методы их решения". - М.:ЦЭМИ, 1987. - С.64-82.

13. Deza M., Grishukhin V.P., Laurent M. Hypermetrics and L-polytopes // Techn. Report IASI CNR. Roma, 1990. - R.286. - 24P.

14. Deza M. , Grishukhin V.P., Laurent M. Hypermetric cone is polyhedral // Combinatorica. - 1993. - V. 13, N 4. - P.397-411.

15. Deza M., Grishukhin V.P., Laurent M. Extreme hypermetrics and L-polytopes, Colloquia Mathematica Societatis Janos Bolyai, V 60, Sets, Graphs and Numbers, Budapest, 1991. -P.157-209.

16. Deza M. , Grishukhin V.P. L-polytopes and equiangular lines // Papport de Recherche du Laboratoire d'Informatique de l'Ecole Normal Supérieure, LIENS-92-26. - Paris, 1992. - 46p.

17. Deza M. , Grishukhin V.P., Laurent M. Hypermetrics in

Geometry of Numbers // Papport de Recherche du Laboratoire d'Informatique de l'Ecole Normal Supérieure. Paris, 1993. -LIENS-93-4. - 100p.

18. Avis D. , Grishukhin V.P. A bound on the k-gonality of facets of the hypermetric cone and related complexity problems // Computational Geometry: Theory and Applications - 1993. - V.2 -P.241-254.

19. Grishukhin V.P. L-polytopes, even unimodular lattices and perfect lattices // Papport de Recherche du Laboratoire d'Informatique de l'Ecole Normal Supérieure. - Paris, 1993. -LIENS-93-1. - 8P.

20. Deza M., Grishukhin V.P., Laurent M. The symmetries of the cut polytope and of some relatives // Applied Geometry and Discrete Mathematics, "Victor Klee Festschrift", DIMACS series in Discr. Math, and Theoret. Comput. Science. 1991. - V.4. P.205-220.

21. Grishukhin V.P. All facets of the cut cone C for n=7

n

are known //Europ. J. Combinatorics. - 1990. - V.ll. - P.115-117.

22. Grishukhin V.P. Computing extreme rays of the metric cone for seven points // Europ. J. Combinatorics. - 1992. - V.13. - P.153-165.