Гіперграфи
Потрібно знайти кількість гіперграфів з $%n$% пронумерованими вершинами, що відповідають таким умовам: 1. Кожне ребро гіперграфа містить 3 вершини. 2. Будь-які 2 ребра гіперграфа мають максимум одну загальну вершину. 3. Гіперграф пов'язаний і не містить циклів.
заданий11 Лют '15 23:12
Завдання порівняно важке, але дуже цікаве.
Гіперграфи, що розглядаються в задачі, мають таку структуру. Якщо вони мають $%m$% гіперребер (трикутників), то число вершин дорівнює $%n=2m+1$%, тобто воно завжди непарне. Якщо $% m = 0 $ %, то гіперграф складається з однієї точки. При $%m=1$% виходить трикутник. При збільшенні $%m$% на одиницю відбувається додавання одного нового трикутника шляхом приєднання однієї з його вершин до однієї з наявних. Такий трикутник назвемо "висячим" за аналогією з вершинами дерева, що мають ступінь 1.
Відповідь має таку форму: $%1cdot3cdot5cdotldotscdot(2m-1)cdot(2m+1)^$%.
Добуток перших $%m$% непарних чисел, тобто $%1cdot3cdot5cdotldotscdot(2m-1)$%, іноді записують у вигляді $%(2m-1)!!$%; можна помітити, що воно дорівнює $%\frac$%.
Доказ проведемо на кшталт того, як доводиться близька характером класична теорема Келі про кількість розмічених дерев. Зручніше розглядати розмічені кореневі гіперграфи, тобто такі, в яких одна з $%n$% вершин, яка називається коренем, фіксується. Очевидно, що кореневих розмічених дерев рівно в $%n$% разів більше, оскільки фіксувати можна будь-яку з $%n$% вершин. Тому доводитимемо, що кореневих розмічених дерев є $%(2m-1)!!\cdot(2m+1)^m$%.
Корисно намалювати якийсь кореневий гіперграф, взявши для прикладу, скажімо, $%m=6$% і пронумерувавши випадковим чином його вершини числами від 1 до13. Через відсутність можливості зробити малюнок, я опишу свій приклад словами. Ми спочатку беремо точку 9 як корінь і приєднуємо до неї два трикутники з нижніми вершинами 6, 2 та 5, 8 відповідно. Далі до 6 приєднуємо трикутник з 3, 7 (зліва направо), а до 2 трикутник з 1, 12. Тепер додамо до 8 трикутник з 4, 11, а до 7 - трикутник з 13, 10.
Кореневі гіперграфи зручні тим, що у будь-якого трикутника буде одна верхня вершина (найближча до кореня) і дві нижні. Ясно, що є хоча б один "висячий" трикутник, у якого до жодної з нижніх вершин нічого не приєднано.
Зазначимо, що число $%(2m-1)!!$% виникає як відповідь у наступному відомому завданні: скільки способів можна розбити на пари безліч із $%2m$% елементів? Нагадаємо доказ: якщо елементи перенумерувати, ми спочатку $%2m-1$% способом вказуємо парний елемент для елемента з найменшим номером. Далі пару видаляємо, і для елемента з найменшим номером серед тих, що залишилися, вибираємо парний $%2m-3$% способами, і так далі. За правилом твору, всі числа, що розглядаються, перемножаться.
Розглянемо кореневий гіперграф, вершини якого занумеровані натуральними числами, але не обов'язково йдуть поспіль (це потрібно для індукції). Кожному такому гіперграфу можна порівняти йогокод, що складається з двох об'єктів. Перший об'єкт буде послідовністю виду $%(x_1,\ldots,x_m)$%, де кожне з чисел $%x_i$% незалежно один від одного приймає одне з $%2m+1$% значень - номерів вершин. Зрозуміло, що таких послідовностей точно $%(2m+1)^m$%. Другий об'єкт є розбиттям на пари множини $%X\setminus\$%, де $%X$% - безліч номерів вершин, а $%x$% - корінь. Таких розбиття є рівно $%(2m-1)!!$%, тому можливих кодів буде точно$%(2m-1)!!\cdot(2m+1)^m$%. Наша мета буде досягнута, якщо ми покажемо, що між кореневими гіперграфами та їх кодами можна встановити біекцію.
Будуватимемо коди за допомогою індукції за $%m\ge0$%. Якщо $%m=0$%, то ми маємо одну точку $%x$%, що є коренем. Послідовність розглядаємо порожню, але в пари розбивати тут нічого.
Тепер нехай $% m \ ge1 $ %. Зручно почати із завдання розбиття на пари одразу для всього гіперграфа, оскільки воно влаштоване просто. У пари ми поєднуємо нижні вершини трикутників. Зрозуміло, що коренева вершина не входить, а решта входить по одному разу. Для прикладу, розглянутого вище, вийде така безліч пар: $% \ & lt; \,\,\,\,\,\\gt;$%.
Тепер з індукції будуємо послідовність вершин, тобто об'єкт коду. Для початку переглядаємо всі "висячі" трикутники та відповідні їм пари. У прикладі таких пар три. Серед них вибираємо ту, в якій є найменший з їх номерів. У нашому прикладі це число 1 і пара $%\$%. Видаляємо відповідний трикутник і записуємо в послідовність номер $%k$% його верхньої вершини, тобто число 2. Після цього виходить кореневий розмічений гіперграф з $%m-1$% трикутником. Для нього за індукцією визначено послідовність вершин, яку дописуємо праворуч до $%k$%. Неважко помітити, що в кінці першого об'єкта коду (при $%m\ge1$%) буде знаходитись номер кореневої вершини, так як останній трикутник, що видаляється, приєднується знизу саме до неї.
Для прикладу, що розглядається, вийде така послідовність: $% (2,8,9,7,6,9) $%.
Тепер коди визначені і залишилося перевірити найголовніше: властивість біоктивності. Для цього візьмемо будь-яку послідовність $%(x_1,\ldots,x_m)$%, членами якої є елементи множини $%\$%(будь-які повторення допускаються). Покладемо $%x=x_m$%, і довільним чином розіб'ємо на пари елементи множини $%X\setminus\$%. Покажемо, що відповідний код має один і лише один розмічений гіперграф з коренем $%x$%.
Розмірковуватимемо, як і вище, щодо індукції. Зауважимо, що хоч на початку числа у нас йдуть поспіль, надалі це може бути й не так, але ми завжди знаємо набір номерів вершин за "поточним" списком пар. Ми знаємо номер кореневої вершини: вона є крайньою праворуч у послідовності, і вона не присутня в розбиття на пари. Переглянемо всі номери, що входять до пар, і виділимо з них ті, що не входять до послідовності. Виділено буде не більше $%m-1$% числа, тому що $%x_m$% у пари не входить. Це означає, що хоча б одна пара виявиться "чистою": тобто обидва її елементи ми виділили. Серед таких "чистих" пар відзначимо ту, в якій є найменший з номерів, що входять в "чисті" пари. Намалюємо трикутник, у якого зверху написано число $%x_1$%, а знизу - елементи виділеної пари. Тепер видаляємо число $%x_1$% та виділену пару з коду, отримуючи код гіперграфа з $%m-1$% трикутником. За припущенням індукції цей гіперграф однозначно відновлюється. Залишилося до нього намалювати той трикутник, який ми зобразили.
Неважко бачити, що за правилом кодування ми в списку всіх пар, які були на початку, повинні будемо вибрати ту, якій відповідає "висячий" трикутник з присутністю найменшого можливого номера внизу. Це і є той трикутник, про який щойно йшлося. У код ми запишемо число $%x_1$% - його верхню вершину. Тим самим процеси кодування і декодування взаємно зворотні, що доводить біоактивність.
Корисно простежити процес декодування з прикладу, переконавшись у тому, що виходитьвихідний кореневий розмічений гіперграф (з точністю до ізоморфізму).