Ловас
Cтраница 1
Ловас также указал много других следствий из (1.5), которые мы сейчас не приводим. [1]
Недавно Ловас [5] предложил удивительно простое решение чрезвычайно трудной комбинаторной задачи ( нахождение емкости пятиугольника), поставленной Шенноном [8] в 1956 г. В этой работе мы покажем, что идеи Ловаса в сочетании с некоторыми нашими идеями приводят к очень мощному и общему методу решения комбинаторных задач упаковки, который мы изложим на языке теории графов В частности, граница линейного программирования Дельсарта [3] для клик в ассоциативных схемах окажется специальным случаем границы Ловаса. [2]
Граница (4.1) эквивалентна теореме 9 Ловаса. [3]
Следующее обобщение этого следствия, принадлежащее Ловасу ( 1977), будет играть важную роль в дальнейшем. Однако его доказательство существенно более запутанное, в частности, оно использует полилинейную алгебру. [4]
Настоящая статья возникла из попыток перенести результаты Ловаса на более общий случай. Думаем, что нам это удалось, но в нашем решении ортонормированные представления полностью исчезли. Тем не менее все границы, которые мы получили ( по крайней мере границы для 6 ( G)), могут быть получены из ортонормированного представления, поэтому мы и называем их границами Ловаса. В приложении А содержатся доказательства эквивалентности нашего метода и метода Ловаса. [5]
Этот результат является частным случаем теоремы 13 Ловаса. [6]
Мы применим подход ( см. Хетейи ( 1972), Ловас ( 1975Ь)), отличный от всех вышеперечисленных. [7]
Этот результат может быть получен как следствие из следующей теоремы ( Ловас ( 1972е)), которая в сущности является перефразировкой теоремы о совершенных графах. [8]
 |
Граф Петерсена.| Граф икосаэдра.| Граф додекаэдра. [9] |
Этот пример, таким образом, есть частный случай теоремы 12 Ловаса. [10]
Это было показано для полиномов от одной переменной Ленстрой, Ленстрой и Ловасом [48] в 1982 г. Как показывает результат Калтофена [39, 40], это можно обобщить на полином от любого фиксированного числа переменных. [11]
Полиномиально временной алгоритм для минимизации субмодулярной функции множества известен ( см. Гречель, Ловас и Схрейвер ( 1981)) и мы не станем вдаваться в его детали, а ограничимся замечанием, что в нем применяется метод эллипсоидов, абсолютно так же, как при решении указанной выше задачи о паросочетании. [12]
Можно показать ( Хелгасон ( 1974), Мак Диармид ( 1975) и Ловас ( 1977)), что, наоборот, всякий полиматроид может быть представлен с использованием этой конструкции. [13]
Воспользовавшись недавними результатами, Карп и Пападими-триу ( 1980, 1982), Падберг и Рао ( 1981) и Гречель, Ловас и Схрейвер ( 1981) показали, что метод эллипсоидов помогает также преодолеть вторую из упомянутых ранее трудностей и действительно приводит к полиномиальному алгоритму построения паросочетаний, базирующемуся на описании политопа паросочетаний, данном Эдмондсом. [14]
Недавно Ловас [5] предложил удивительно простое решение чрезвычайно трудной комбинаторной задачи ( нахождение емкости пятиугольника), поставленной Шенноном [8] в 1956 г. В этой работе мы покажем, что идеи Ловаса в сочетании с некоторыми нашими идеями приводят к очень мощному и общему методу решения комбинаторных задач упаковки, который мы изложим на языке теории графов В частности, граница линейного программирования Дельсарта [3] для клик в ассоциативных схемах окажется специальным случаем границы Ловаса. [15]
Страницы: 1 2