Екстремальні розклади повних графів: існування, перелік.

РОЗДІЛ 2
ТЕОРЕТИЧНІ ОСНОВИ РОЗВ'ЯЗУВАННЯ ЗАДАЧ,
ЩО РОЗГЛЯДАЮТЬСЯ У ДИСЕРТАЦІЇ
Розклади, що розглядаються у різних розділах дисертації, відрізняються складом множини G допустимих компонентів. Тому розв'язування задач існування та перелік цих розкладів проводяться по-різному. Проте є багато спільних рис у способах проведення досліджень, тому на перший план виходить завдання уніформізації підходів та універсалізації методів роботи з цими та подібними комбінаторними конфігураціями.
Мета цього розділу - викласти принципові засади досліджень , результатам яких присвячена ця дисертація. Розглянути застосовані методи у всій їх загальності необхідно , у першу чергу, для того, щоб уникнути небезпеки "не побачити за деревами лісу", тобто за конкретикою, частковими проявами загального не побачити самого цього загального - принципів.
Серед цих принципів виділено три групи. Перша стосується зручного для досліджень представлення графів - компонент розкладів та упаковок, друга - способів побудови розкладів, а третя - способів розрізнення неізоморфних та ототожнення ізоморфних розкладів.
2.1. Шаблонне представлення графів

Значна доля успіху у розв'язуванні задач, що розглядаються у дисертації, досягнута за рахунок доцільного вибору способу представлення графів у комп'ютері.
Звичайний граф порядку n представляють у вигляді списка його ребер. Щоб це представлення було однозначним, вибирають за множину вершин стандартну множину {1, 2, ..., n}, або {0, 1, ..., n-1}, ребра записують у вигляді ij, де i У перших трьох розділах дисертації застосовується інший спосіб представлення графів (зокрема, дерев) - за допомогою шаблонів. При цьому способі граф G представляється у вигляді пари об'єктів, перший з яких являє собою перестановку a1a2...an стандартної множини вершин, а другий об'єкт - шаблон графа G, тобто список пар номерів ij, i Зафіксуємо шаблон графа G, тоді кожна перестановка його вершин b1b2...bn представляє граф, ізоморфний графові G, причому серед цих представлень є всі графи зі стандартною множиною вершин, ізоморфні G. Якщо граф G має нетотожний автоморфізм, то його шаблонне представлення не єдине. У цьому випадку серед представлень графа G вибирають одне, яке називають стандартним шаблонним представленням.
Для забезпечення однозначності шаблонного запису графа G застосовують умови стандартності, які мають вигляд системи строгих нерівностей та призначені забезпечити певний порядок нумерації вершин у вершинних орбітах графа G.
Наприклад, граф, зображений на рис.2.1, називають драконом[75,76]. Якщо взяти шаблон 12 13 24 34 45, то можна записати відповідну цьому графові перестановку двома способами: 12345 і 13245.
Рис.2.1. Дракон

Стандартний шаблонний запис цього графа визначається умовою стандартності a2 У кожному з наступних розділів вживається те чи інше стандартне шаблонне представлення графів - компонент розкладу. Переваги, які дає шаблонне представлення графа порівняно зі стандартним, грунтується на тому, що шаблон являє собою жорстке представлення графа, а перестановка - змінну, гнучку компоненту цього представлення. Змінюючи перестановку, можна одержати представлення будь-якого графа, ізоморфного представленому шаблоном. Ця перевага особливо чітко проявляється і використовується у алгоритмах побудови та переліку T-факторизацій, поданих у розділах 3-5.
2.2. Методи побудови розкладів повних графів

Серед методів побудови розкладів чільне місце займав і продовжує займати циклічний метод і споріднені з ним методи. Ці методи належать до історично самих ранніх і використовувалися у дослідженнях Є.Нетто [2], Р.Пельтесон[12], Р.Боуза[19], C.Бейса [77], Т.Сколема [78] , Х.Ханані [20,21, 67] та ряду інших .
У даній дисертації застосовується як чисто циклічний метод (напр.,у пунктах 6.4-6.6,10.7), так і два споріднені з ним методи - біциклічний та півобертовий, описані відповідно у пунктах 3.2 та 3.7.
Біциклічний метод та описаний вище шаблонний спосіб запису графів дали змогу розв'язати задачу про існування біциклічних T-факторизацій порядку 14.
В основу описаного у розділі 3.2 алгоритму побудови біциклічної T-факторизації покладено слідуючий принцип. При фіксованих шаблоні дерева T і умовах стандартності пробігаємо у деякому порядку всі перестановки n вершин, перевіряючи кожне одержане дерево на стандартність та на біциклічність. Послідовність дерев, яка при цьому пробігається, називається трасою пошуку. Здавалось би, потрібно переглянути n! перестановок - така задача, навіть при не дуже великих n, забирає занадто багато часу(якщо взагалі досягає результату) навіть при застосуванні найсучасніших комп'ютерів. Проте є можливість уникнути занадто громіздкого перебору, якщо застосувати так звану стратегію стрибків, описану в розділі 4.
Ця стратегія дозволяє проходити трасу перебору досить великими стрибками, перестрибуючи через послідовності дерев, про які наперед відомо, що серед них немає шуканих біциклічних базових компонент. При цьому рішення про "дальність" стрибка приймається перед самим стрибком, виходячи з обставин, що склалися на цей момент.
В результаті цього перебір у випадку n=14 зменшується до такого, який можна провести за практично прийнятний час. У планах дисертанта на майбутнє є сподівання, що цей спосіб виявиться ефективним і для побудови біциклічних T-факторизацій порядків n=18 та n=22.
Півобертовий спосіб побудови T-факторизацій розвинутий дисертантом на основі часткового випадку цього способу, наведеного у відомій монографії К.Бержа про гіперграфи [7