Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4
The existence problem for T-factorizations of the complete graph K12 is investigated . With computer aid, more than 250 T-factorizations are constructed for some admissible non-isomorphic trees of the order.
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2005 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84937 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 / И.Э. Шулинок, Л.П. Петренюк, А.Я. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 140-145. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84937 |
|---|---|
| record_format |
dspace |
| spelling |
Шулинок, И.Э. Петренюк, Л.П. Петренюк, А.Я. 2015-07-17T06:01:53Z 2015-07-17T06:01:53Z 2005 Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 / И.Э. Шулинок, Л.П. Петренюк, А.Я. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 140-145. — Бібліогр.: 9 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84937 519.1 The existence problem for T-factorizations of the complete graph K12 is investigated . With computer aid, more than 250 T-factorizations are constructed for some admissible non-isomorphic trees of the order. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 Construction T-factorizations of the order 12 for trees with Δ(T) = 4 Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 |
| spellingShingle |
Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 Шулинок, И.Э. Петренюк, Л.П. Петренюк, А.Я. |
| title_short |
Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 |
| title_full |
Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 |
| title_fullStr |
Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 |
| title_full_unstemmed |
Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 |
| title_sort |
построение т-факторизаций порядка 12 для деревьев с δ(т)=4 |
| author |
Шулинок, И.Э. Петренюк, Л.П. Петренюк, А.Я. |
| author_facet |
Шулинок, И.Э. Петренюк, Л.П. Петренюк, А.Я. |
| publishDate |
2005 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Construction T-factorizations of the order 12 for trees with Δ(T) = 4 |
| description |
The existence problem for T-factorizations of the complete graph K12 is investigated . With computer aid, more than 250 T-factorizations are constructed for some admissible non-isomorphic trees of the order.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84937 |
| citation_txt |
Построение Т-факторизаций порядка 12 для деревьев с Δ(Т)=4 / И.Э. Шулинок, Л.П. Петренюк, А.Я. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 140-145. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT šulinokié postroenietfaktorizaciiporâdka12dlâderevʹevsδt4 AT petrenûklp postroenietfaktorizaciiporâdka12dlâderevʹevsδt4 AT petrenûkaâ postroenietfaktorizaciiporâdka12dlâderevʹevsδt4 AT šulinokié constructiontfactorizationsoftheorder12fortreeswithδt4 AT petrenûklp constructiontfactorizationsoftheorder12fortreeswithδt4 AT petrenûkaâ constructiontfactorizationsoftheorder12fortreeswithδt4 |
| first_indexed |
2025-11-24T18:05:51Z |
| last_indexed |
2025-11-24T18:05:51Z |
| _version_ |
1850485176406114304 |
| fulltext |
140 Теорія оптимальних рішень. 2005, № 4
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Исследуется задача существова-
ния T-факторизаций полного гра-
фа K12. Доказано, что существу-
ют не меньше 250 допустимых
деревьев порядка 12, для которых
существуют T-факторизации.
И.Э. Шулинок, Л.П. Петренюк,
А.Я. Петренюк, 2005
ÓÄÊ 519.1
È.Ý. ØÓËÈÍÎÊ, Ë.Ï. ÏÅÒÐÅÍÞÊ, À.ß. ÏÅÒÐÅÍÞÊ
ÏÎÑÒÐÎÅÍÈÅ T-ÔÀÊÒÎÐÈÇÀÖÈÉ
ÏÎÐßÄÊÀ 12 ÄËß ÄÅÐÅÂÜÅÂ
Ñ ∆∆∆∆((((ΤΤΤΤ)))) = 4
Введение. Исследуется задача существова-
ния T-факторизаций полного графа K12. До-
казано, что существуют не менее 250 допус-
тимых деревьев порядка 12, для которых су-
ществуют T-факторизации.
Формулировка задачи и предваритель-
ные сведения. Для дерева T порядка n и
полного графа Kn T-факторизацией графа Kn
называют такую совокупность деревьев {T1,
T2,…, Tk}, что: 1) все Ti изоморфны дереву T;
2) все Ti – подграфы графа Kn; 3) каждое реб-
ро графа Kn принадлежат одному и только
одному из деревьев T1, T2, …, Tk. Выяснить,
существует или нет T-факторизация графа Kn
для заданого дерева T ( такую задачу сфор-
мулировал в 1964 г. Л. Байнеке [1] ).
Л. Байнеке установил необходимые усло-
вия существования T-факторизации порядка
n: 1) четность числа n, n = 2k; 2) выполнение
неравенства ∆(T) ≤ k, где ∆(T) – наивысшая
степень вершины в дереве T. Деревья, удов-
летворяющие условиям Байнеке, называют
допустимыми.
Современное состояние задачи. Сле-
дующие шаги на пути решения этой задачи:
Ш. Хуанг и А. Роса [2] в 1978 г. нашли ответ
для всех порядков n, n ≤ 8, а затем А.Я. Пет-
ренюк [3, 4] решил ее в случае n = 10 полно-
стью и, за исключением 20 деревьев, в слу-
чае n = 14.
Достичь успеха в случаях n = 10 и n = 14
удалось благодаря необходимым условиям
существования T-факторизаций, найденным
автором статей [3,4], и бициклическому
ПОСТРОЕНИЕ T-ФАКТОРИЗАЦИЙ ПОРЯДКА 12 ДЛЯ ДЕРЕВЬЕВ С ∆(Τ) = 4
Теорія оптимальних рішень. 2005, № 4 141
методу построения T-факторизаций, посредством которого осуществлены по-
строения T-факторизаций в случаях их существования.
Несуществование T-факторизаций порядка 12 изложено в [5]; при получе-
нии ее результатов применены вышеупомянутые и найдены новые необходи-
мые условия существования. О существовании T-факторизаций порядка 12 идет
речь в [6, 7, 8, 9]. Дополнительные трудности при построении T-факторизаций
порядков n ≡ 0(mod 4) обусловлены несуществованием в этих случаях бицикли-
ческих T-факторизаций [3, 4]. На сегодня известно: 1) о существовании T-
факторизаций для 20 полусимметричных деревьев порядка 12 (эти T-
факторизации построены полувращательным методом [6] ); 2) о существовании
98 допустимих деревьев порядка 12 с ∆(T) = 3, для которых T-факторизации су-
ществуют [7].
Алгоритм построения T-факторизаций и результаты, полученные с помо-
щью программы, построенной на его основе, изложены в [7].
Основной результат. С помощью программы (см. [7]) авторы настоящей
статьи исследовали существование T-факторизаций для деревьев порядка 12 с
∆(T) = 4. Ниже приводятся T-факторизации для 50 деревьев этого класса. Под
каждым номером дано дерево T в канонической форме и компоненты соответст-
вующей T-факторизации. Деревья изображаются списками их ребер.
1. 12 13 14 15 26 27 38 49 8A 8B 9С 16 1B 1C 23 24 25 2C 47 58 59 7A
17 29 35 45 57 67 6C 78 89 9A BC 18 28 37 3A 48 4A 5A 6B 7C 9B AB
19 2B 3C 46 4B 56 5C 68 69 79 AC 1A 2A 34 36 39 3B 4C 5B 6A 7B 8C
2. 12 13 14 15 26 27 38 39 4A 5B 6C 16 1C 23 28 29 2C 34 35 7C 8A 9B
17 2B 3A 3B 46 4C 59 67 69 6B 78 18 25 3C 45 49 4B 6A 7A 8B AB BC
19 1B 2A 37 47 5C 68 79 89 9C AC 1A 24 36 48 56 57 58 5A 7B 8C 9A
3. 12 13 14 15 26 27 38 39 4A 5B AC 16 2A 34 37 56 57 5A 5C 6B 8C 9C
17 19 28 29 3B 46 58 69 6C 9B AB 18 24 25 2B 3A 3C 47 48 4C 67 89
1A 1B 23 36 49 59 6A 78 7A 7C 9A 1C 2C 35 45 4B 68 79 7B 8A 8B BC
4. 12 13 14 15 26 27 38 39 4A 6B 7C 16 17 2C 36 46 4B 4C 56 58 59 AB
18 29 37 45 5A 69 78 79 7A AC 19 2A 35 3B 47 48 6A 8A 8B 8C 9B
1A 24 3C 49 57 5B 5C 68 6C 9A 9C 1B 1C 23 25 28 2B 34 3A 67 7B 89
5. 12 13 14 15 26 27 38 39 4A 6B 8C 16 1B 2A 3A 3C 45 59 7B 89 9B AB
17 1C 23 24 25 46 47 48 5B 6A 79 18 2B 34 37 57 6C 7C 8B 9A 9C BC
19 28 36 49 4B 58 5C 67 68 69 7A 1A 29 2C 35 3B 4C 56 5A 78 8A AC
6. 12 13 14 15 26 27 38 39 4A 6B AC 16 28 29 2B 3B 49 5A 5B 5C 67 7B
17 1B 24 2A 37 46 47 57 58 59 BC 18 1C 23 34 36 56 68 69 78 9A AB
19 25 3C 45 4B 4C 6A 7A 7C 89 9C 1A 2C 35 3A 48 6C 79 8A 8B 8C 9B
7. 12 13 14 15 26 27 38 39 4A 6B BC 16 23 3C 46 57 5B 5C 6C 78 89 AC
17 18 2C 3B 4C 56 67 69 9A 9B 9C 19 24 2A 34 48 49 59 68 7B 7C 8B
1A 2B 36 3A 47 4B 58 79 7A 8A 8C 1B 1C 25 28 29 35 37 45 5A 6A AB
8. 12 13 14 15 26 27 38 39 4A AB BC 16 2C 3C 46 57 58 69 8A 9A 9B 9C
17 23 3B 4B 4C 5C 68 7A 7C 8C 18 1B 1C 2B 36 3A 47 56 5B 79 7B
И.Э. ШУЛИНОК, Л.П. ПЕТРЕНЮК, А.Я. ПЕТРЕНЮК
142 Теорія оптимальних рішень. 2005, № 4
19 24 2A 34 48 49 59 6A 6C 78 8B 1A 25 28 29 35 37 45 5A 67 6B AC
9. 12 13 14 15 26 27 38 39 6A 6B AC. 16 1A 1B 23 28 29 2A 34 35 6C 7A
17 2C 3C 49 56 59 5A 5C 78 79 8B 18 24 36 45 46 48 67 7B 7C 89 AB
19 25 37 4A 57 5B 69 8A 9A 9B BC 1C 2B 3A 3B 47 4B 4C 58 68 8C 9C
10. 12 13 14 15 26 27 38 39 6A 7B 8C 16 1C 24 34 37 3A 45 46 68 79 AB
17 1A 25 35 47 56 57 69 6B 89 BC 18 2B 36 3B 48 49 4A 58 7A 8B 9C
19 2A 3C 4B 59 5B 5C 6C 78 8A AC 1B 23 28 29 2C 4C 5A 67 7C 9A 9B
11. 12 13 14 15 26 27 38 39 6A 7B AC 16 24 34 37 3A 45 46 68 79 9C AB
17 25 35 47 56 57 69 6B 89 8A BC 18 1A 23 2A 2B 2C 4C 59 6C 78 9A
19 29 36 3C 4B 5A 5B 5C 7A 8B 9B 1B 1C 28 3B 48 49 4A 58 67 7C 8C
12. 12 13 14 15 26 27 38 39 6A 8B AC 16 1B 24 34 37 3A 45 46 68 79 9C
17 1A 25 35 47 56 57 69 6B 89 8C 18 2A 3C 4B 58 67 78 7C 8A 9A 9B
19 23 28 29 2B 49 4C 5B 6C 7A AB 1C 2C 36 3B 48 4A 59 5A 5C 7B BC
13. 12 13 14 15 26 27 38 39 6A AB BC 16 28 36 47 57 5B 5C 67 7A 89 9C
17 1A 1C 2B 2C 3A 49 5A 69 8B 9A 18 24 29 2A 34 45 48 6B 6C 78 7B
19 25 35 4B 4C 58 59 68 79 7C 8A 1B 23 37 3B 3C 46 4A 56 8C 9B AC
14. 12 13 14 15 26 27 38 49 5A 6B 6C 16 25 2C 36 3B 3C 48 4C 67 9A 9C
17 2B 34 35 46 47 4A 69 7B 8A BC 18 19 1A 23 28 4B 58 5C 6A 7A 8B
1B 24 29 37 39 56 59 5B 89 8C AB 1C 2A 3A 45 57 68 78 79 7C 9B AC
15. 12 13 14 15 26 27 38 49 5A 6B 7C 16 25 2C 36 3B 3C 48 4C 67 9A 9C
17 2B 34 35 46 47 4A 69 7B 8A BC 18 19 1A 23 28 4B 58 5C 6A 7A 8B
1B 24 29 37 39 56 59 5B 89 8C AB 1C 2A 3A 45 57 68 78 79 7C 9B AC
16. 12 13 14 15 26 27 38 49 5A 8B 8C 16 1A 2C 37 45 4A 58 59 7A 7B AC
17 1C 24 25 2A 36 47 67 79 89 9B 18 28 39 3B 48 4B 5C 6A 6B 7C BC
19 23 29 34 35 3A 46 57 8A 9C AB 1B 2B 3C 4C 56 5B 68 69 6C 78 9A
17. 12 13 14 15 26 27 38 49 5A 8B 9C 16 25 29 35 3A 45 48 56 67 8C 9B
17 23 28 34 36 37 4B 57 6A 89 AC 18 1A 2A 2B 39 4A 4C 59 6C 7B 9A
19 1B 2C 3C 46 58 5B 6B 79 8A BC 1C 24 3B 47 5C 68 69 78 7A 7C AB
18. 12 13 14 15 26 27 38 49 6A 6B 7C 16 19 25 28 35 37 45 59 9A AB AC
17 1B 23 36 3A 3B 4C 5C 69 8A BC 18 24 29 34 47 48 57 5A 5B 67 6C
1A 2C 39 4A 56 68 78 79 7A 8B 8C 1C 2A 2B 3C 46 4B 58 7B 89 9B 9C
19. 12 13 14 15 26 27 38 49 6A 6B 8C 16 2B 2C 3C 46 56 5A 5C 78 79 9C
17 23 39 3A 3B 4A 4C 5B 67 7B 89 18 1A 24 29 34 47 48 57 6C 7C BC
19 25 28 35 37 45 59 68 9A AB AC 1B 1C 2A 36 4B 58 69 7A 8A 8B 9B
20. 12 13 14 15 26 27 38 49 6A 8B 8C 16 19 1C 23 24 29 2A 45 78 8A AB
17 2C 39 46 57 58 5C 67 7A 9A 9B 18 28 3A 3B 48 4B 5B 69 6C 7C BC
1A 25 37 4A 4C 56 59 5A 68 79 7B 1B 2B 34 35 36 3C 47 6B 89 9C AC
21. 12 13 14 15 26 27 38 49 6A AB AC 16 24 28 2C 36 46 58 5B 7A 89 8A
17 23 29 45 56 5A 67 79 8B 9B 9C 18 19 25 39 47 4B 57 68 78 7C 9A
1A 2A 3A 3B 48 4C 5C 69 6C 7B BC 1B 1C 2B 34 35 37 3C 4A 59 6B 8C
22. 12 13 14 15 26 27 38 49 6A AB BC 16 17 23 3B 4B 4C 5B 69 78 7B 9A
18 25 2B 39 3C 45 56 5C 67 89 AC 19 2C 34 36 47 57 6B 7C 8A 8C 9C
ПОСТРОЕНИЕ T-ФАКТОРИЗАЦИЙ ПОРЯДКА 12 ДЛЯ ДЕРЕВЬЕВ С ∆(Τ) = 4
Теорія оптимальних рішень. 2005, № 4 143
1A 24 35 48 58 59 68 6C 79 7A 8B 1B 1C 28 29 2A 37 3A 46 4A 5A 9B
23. 12 13 14 15 26 27 38 49 8A 8B 9C 16 1A 1C 23 24 25 2C 47 58 59 7B
17 29 35 45 57 67 6C 78 89 9B AC 18 28 37 3B 48 4B 5B 6A 7C 9A AB
19 2A 3C 46 4A 56 5C 68 69 79 BC 1B 2B 34 36 39 3A 4C 5A 6B 7A 8C
24. 12 13 14 15 26 27 38 49 8A 8B AC 16 29 2C 35 3A 45 56 58 67 89 9B
17 2A 3B 46 5A 5C 68 6A 7A 9C BC 18 2B 3C 47 4A 4B 59 5B 6B 6C 8C
19 1A 1C 23 24 25 36 37 39 78 AB 1B 28 34 48 4C 57 69 79 7B 7C 9A
25. 12 13 14 15 26 27 38 49 8A 9B AC 16 1A 23 24 25 56 57 58 79 9C AB
17 29 39 3B 47 5A 5C 6B 7B 8B 8C 18 2C 37 3C 4B 4C 5B 69 6A 6C 78
19 1C 28 2B 36 45 46 48 4A 59 67 1B 2A 34 35 3A 68 7A 7C 89 9A BC
26. 12 13 14 15 26 27 38 49 8A AB AC 16 19 29 34 36 37 3C 4A 59 78 7B
17 25 2C 39 4B 58 5A 6B 79 9B 9C 18 23 28 35 48 56 57 5B 69 7A 7C
1A 2A 2B 3A 47 4C 5C 68 89 8C BC 1B 1C 24 3B 45 46 67 6A 6C 8B 9A
27. 12 13 14 15 26 27 38 49 8A AB BC 16 1B 23 24 25 56 57 58 7A 9B 9C
17 28 37 4B 4C 5B 68 6C 78 89 9A 18 19 2A 34 35 3A 3B 5C 6A 79 7B
1A 2B 39 3C 47 5A 69 6B 7C 8C AC 1C 29 2C 36 45 46 48 4A 59 67 8B
28. 12 13 14 15 26 27 38 69 6A 7B 8C 16 19 1A 24 27 34 45 46 67 7C 8B
17 23 36 39 3A 4B 58 5A 5C 79 AB 18 25 35 47 49 4A 56 57 6B 78 BC
1B 2A 2B 2C 3C 48 5B 6C 7A 89 9C 1C 29 37 3B 4C 59 68 8A 9A 9B AC
29. 12 13 14 15 26 27 38 69 6A 7B 9C 16 19 1A 24 28 34 45 46 67 7C 9B
17 23 36 39 3A 48 59 7A 8A 8B BC 18 25 35 47 49 4C 56 57 6B 78 9A
1B 2B 37 3B 4A 58 5B 5C 6C 89 AC 1C 29 2A 2C 3C 4B 5A 68 79 8C AB
30. 12 13 14 15 26 27 38 69 6A 7B BC 16 19 1B 24 28 34 45 46 67 7A AC
17 29 3B 4B 58 5A 68 79 9A 9C AB 18 2A 2B 2C 37 3C 4C 5B 6C 8A 9B
1A 23 36 39 3A 48 59 5C 7C 89 8B 1C 25 35 47 49 4A 56 57 6B 78 8C
31. 12 13 14 15 26 27 38 69 6A 8B 9C 16 19 1A 24 28 34 45 46 67 8C 9B
17 25 35 47 4A 4B 56 57 68 89 AC 18 29 2A 2B 39 4C 58 5C 6C 7B BC
1B 2C 3B 3C 48 5A 6B 78 79 7A AB 1C 23 36 37 3A 49 59 5B 7C 8A 9A
32 12 13 14 15 26 27 38 69 6A 8B BC 16 19 1B 24 28 34 45 46 67 8A AC
17 25 35 47 4A 4B 56 57 68 89 9C 18 23 36 37 3C 48 5C 79 8C 9A AB
1A 2B 2C 39 49 58 59 5A 6C 7A 9B 1C 29 2A 3A 3B 4C 5B 6B 78 7B 7C
33. 12 13 14 15 26 27 38 69 6A 9B 9C 16 24 34 37 39 45 46 78 7A 8B 8C
17 25 35 48 49 4C 56 57 68 6B 8A 18 1A 1C 2B 3A 47 5C 67 7C 9A AB
19 23 29 2A 36 3B 4B 58 79 89 BC 1B 28 2C 3C 4A 59 5A 5B 6C 7B AC
34. 12 13 14 15 26 27 38 69 6A 9B AC 16 19 1A 24 28 34 45 46 67 9C AB
17 25 35 47 49 4B 56 57 68 9A BC 18 29 2A 2C 3A 48 59 6B 7C 89 8B
1B 23 36 37 3B 4C 5A 5B 5C 79 8A 1C 2B 39 3C 4A 58 6C 78 7A 7B 8C
35. 12 13 14 15 26 27 38 69 7A 9B 9C 16 1A 24 27 34 45 46 67 79 AB AC
17 18 25 35 47 49 56 57 6A 8B 8C 19 2C 37 3C 48 4B 59 5B 6C 9A BC
1B 29 2A 2B 3B 4A 58 68 7B 7C 89 1C 23 36 39 3A 4C 5A 5C 6B 78 8A
36. 12 13 14 15 26 27 38 69 6A 9B BC 16 19 1B 24 28 34 45 46 67 9A AC
17 25 35 47 48 4A 56 57 6B 89 9C 18 2B 2C 3A 4C 5B 68 78 79 8A AB
И.Э. ШУЛИНОК, Л.П. ПЕТРЕНЮК, А.Я. ПЕТРЕНЮК
144 Теорія оптимальних рішень. 2005, № 4
1A 29 2A 3B 3C 49 58 5A 5C 6C 7C 1C 23 36 37 39 4B 59 7A 7B 8B 8C
37. 12 13 14 15 26 27 38 69 7A 8B 9C 16 1B 24 34 37 39 45 46 78 8C 9A
17 19 25 35 48 4C 56 57 68 6A AB 18 2B 3A 3B 3C 4B 59 6C 79 7B 8A
1A 2C 36 49 58 5A 5C 6B 7C 89 BC 1C 23 28 29 2A 47 4A 5B 67 9B AC
38. 12 13 14 15 26 27 38 69 7A 8B BC 16 1A 24 34 37 39 45 46 78 9B BC
17 19 25 35 48 56 57 68 6A 9C AB 18 23 29 2A 2B 47 49 5A 5C 6C 89
1B 2C 36 3A 3B 44B 58 5B 67 8C 9A 1C 28 3C 4A 4C 59 6B 79 7B 7C 8A
39. 12 13 14 15 26 27 38 69 7A 9B 9C 16 1A 24 28 34 45 46 67 79 AB AC
17 18 25 35 47 49 56 57 6A 8B 8C 19 2C 37 3C 48 4B 59 5B 6C 9A BC
1B 29 2A 2B 3B 4A 58 68 7B 7C 89 1C 23 36 39 3A 4C 5A 5C 6B 78 8A
40. 12 13 14 15 26 27 38 69 7A 9B AC 16 24 34 37 39 45 46 78 8C 9A AB
17 25 35 4A 4B 56 57 68 6A 89 9C 18 2A 3B 3C 48 59 6C 79 7B 8A 8B
19 23 28 29 2B 47 5A 5C 67 6B BC 1A 1B 1C 2C 36 3A 49 4C 58 5B 7C
41. 12 13 14 15 26 27 38 69 7A 9B BC 16 24 34 37 39 45 46 78 8A 9C AB
17 25 35 49 4B 56 57 68 6A 89 AC 18 2B 3A 3B 3C 4C 58 5A 6B 79 7B
19 1C 23 28 29 2A 4A 59 5B 67 7C 1A 1B 2C 36 47 48 5C 6C 8B 8C 9A
42. 12 13 14 15 26 27 38 69 8A 8B 9C 16 18 24 29 34 45 46 67 8C 9A 9B
17 1B 25 35 48 56 57 68 7A 89 BC 19 28 2A 2B 3B 49 4B 59 6B 7C AC
1A 2C 3A 3C 4C 58 5A 5B 6A 79 7B 1C 23 36 37 39 47 4A 5C 6C 78 AB
43. 12 13 14 15 26 27 38 69 8A 8B AC 16 1A 24 28 34 45 46 67 89 8C 9B
17 18 25 35 47 56 57 6A 9A 9C AB 19 23 36 37 3A 48 4A 4C 58 79 7B
1B 29 2A 39 3B 49 5B 6C 78 7C BC 1C 2B 2C 3C 4B 59 5A 5C 68 6B 7A
44. 12 13 14 15 26 27 38 69 8A 9B 9C 16 28 2B 2C 34 45 46 47 68 79 9A
17 19 29 3C 4A 4C 5A 67 7A 7B 8C 18 24 25 35 49 57 58 6A 6B 6C 8B
1A 2A 37 3A 4B 56 59 5C 78 AB BC 1B 1C 23 36 39 3B 48 5B 7C 89 AC
45.12 13 14 15 26 27 38 69 8A 9B AC 16 1A 24 34 37 39 45 46 78 8C AB
17 19 25 35 48 4B 56 57 68 6A 9C 18 2B 3B 3C 47 5C 67 7A 7B 89 9A
1B 2C 36 3A 4A 58 59 6C 7C 8B BC 1C 23 28 29 2A 49 4C 5A 5B 6B 79
46. 12 13 14 15 26 27 38 69 8A 9B BC 16 1B 24 34 37 39 45 46 78 8C AC
17 1C 25 35 49 4B 56 57 68 6A 89 18 2C 36 3A 3C 48 4A 5B 7B 7C 9C
19 23 28 29 2B 47 59 5A 6B 6C 7A 1A 2A 3B 4C 58 5C 67 78 8B 9A AB
47. 12 13 14 15 26 27 38 69 8A AB AC 16 1A 24 28 34 45 46 67 89 9B 9C
17 19 25 35 4A 4B 4C 56 57 6A 78 18 29 2A 2C 3C 48 5C 6B 6C 79 8B
1B 2B 3A 3B 47 58 59 5B 68 7A 7C 1C 23 36 37 39 49 5A 7B 8C 9A BC
48.12 13 14 15 26 27 38 69 8A AB BC 16 1B 26 34 37 39 45 46 7A 8B 8C
17 1C 25 35 48 56 57 68 6A 9B 9C 18 2C 3C 47 58 5B 6B 6C 79 7C 9A
19 23 28 29 2A 4A 4B 59 5C 67 7B 1A 2B 36 3A 3B 49 4C 5A 78 89 AC
49. 12 13 14 15 26 27 38 69 9A 9B AC 16 1B 24 28 34 45 46 67 9C AB BC
17 18 25 35 48 4C 56 57 6A 79 8B 19 29 2B 37 49 5C 68 6C 7C 89 8A
1A 2A 2C 39 3B 47 4B 5A 6B 78 7A 1C 23 36 3A 3C 4A 58 59 5B 7B 8C
50.12 13 14 15 26 27 38 69 9A AB AC 16 1A 24 29 34 45 46 67 8A 8B 8C
17 18 25 35 47 56 57 6A 89 9B 9C 19 28 2A 2B 36 3B 4B 59 5A 79 BC
ПОСТРОЕНИЕ T-ФАКТОРИЗАЦИЙ ПОРЯДКА 12 ДЛЯ ДЕРЕВЬЕВ С ∆(Τ) = 4
Теорія оптимальних рішень. 2005, № 4 145
1B 2C 3C 48 49 4C 5B 68 6B 7A 7C 1C 23 37 39 3A 4A 58 5C 6C 78 7B.
Заключение. В последующих публикациях авторы продолжат этот список.
Общее количество деревьев порядка 12 с ∆(Τ) = 4, для которых известны T-фак-
торизации, превышает 120. Всего на момент написания данной статьи известно
более 250 деревьев порядка 12 (всего их 551 дерево), для которых задача Байне-
ке полностью решена.
І.Е. Шулінок, Л.П. Петренюк, А.Я. Петренюк
ПОБУДОВА T-ФАКТОРИЗАЦІЙ ПОРЯДКУ 12 ДЛЯ ДЕРЕВ С ∆(Τ) = 4
Досліджується задача існування T-факторизацій повного графу K12. Доведено, що є не менше
250 допустимих дерев порядку 12, для яких існують T-факторизації.
I.E. Shoolinock, L. P. Petrenjuk, A.J. Petrenjuk
CONSTRUCTION T-FACTORIZATIONS OF THE ORDER 12 FOR TREES WITH ∆(Τ) = 4
The existence problem for T-factorizations of the complete graph K12 is investigated . With comput-
er aid, more than 250 T-factorizations are constructed for some admissible non-isomorphic trees of
the order.
1. Beineke L.W. Decomposition of complete graphs into forests // Magyar Tud. Akad. Mat.
Kut. Int. Közl. – 1964. – N 9. – P. 589–594.
2. Huang C., Rosa A. Decomposition of complete graphs into trees // Ars Combinatoria –
1978. – N 5. – P. 23–63.
3. Petrenjuk A.J. On tree factorizations of K10 // J. of Combin. Math. and Combin. Computing
– 2002. – 41. – P. 193–202.
4. Петренюк А.Я. Древесные факторизации полных графов: существование, построе-
ние, перечисление // Материалы 7 Междунар. семинара “Дискретная математика и ее
приложения” (Москва, 29 января – 2 февраля 2001 г.). – М., 2001. – С. 26 – 30.
5. Петренюк А.Я. Неіснування деяких T-факторизацій порядку 12 // Укр. мат.. журнал.
– 2004. – 57, №7. – С. 718 – 727.
6. Петренюк А.Я. Півобертові деревні факторизації повних графів // Укр. мат. журнал.
– 2001. – 53, №5. – С. 710–716.
7. Петренюк Л.П., Петренюк А.Я. Існування деяких T-факторизацій порядку 12 // Наук.
записки. Сер. Мат. науки. – Кіровоград: РВВ КДПУ ім.В.Винниченка, 2004. – С. 76–
87.
8. Petrenjuk A. J. Petrenjuk D. A.., The nonexistence of some T-factorizations // Матеріали
ІІ Міжнар. наук.-практ. конф. “Динаміка наукових досліджень – 2003”, 20–27 жовтня
2003 р. – Дніпропетровськ – Кіровоград – Одеса – Дніпропетровськ: Наука і освіта,
2003. – 32. – С. 19–20.
9. Петренюк Л.П. Петренюк А.Я. 100 новых T-факторизаций порядка 12 // Материалы
8 Междунар. семинара “Дискретная математика и ее приложения” (Москва, 29
января – 2 февраля 2004 г.). – М., 2004. – С. 355–357.
И.Э. ШУЛИНОК, Л.П. ПЕТРЕНЮК, А.Я. ПЕТРЕНЮК
146 Теорія оптимальних рішень. 2005, № 4
Получено 24.03.2005
|