В математике упаковка в гиперграфе - это разбиение множества ребер гиперграфа на некоторое количество непересекающихся подмножеств, так что никакая пара ребер в каждом подмножестве не имеет общих вершин. Есть два известных алгоритма для достижения асимптотически оптимальной упаковки в k -однородные гиперграфы. Один из них - случайный жадный алгоритм, предложенный Джоэлом Спенсером . Он использовал ветвящийся процесс, чтобы формально доказать оптимальную достижимую оценку при некоторых побочных условиях. Другой алгоритм называется полубайтом Рёдля и был предложен Войтехом Рёдлем.и другие. Они показали, что достижимая упаковка полубайтом Рёдля в некотором смысле близка к упаковке случайного жадного алгоритма.
История
Проблема нахождения числа таких подмножеств в k -однородном гиперграфе была первоначально мотивирована гипотезой Пола Эрдёша и Хаима Ханани в 1963 году. Войтех Рёдль доказал их гипотезу асимптотически при определенных условиях в 1985 году. Пиппенгер и Джоэл Спенсер обобщили результаты Рёдля, используя случайный жадный алгоритм в 1989 году.
Определение и терминология
В следующих определениях гиперграф обозначается H = ( V , E ). H называется k -однородным гиперграфом, если каждое ребро в E состоит ровно из k вершин.
является упаковкой гиперграфа, если это подмножество ребер в H такое, что не существует пары различных ребер с общей вершиной.
это (,) -хороший гиперграф, если существует такое, что для всех а также и выполняются оба следующих условия.
где степень deg ( x ) вершины x - это количество ребер, которые содержат x, а кодовая степень codeg ( x , y ) двух различных вершин x и y - это количество ребер, содержащих обе вершины.
Теорема
Существует асимптотическая упаковка P размера не менее для -равномерный гиперграф при следующих двух условиях:
- Все вершины имеют степень в котором стремится к бесконечности.
- На каждую пару вершин приходится только общие края.
где n - общее количество вершин. Этот результат был показан Пиппенгером и позже доказан Джоэлом Спенсером. Для решения проблемы упаковки асимптотических гиперграфов Джоэл Спенсер предложил случайный жадный алгоритм. В этом алгоритме в качестве основы используется процесс ветвления, и было показано, что он почти всегда обеспечивает асимптотически оптимальную упаковку при указанных выше побочных условиях.
Алгоритмы асимптотической упаковки
Есть два известных алгоритма асимптотической упаковки k-однородных гиперграфов: случайный жадный алгоритм через процесс ветвления и полубайт Рёдля.
Случайный жадный алгоритм через процесс ветвления
Каждый край независимо и единообразно назначается отличное реальное «время рождения» . Края берутся по одному в порядке их рождения. Край принято и включено в если он не перекрывает ранее принятые края. Очевидно, что подмножество это упаковка, и можно показать, что ее размер почти наверняка. Чтобы показать это, позвольте остановить процесс добавления новых ребер на время.. Для произвольного, выбирать такой, что для любого -хороший гиперграф где обозначает вероятность вершины выживание (вершина выживает, если она не входит ни в одно ребро в ) до времени . Очевидно, что в такой ситуации ожидаемое количество выжить во времени меньше чем . В результате вероятность выживать меньше чем выше чем . Другими словами, должен включать как минимум вершины, что означает, что .
Для завершения доказательства необходимо показать, что . Для этого асимптотикавыживание моделируется непрерывным процессом ветвления. Исправить и начнем с Евы с датой рождения . Предположим, что время идет назад, поэтому Ева рожает в интервалес распределением Пуассона единичной плотности . Вероятность того, что у Евы рождение . Путем кондиционирования время рождения независимо и равномерно распределены по . Каждое рождение, данное Евой, состоит из все потомки с одинаковым временем рождения говорят . Процесс повторяется для каждого потомства. Можно показать, что для всех существует так что с вероятностью выше, чем , У Евы не больше потомки.
Укоренившееся дерево с понятиями «родитель», «потомок», «корень», «родина» и «матка» должно называться выводным деревом. Учитывая конечное племенное деревомы говорим для каждой вершины, что она выживает или умирает. Бездетная вершина выживает. Вершина умирает тогда и только тогда, когда в ней есть хотя бы один выводок, и все они выживают. Позволять обозначают вероятность того, что Ева выживет в племенном дереве дано вышеуказанным процессом. Цель - показать а затем для любых фиксированных , можно показать, что . Эти два отношения завершают нашу аргументацию.
Показывать , позволять . Для небольшой, как, грубо говоря, Ева, начинающаяся во времени может иметь рождение в промежутке времени все чьи дети выживают, пока Ева не рожает в все чьи дети выживают. Сдача дает дифференциальное уравнение . Начальное значение дает уникальное решение . Обратите внимание, что действительно.
Чтобы доказать , рассмотрим процедуру, которую мы называем историей, которая либо прерывает, либо производит выводок. История содержит набор вершин, первоначально . будет иметь структуру племенного дерева с корень. В либо обрабатываются, либо не обрабатываются, изначально необработан. Для каждого назначается время рождения , мы инициализируем . Историю взять необработанныйи обработайте его следующим образом. Для ценности всех с участием но без который уже был обработан, если какой-либо имеет а также с участием или несколько имеют с участием а также , то история прерывается. В противном случае для каждого с участием добавить все к как соседи с родителями и общая дата рождения . Сейчассчитается обработанным. История останавливается, если не прерывается, когда всеобрабатываются. Если история не прерывается, то root выживает племенное дерево если и только если выживает во времени . Для фиксированного расплода пусть обозначают вероятность того, что в процессе ветвления будет получено расплодное дерево. . Тогда вероятность того, что история не прервется, равна. По конечности ветвящегося процесса, суммирование по всем выводкам и история не прерывается. ВРаспределение его потомства приближается к распределению ветвящегося процесса. Таким образом.
Клев Рёдля
В 1985 году Рёдль доказал гипотезу Пауля Эрдёша методом, названным полубайтом Рёдля. Результат Рёдля можно сформулировать в виде задачи об упаковке или покрытии. Для покрывающее число, обозначенное показывает минимальный размер семьи k-элементных подмножеств которые обладают тем свойством, что каждый набор l-элементов содержится хотя бы в одном . Пол Эрдеш и др. предположение было
- .
где . Эта гипотеза примерно означает, что тактическая конфигурация асимптотически достижима. Аналогичным образом можно определить номер упаковки. как максимальный размер семьи k-элементных подмножеств обладающий тем свойством, что каждый набор l-элементов содержится не более чем в одном .
Упаковка в более прочном состоянии
В 1997 году Нога Алон , Чон Хан Ким и Джоэл Спенсер также предоставили хорошие возможности для при более сильном условии кодовой градации, что каждая отдельная пара имеет не более одного общего края.
Для k -равномерного D -регулярного гиперграфа на n вершинах, если k > 3, существует упаковка P, покрывающая все вершины, но не более. Если k = 3, существует упаковка P, покрывающая все вершины, но не более.
Эта оценка желательна в различных приложениях, например в системе троек Штейнера . Система троек Штейнера - это 3-равномерный простой гиперграф, в котором каждая пара вершин содержится ровно на одном ребре. Поскольку система троек Штейнера, очевидно, является d = ( n -1) / 2-регулярной, приведенная выше оценка обеспечивает следующее асимптотическое улучшение.
Любая система троек Штейнера на n вершинах содержит упаковку, покрывающую все вершины, но не более.
Смотрите также
Рекомендации
- Erdős, P .; Ханани, Х. (1963), "О предельной теореме комбинаторного анализа" (PDF) , Publ. Математика. Дебрецен , 10 : 10–13.
- Спенсер, J. (1995), "Асимптотическая упаковка с помощью ветвящегося процесса", Случайные Структуры и алгоритмы , 7 (2): 167-172, DOI : 10.1002 / rsa.3240070206.
- Алон, Н .; Спенсер, Дж. (2008), Вероятностный метод (3-е изд.), Wiley-Interscience, Нью-Йорк, ISBN 978-0-470-17020-5.
- Рёдль, В .; Thoma, Л. (1996), "Асимптотическая упаковка и случайный жадный алгоритм", Случайные структуры и алгоритмы , 8 (3): 161-177, CiteSeerX 10.1.1.4.1394 , DOI : 10.1002 / (SICI) 1098-2418 ( 199605) 8: 3 <161 :: AID-RSA1> 3.0.CO; 2-W.
- Спенсер, Дж . ; Пиппенгер, Н. (1989), «Асимптотическое поведение хроматики», журнал комбинаторной теории , серия A, 51 (1): 24–42, DOI : 10.1016 / 0097-3165 (89) 90074-5.
- Алон, Н .; Kim, J .; Спенсер, Дж (1997), "Почти идеальное паросочетание в регулярных простых гиперграфах", Израиль Журнал математики , 100 (1): 171-187, CiteSeerX 10.1.1.483.6704 , DOI : 10.1007 / BF02773639.