Існування Т-факторизації непарного порядку для симетричних дерев
Досліджується питання про існування Т-факторизації повно-го графа Kn непарного порядку n = 2k +1. За допомогою пів-обертового методу підтверджується гіпотеза «Кожне си-метричне дерево допускає Т-факторизацію» для дерева порядку n=13, n=17. За результатами досліджень складено таблицю. Исследуется воп...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2009 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46641 |
| 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: | Існування Т-факторизації непарного порядку для симетричних дерев / О.В. Мироненко // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 69-73. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859606061919502336 |
|---|---|
| author | Мироненко, О.В. |
| author_facet | Мироненко, О.В. |
| citation_txt | Існування Т-факторизації непарного порядку для симетричних дерев / О.В. Мироненко // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 69-73. — Бібліогр.: 6 назв. — укр. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Досліджується питання про існування Т-факторизації повно-го графа Kn непарного порядку n = 2k +1. За допомогою пів-обертового методу підтверджується гіпотеза «Кожне си-метричне дерево допускає Т-факторизацію» для дерева порядку n=13, n=17. За результатами досліджень складено таблицю.
Исследуется вопрос о существовании T-факторизаци полного графа Кn нечетного порядка n = 2k + 1. С помощью полуоборотного метода подтверждается гипотеза «Каждое симметрическое дерево нечетного порядка допускает T-факторизацию» для деревьев порядка n = 13, n = 15, n = 17. По результатам исследований составлена таблица.
In this paper we explore the problem of the existence of T-factorization of complete graph Кn of odd order n = 2k + 1. The research in this direction is confirm the hypothesis «For each symmetrical tree of odd order T-factorization is possible» for tress of order n = 13, n = 15, n = 17 with the help of a half-turned method. The results of studies are presented in the form of table.
|
| first_indexed | 2025-11-28T03:03:17Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2009, № 8 69
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Досліджується питання про
існування Т-факторизації
повно-го графа
nK непарного
порядку 2 1.n k= + За допомо-
гою пів-обертового методу
підтверджується гіпотеза
«Кожне си-метричне дерево
допускає
Т-факторизацію» для дерева по-
рядку n=13, n=17. За результа-
тами досліджень складено
таблицю.
_____________________________
О.В. Мироненко, 2009
ÓÄÊ 519.1
Î.Â. ÌÈÐÎÍÅÍÊÎ
²ÑÍÓÂÀÍÍß Ò-ÔÀÊÒÎÐÈÇÀÖ²¯
ÍÅÏÀÐÍÎÃÎ ÏÎÐßÄÊÓ
ÄËß ÑÈÌÅÒÐÈ×ÍÈÕ ÄÅÐÅÂ
T-факторизація повного графа порядку n – це
таке розбиття множини ребер повного графа
Kn на k підмножин (факторів), кожна з яких
породжує дерево (компоненту T-фак-
торизації), ізоморфне даному дереву T по-
рядку n.
Задача Л. Байнеке [1] полягає у тому, щоб
з’ясувати, для яких дерев існують T-фак-
торизації. Він же знайшов необхідні умови
існування T-факторизації:
1) n – парне натуральне число, n = 2k;
2) ∆(T) ≤ k , де ∆(T) – найбільший із степе-
нів вершин дерева T.
Дерево називають допустимим, якщо воно
задовольняє умовам Байнеке. Для багатьох
допустимих дерев доведено існування T-фак-
торизацій, для багатьох інших – що T-факто-
ризації не існують [2 – 4]. Повного розв’я-
зання задачі Байнеке на даний час не існує.
Постає питання про існування деревної
факторизації непарного порядку. Для графа
Кn , де n = 2k+1 така факторизація не існує.
Розглянемо граф К2k+1 – F, де F – майже
1-фактор (рис. 1).
Гіпотеза. Кожне симетричне дерево не-
парного порядку допускає деревну факто-
ризацію.
Одним з методів побудови реалізуючих
Т-факторизацій є півобертовий метод. За цим
методом автором було отримано півобертові
реалізуючі факторизації для півсиметричних
дерев парного порядку 10 [5].
О.В. МИРОНЕНКО
70 Теорія оптимальних рішень. 2009, № 8
▪▪▪
▪
РИС. 1
Введемо наступні поняття [2].
Дерево порядку n=2k+1 називається си-
метричним, якщо:
1) воно містить центральну вершину;
2) після вилучення цієї вершини воно роз-
падається на два ізоморфні кореневі дерева,
коренями яких є кінці ребер, що сполуча-
ються у центральній вершині.
Симетричне дерево Т порядку n=2k+1 на-
зивається правильно вписаним у коло,
розділене n=2k точками на рівні дуги, якщо:
1) точки поділу є вершини дерева Т;
2) ребра дерева Т зображаються хордами кола;
3) для кожної допустимої довжини хорди рівно два нецентральних ребра
мають таку довжину;
4) для кожного ребра (а; b) існує симетричне йому відносно центра кола
ребро (а+k; b+k) дерева Т;
5) центром кола є центральна вершина дерева.
1
2k 2
. . ∞ .
. .
.
. k
k+1
РИС. 2
Під дією циклічної підстановки
α=(1, 2 …n) вершин дерева Т порядку
2k+1, правильно вписанного у ко-ло,
отримаємо сімейство дерев Т, Тα,…,
Тα
k–1
, яке являє собою T-факто-
ризацію графа Кn, де n=2k+1, яку
називають півобертовою.
Дерево Т, яке породжує описаним
методом півобертову T-факторизацію,
називають її базовою компонентою.
Для часткового підтвердження ви-
сунутої гіпотези розглянуто симетри-
чні дерева непарного порядку (до 17-
го порядку включно).
Для побудови симетричних дерев більш високих порядків використано діаг-
рами всіх можливих дерев наведених у [6] з кількістю вершин p = {6, 7, 8, 9} за
принципом n=2p – 1, тобто як половинок дерев відповідно 11, 13, 15 та 17-го
порядків, симетричних відносно центральної вершини. До отриманих дерев та-
кож застосовано півобертовий метод знаходження базових компонент Т-фак-
торизацій.
За допомогою півобертового методу побудовано всі базові компоненти для
порядку n = 13 (у кількості 20), 27 для порядку n = 15 (при загальній кількості
48) і 10 для n = 17 ( при загальній кількості 116 ).
ІСНУВАННЯ T-ФАКТОРИЗАЦІЇ НЕПАРНОГО ПОРЯДКУ ДЛЯ СИМЕТРИЧНИХ ДЕРЕВ
Теорія оптимальних рішень. 2009, № 8 71
За результатами досліджень складено таблицю, яка наводиться далі.
ТАБЛИЦЯ. Існування деревної факторизації непарного порядку для симетричних дерев
Порядок
дерева
Кількість
симетричних
дерев
Базові компоненти
n = 3 1 1) 01 02
n = 5 1 1) 14 1∞ 23 3∞
n = 7 2
1) 15 1∞ 23 24 4∞ 56
2) 1∞ 15 16 24 34 4∞
n = 9 4
1) 1∞ 16 24 25 34 5∞ 68 78
2) 1∞ 16 17 18 25 35 45 5∞
3) 1∞ 12 13 38 47 56 57 5∞
4) 1∞ 16 23 24 25 5∞ 67 68
n = 11 9
1) 1∞ 12 25 26 2А 34 35 6∞ 89 8А
2) 1∞ 17 18 19 1А 26 36 46 56 6∞
3) 1∞ 17 18 26 2А 34 36 57 6∞ 89
4) 1∞ 17 18 26 35 36 45 6∞ 8А 9А
5) 1∞ 17 18 19 26 36 45 46 6∞ 9А
6) 1∞ 17 24 25 26 34 6∞ 79 7А 89
7) 1∞ 17 23 24 25 26 6∞ 78 79 7А
8) 1∞ 15 23 24 25 6∞ 6А 78 79 7А
9) 1∞ 14 15 24 34 68 69 6А 79 89
n = 13 20
1) 1∞ 18 26 27 35 36 45 7∞ 8С 9В 9С АВ
2) 1∞ 18 19 1А 1В 1С 7∞ 72 73 74 75 76
3) 1∞ 13 15 16 25 34 7∞ 79 7В 7С 8В 9А
4) 1∞ 13 14 15 16 23 7∞ 79 7А 7В 7С 89
5) 1∞ 15 16 23 25 46 7∞ 7В 7С 8В 89 АС
6) 1∞ 14 15 16 23 24 7∞ 7А 7В 7С 89 8А
7) 1∞ 13 16 25 26 45 7∞ 79 7С 8В 8С АВ
8) 1∞ 16 26 36 46 56 7∞ 7С 8С 9С АС ВС
9) 1∞ 16 26 36 45 46 7∞ 7С 8С 9С АВ АС
10) 1∞ 16 25 26 34 46 7∞ 7С 8В 8С 9А АС
11) 1∞ 16 26 35 36 45 7∞ 7С 8С 9В 9С АВ
12) 1∞ 16 23 24 25 26 7∞ 7С 89 8А 8В 8С
13) 1∞ 16 34 47 57 67 7∞ 7С 8А 8В 8С 9А
14) 1∞ 16 25 26 35 45 7∞ 7С 8В 8С 9В АВ
15) 1∞ 15 16 23 24 25 7∞ 7В 7С 89 8А 8В
16) 1∞ 15 16 25 34 25 7∞ 7В 7С 8В 9А 9В
17) 1∞ 15 16 25 35 45 7∞ 7В 7С 8В 9В АВ
18) 1∞ 15 16 2С 36 45 68 7∞ 7В 7С 9С АВ
19) 1∞ 16 23 25 26 46 7∞ 7С 89 8В 8С АС
20) 1∞ 14 15 16 24 34 7∞ 7А 7В 7С 8А 9А
О.В. МИРОНЕНКО
72 Теорія оптимальних рішень. 2009, № 8
Закінчення табл.
Порядок
дерева
Кількість
симетричних
дерев
Базові компоненти
n = 15 48
1) 1∞ 17 26 27 35 36 45 8∞ 8Е 9D 9E AC AD BC
2) 1∞ 17 26 27 36 45 46 8∞ 8E 9D 9E AD BC BD
3) 1∞ 17 27 36 37 45 46 8 8E 9E AD AE BC BD
4) 1∞ 16 17 26 35 45 47 8∞ 8D 8E 9D AC BC BE
5) 1∞ 17 26 27 34 35 36 8 8E 9D 9E AB AC AD
6) 1∞ 16 17 25 26 34 35 8∞ 8D8E9C 9D AB AC
7) 1∞ 17 24 26 27 36 45 8∞ 8E 9B 9D 9E AD BC
8) 1∞ 17 25 27 34 37 46 8∞ 8E 9C 9E AB AE BD
9) 1∞ 14 17 26 27 34 35 8∞ 8B 8E 9D 9E AB AC
10) 1∞ 17 25 26 27 34 35 8∞ 8E 9C 9D 9E AB AC
11) 1∞ 17 26 27 36 46 56 8∞ 8E 9D 9E AD BD CD
12) 1∞ 15 16 17 24 25 34 8∞ 8C 8D 8E 9B 9C AB
13) 1∞ 17 24 25 26 27 34 8∞ 8E 9B 9C 9D 9E AB
14) 1∞ 17 27 37 46 47 56 8∞ 8E 9E AE BD BE CD
15) 1∞ 13 16 17 25 26 34 8∞ 8A 8D 8E 9C 9D AB
16) 1∞ 17 27 36 37 45 57 8∞ 8E 9E AD AE BC CE
17) 1∞ 14 16 17 24 37 56 8∞ 8B 8D 8E 9B AE CD
18) 1∞ 17 23 24 25 26 27 8∞ 8E 9A 9B 9C 9D 9E
19) 1∞ 14 15 16 17 23 24 8∞ 8B 8C 8D 8E 9A 9B
20) 1∞ 17 27 37 47 56 57 8∞ 8E 9E AE BE CD CE
21) 1∞ 13 15 16 17 25 34 8∞ 8A 8C 8D 8E 9C AB
22) 1∞ 17 27 37 47 57 67 8∞ 8E 9E AE BE CE DE
23) 1∞ 13 14 15 16 17 23 8∞ 8A 8B 8C 8D 8E 9A
24) 1∞ 12 13 14 15 16 17 8∞ 89 8A 8B 8C 8D 8E
25) 1∞ 16 17 25 26 35 45 8∞ 8D 8E 9C 9D AC BC
26) 1∞ 17 27 36 37 46 56 8∞ 8E 9E AD AE BD CD
27) 1∞ 16 17 24 25 26 34 8∞ 8D 8E 9B 9C 9D AB
…
n = 17 116
1) 1∞ 18 27 28 34 36 48 57 9∞ 9К AF AK BC BE
CK DF
2) 1∞ 18 27 28 37 47 57 67 9∞ 9K AF AK BF CF DF
EF
3) 1∞ 16 18 25 28 35 48 67 9∞ 9E 9K AD AK BD
CK EF
4) 1∞ 18 23 26 27 28 47 57 9∞ 9K AB AE AF AK
CF DF
5) 1∞ 17 18 27 37 47 57 67 9∞ 9F 9K AF BF CF DF
EF
6) 1∞ 18 23 25 27 28 46 48 9∞ 9K AB AD AF AK
CE CK
7) 1∞ 18 23 25 27 28 48 68 9∞ 9K AB AD AF AK
ІСНУВАННЯ T-ФАКТОРИЗАЦІЇ НЕПАРНОГО ПОРЯДКУ ДЛЯ СИМЕТРИЧНИХ ДЕРЕВ
Теорія оптимальних рішень. 2009, № 8 73
CK EK
8) 1∞ 17 18 26 27 34 35 36 9∞ 9F 9K AE AF BC BD
BE
9) 1∞ 18 28 38 48 58 67 68 9∞ 9K AK BK CK DK
EF EK
10) 1∞ 18 25 27 28 34 46 48 9∞ 9K AD AF AK BC
CE CK
…
Всі отримані результати повністю підтверджують висунуту гіпотезу. Це дає
можливість сподіватися, що для всіх симетричних дерев непарного порядку вона
справедлива. Дослідження продовжуються.
О.В. Мироненко
СУЩЕСТВОВАНИЕ T-ФАКТОРИЗАЦИИ НЕЧЕТНОГО ПОРЯДКА
ДЛЯ СИММЕТРИЧЕСКИХ ДЕРЕВЬЕВ
Исследуется вопрос о существовании T-факторизаци полного графа Кn нечетного порядка
n = 2k + 1. С помощью полуоборотного метода подтверждается гипотеза «Каждое симметри-
ческое дерево нечетного порядка допускает T-факторизацию» для деревьев порядка
n = 13, n = 15, n = 17. По результатам исследований составлена таблица.
O.V. Mironenko
THE EXISTENCE OF T-FACTORIZATION OF ODD ORDER FOR SYMMETRICAL TREES
In this paper we explore the problem of the existence of T-factorization of complete graph Кn of odd
order n = 2k + 1. The research in this direction is confirm the hypothesis «For each symmetrical tree
of odd order T-factorization is possible» for tress of order n = 13, n = 15, n = 17 with the help of a
half-turned method. The results of studies are presented in the form of table.
1. Beineke L.W. Decomposition of complete graphs into forests // Magyar Tud. Acad. Mat. Kut. Int.
Közl.– 1964.– 9.– P. 589–594.
2. Petrenjuk A.J. On tree factorizations of K 10 // J. of Combin. Math. and Combin. – Computing –
2002.– 41. Р. 193–202.
3. Петренюк А.Я. Півобертові деревні факторизації повних графів // Укр. мат. журн. – 2001.
53, № 5. – С. 710–716.
4. Петренюк А.Я. Древесные факторизации полных графов: существование, построение, пе-
речисление // Материлы 7 Междунар. семинара «Дискретная математика и ее приложе-
ния». (Москва, 29 января – 2 февраля 2001). – М.: МГУ, 2001. – С. 26–30.
5. Мироненко О.В. Нові результати у типовій задачі існування T-факторизацій порядку 10 //
Вісн. Тернопільського держ. техн. ун-ту. – 2006. – № 2. – С. 116–125.
6. Харари Фрэнк. Теория графов / Пер. с англ. и предисл. В.П. Козырева. Под ред.
Г.П. Гаврилова. Изд. 2-е. – М.: Едиториал УРСС, 2003. – 267 с.
Отримано 16.03.2009
|
| id | nasplib_isofts_kiev_ua-123456789-46641 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Ukrainian |
| last_indexed | 2025-11-28T03:03:17Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Мироненко, О.В. 2013-07-04T19:05:04Z 2013-07-04T19:05:04Z 2009 Існування Т-факторизації непарного порядку для симетричних дерев / О.В. Мироненко // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 69-73. — Бібліогр.: 6 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46641 519.1 Досліджується питання про існування Т-факторизації повно-го графа Kn непарного порядку n = 2k +1. За допомогою пів-обертового методу підтверджується гіпотеза «Кожне си-метричне дерево допускає Т-факторизацію» для дерева порядку n=13, n=17. За результатами досліджень складено таблицю. Исследуется вопрос о существовании T-факторизаци полного графа Кn нечетного порядка n = 2k + 1. С помощью полуоборотного метода подтверждается гипотеза «Каждое симметрическое дерево нечетного порядка допускает T-факторизацию» для деревьев порядка n = 13, n = 15, n = 17. По результатам исследований составлена таблица. In this paper we explore the problem of the existence of T-factorization of complete graph Кn of odd order n = 2k + 1. The research in this direction is confirm the hypothesis «For each symmetrical tree of odd order T-factorization is possible» for tress of order n = 13, n = 15, n = 17 with the help of a half-turned method. The results of studies are presented in the form of table. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Існування Т-факторизації непарного порядку для симетричних дерев Существование T-факторизации нечетного порядка для симметрических деревьев The existence of t-factorization of odd order for symmetrical trees Article published earlier |
| spellingShingle | Існування Т-факторизації непарного порядку для симетричних дерев Мироненко, О.В. |
| title | Існування Т-факторизації непарного порядку для симетричних дерев |
| title_alt | Существование T-факторизации нечетного порядка для симметрических деревьев The existence of t-factorization of odd order for symmetrical trees |
| title_full | Існування Т-факторизації непарного порядку для симетричних дерев |
| title_fullStr | Існування Т-факторизації непарного порядку для симетричних дерев |
| title_full_unstemmed | Існування Т-факторизації непарного порядку для симетричних дерев |
| title_short | Існування Т-факторизації непарного порядку для симетричних дерев |
| title_sort | існування т-факторизації непарного порядку для симетричних дерев |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46641 |
| work_keys_str_mv | AT mironenkoov ísnuvannâtfaktorizacííneparnogoporâdkudlâsimetričnihderev AT mironenkoov suŝestvovanietfaktorizaciinečetnogoporâdkadlâsimmetričeskihderevʹev AT mironenkoov theexistenceoftfactorizationofoddorderforsymmetricaltrees |