Існування кубічних розкладів графа K₁₃
The problem of decomposition complete graphs on set of regular subgraphs, in particular, on cubic is solved. With the help of computer calculations number of types of such decomposition complete graphs with 13, 16 and 19 tops for the first time is found. The structure of different types of decomposi...
Gespeichert in:
| Datum: | 2006 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84955 |
| 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: | Існування кубічних розкладів графа K₁₃ / Д.А. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 62-67. — Бібліогр.: 3 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84955 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-849552025-02-09T22:36:30Z Існування кубічних розкладів графа K₁₃ Existence of cubic decomposition the complete graphs K₁₃ Петренюк, Д.А. The problem of decomposition complete graphs on set of regular subgraphs, in particular, on cubic is solved. With the help of computer calculations number of types of such decomposition complete graphs with 13, 16 and 19 tops for the first time is found. The structure of different types of decomposition the complete graphs with 13 tops is completely investigated. 2006 Article Існування кубічних розкладів графа K₁₃ / Д.А. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 62-67. — Бібліогр.: 3 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84955 519.1 uk Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
The problem of decomposition complete graphs on set of regular subgraphs, in particular, on cubic is solved. With the help of computer calculations number of types of such decomposition complete graphs with 13, 16 and 19 tops for the first time is found. The structure of different types of decomposition the complete graphs with 13 tops is completely investigated. |
| format |
Article |
| author |
Петренюк, Д.А. |
| spellingShingle |
Петренюк, Д.А. Існування кубічних розкладів графа K₁₃ Теорія оптимальних рішень |
| author_facet |
Петренюк, Д.А. |
| author_sort |
Петренюк, Д.А. |
| title |
Існування кубічних розкладів графа K₁₃ |
| title_short |
Існування кубічних розкладів графа K₁₃ |
| title_full |
Існування кубічних розкладів графа K₁₃ |
| title_fullStr |
Існування кубічних розкладів графа K₁₃ |
| title_full_unstemmed |
Існування кубічних розкладів графа K₁₃ |
| title_sort |
існування кубічних розкладів графа k₁₃ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2006 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84955 |
| citation_txt |
Існування кубічних розкладів графа K₁₃ / Д.А. Петренюк // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 62-67. — Бібліогр.: 3 назв. — укр. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT petrenûkda ísnuvannâkubíčnihrozkladívgrafak13 AT petrenûkda existenceofcubicdecompositionthecompletegraphsk13 |
| first_indexed |
2025-12-01T11:20:57Z |
| last_indexed |
2025-12-01T11:20:57Z |
| _version_ |
1850304691780452352 |
| fulltext |
Теорія оптимальних рішень. 2006, № 5 62
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Розв’язується задача розкладу
повних графів на множину регу-
лярних під графів, зокрема на
кубічні. За допомогою комп’ю-
терних обчислень уперше знайде-
но кількість типів такого розкла-
ду повних графів з 13, 16 та 19
вершинами. Повністю досліджена
структура різних типів розкладів
повного графа з 13 вершинами.
Д.А. Петренюк, 2006
ÓÄÊ 519.1
Ä.À. ÏÅÒÐÅÍÞÊ
²ÑÍÓÂÀÍÍß ÊÓÁ²×ÍÈÕ ÐÎÇÊËÀIJÂ
ÃÐÀÔÀ K13
Регулярним графом степеня k називають
граф, у якого степені всіх вершин
дорівнюють k. Регулярний граф степеня k=3
називають кубічним графом. Розкладом за-
даного графа H на підграфи з множини
G={g1, g2, …, gn} називають розбиття мно-
жини ребер цього графа на підграфи (компо-
ненти розкладу), кожен з яких ізоморфний
деякому графу з множини G.
Розглянемо умови існування розкладів
графа Kn на регулярні компоненти степеня
k>2. Відомо, що необхідна умова існування
розкладів графа Kn на компоненти, кожна з
яких – регулярний граф степеня k > 2, має
вигляд
)(mod1 kn ≡ . (1)
Кількість ребер регулярного графа поряд-
ку m степеня k дорівнює
2
km
. Кількість ре-
бер графа Kn визначається виразом
2
)1( −nn
.
Типом розкладу називатимемо вектор
a={a4,a5,a6,...,an}, де ai – кількість компонент
порядку i у розкладі. Тоді повинна виконува-
тися рівність
2
)1(
2
−
=∑
nn
a
ki
i . (2)
У випадку k = 3 маємо розклад графа Kn на
кубічні компоненти. Такий розклад назива-
ють кубічним.
ІСНУВАННЯ КУБІЧНИХ РОЗКЛАДІВ ГРАФА K13
Теорія оптимальних рішень. 2006, № 5 63
Умова (2) для кубічного розкладу матиме вигляд
2
)1(
2
3 −
=∑
nn
a
i
i . (3)
Відомо, що кубічний граф порядку i існує лише у випадку, коли i – парне чи-
сло, i ≥ 4. Тоді рівняння (3) можна записати так:
6
)1(
2
...432 864
−
=++++
nn
a
n
aaa n . (4)
При n = 4 існує лише од ин розклад графа Kn на кубічні графи. Наступне n,
що відповідає умові (1), – n = 7. Єдиний можливий тип кубічного розкладу гра-
фа K7 – це a = {2, 1} (рис.1). Компоненти єдиної (з точністю до ізоморфізму)
реалізації цього типу показано на рис. 1, і цим задача повністю розв’язана.
РИС. 1. Компоненти кубічного розкладу графа К7
Вивчення випадку n = 10 започатковано в [1], де опубліковано перелік типів
кубічних розкладів графа K10.
Шляхом комп’ютерного перебору автором отримано можливі типи кубіч-
них розкладів графів K13, K16 та K19. Для n = 13 існує 97 можливих типів, для n =
16 їх кількість становить 1161, для n = 19 – 9670. Перелік можливих типів для n
= 13 опубліковано в [2].
Д.А. ПЕТРЕНЮК
Теорія оптимальних рішень. 2006, № 5 64
РИС. 2. Розклад графа К13 типу {0, 2, 2, 0, 2}
В даній роботі вивчається питання існування кубічних розкладів графа K13
для кожного зі згаданих типів. На початку було перевірено існування лише та-
ких розкладів, для яких виконується умова: будь-які дві компоненти одного й
того ж порядку ізоморфні. За допомогою комп’ютера отримано кубічні розкла-
ди з вказаною властивістю для 50 типів з 97 можливих. Для цього використано
переліки кубічних графів порядків 8, 10, 12, наведені в [3]. Після цього для реш-
ти 47 типів проведено пошук реалізацій, у яких компоненти однакових порядків
не обов’язково ізоморфні. Такі реалізації знайдено для 19 типів. Розв’язок задачі
знайдено шляхом повного перебору, отже 28 типів, для яких не знайдено розк-
ладів, не реалізуються взагалі.
Існування чи відсутність розкладів відображено в таблиці. У ній зірочкою
позначено типи, для яких знайдено лише реалізації, компоненти одного порядку
не обов’язково ізоморфні.
Приклади розкладів подано на рис. 2 та 3. На рис.2 показано розклад типу
{0, 2, 2, 0, 2}
1-2 1-3 1-4 2-3 2-4 3-5 4-6 5-7 5-8 6-9 6-10 7-8 7-11 8-11 9-10 9-12 10-12 11-12;
ІСНУВАННЯ КУБІЧНИХ РОЗКЛАДІВ ГРАФА K13
Теорія оптимальних рішень. 2006, № 5 65
1-5 1-6 1-9 5-6 5-9 6-2 9-3 2-7 2-10 3-4 3-8 7-10 7-13 10-13 4-8 4-12 8-12 13-12;
1-7 1-12 1-8 7-12 7-6 12-2 8-6 8-9 6-11 2-9 2-11 9-11;
1-10 1-11 1-13 10-11 10-3 11-4 13-3 13-9 3-7 4-9 4-7 9-7;
2-8 2-13 2-5 8-13 8-10 13-4 5-4 5-10 4-10;
3-6 3-12 3-11 6-12 6-13 12-5 11-5 11-13 5-13,
у якому компоненти однакових порядків ізоморфні .
На рис.3 показано розклад типу {3,0,1,2,1}
1-2 1-3 1-4 2-3 2-4 3-5 4-5 5-6 6-7 6-8 7-9 7-10 8-9 8-11 9-12 10-11 10-12 11-12;
1-5 1-7 1-8 5-7 5-8 7-2 8-10 2-10 2-6 10-3 6-4 6-9 3-4 3-9 4-9;
1-6 1-10 1-9 6-10 6-11 10-4 9-11 9-2 11-5 4-8 4-12 2-5 2-8 5-12 8-12;
3-7 3-8 3-11 7-8 7-12 8-13 11-1 11-2 12-1 12-2 13-1 13-2;
3-6 3-12 3-13 6-12 6-13 12-13;
4-7 4-11 4-13 7-11 7-13 11-13;
5-9 5-10 5-13 9-10 9-13 10-13.
Тут умова ізоморфності компонент однакових порядків не виконується.
РИС. 3. Компоненти розкладу типу {3,0,1,2,1}
Д.А. ПЕТРЕНЮК
Теорія оптимальних рішень. 2006, № 5 66
ТАБЛИЦЯ
Но-
мер
ти-
пу
Тип роз-
кладу
Існу-
вання
Но-
мер
ти-
пу
Тип
розкладу
Існу-
вання
Но-
мер
ти-
пу
Тип
розкладу
Існу-
вання
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
*18
19
*20
21
22
23
*24
25
26
27
*28
29
30
31
32
33
0 0 0 4 1
0 0 1 2 2
0 0 2 0 3
0 0 4 2 0
0 0 5 0 1
0 1 0 1 3
0 1 2 3 0
0 1 3 1 1
0 2 0 4 0
0 2 1 2 1
0 2 2 0 2
0 2 5 0 0
0 3 0 1 2
0 3 3 1 0
0 4 1 2 0
0 4 2 0 1
0 5 0 1 1
0 6 2 0 0
0 7 0 1 0
1 0 0 0 4
1 0 1 4 0
1 0 2 2 1
1 0 3 0 2
1 0 6 0 0
1 1 0 3 1
1 1 1 1 2
1 1 4 1 0
1 2 0 0 3
1 2 2 2 0
1 2 3 0 1
1 3 0 3 0
1 3 1 1 1
1 4 0 0 2
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
34
35
36
37
38
*39
40
41
42
43
44
*45
*46
47
48
49
*50
*51
*52
*53
*54
55
*56
57
58
59
*60
*61
62
*63
64
*65
66
1 4 3 0 0
1 5 1 1 0
1 6 0 0 1
1 8 0 0 0
2 0 0 2 2
2 0 1 0 3
2 0 3 2 0
2 0 4 0 1
2 1 1 3 0
2 1 2 1 1
2 2 0 2 1
2 2 1 0 2
2 2 4 0 0
2 3 2 1 0
2 4 0 2 0
2 4 1 0 1
2 6 1 0 0
3 0 0 4 0
3 0 1 2 1
3 0 2 0 2
3 0 5 0 0
3 1 0 1 2
3 1 3 1 0
3 2 1 2 0
3 2 2 0 1
3 3 0 1 1
3 4 2 0 0
3 5 0 1 0
4 0 0 0 3
4 0 2 2 0
4 0 3 0 1
4 1 0 3 0
4 1 1 1 1
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
–
+
+
+
+
+
+
–
+
+
+
+
67
*68
69
*70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
4 2 0 0 2
4 2 3 0 0
4 3 1 1 0
4 4 0 0 1
4 6 0 0 0
5 0 0 2 1
5 0 1 0 2
5 0 4 0 0
5 1 2 1 0
5 2 0 2 0
5 2 1 0 1
5 4 1 0 0
6 0 1 2 0
6 0 2 0 1
6 1 0 1 1
6 2 2 0 0
6 3 0 1 0
7 0 0 0 2
7 0 3 0 0
7 1 1 1 0
7 2 0 0 1
7 4 0 0 0
8 0 0 2 0
8 0 1 0 1
8 2 1 0 0
9 0 2 0 0
9 1 0 1 0
10 0 0 0 1
10 2 0 0 0
11 0 1 0 0
13 0 0 0 0
–
+
+
+
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
+
–
–
–
–
+
ІСНУВАННЯ КУБІЧНИХ РОЗКЛАДІВ ГРАФА K13
Теорія оптимальних рішень. 2006, № 5 67
Д.А. Петренюк
СУЩЕСТВОВАНИЕ КУБИЧЕСКИХ РАЗЛОЖЕНИЙ ПОЛНОГО ГРАФА K13
Решается задача разложения полных графов на множество регулярных подграфов, в частнос-
ти, на кубические. С помощью компьютерных вычислений впервые найдено количество ти-
пов такого разложения полных графов с 13, 16 и 19 вершинами. Полностью исследована
структура разных типов разложений полного графа с 13 вершинами.
D.A. Petrehyuk
EXISTENCE OF CUBIC DECOMPOSITION THE COMPLETE GRAPHS K13
The problem of decomposition complete graphs on set of regular subgraphs, in particular, on cubic
is solved. With the help of computer calculations number of types of such decomposition complete
graphs with 13, 16 and 19 tops for the first time is found. The structure of different types of decom-
position the complete graphs with 13 tops is completely investigated.
1. Петренюк А.Я. Про перелік кубічних розкладів повного графа K(10) // Зб. доп. п’ятої
міжнар. наук. конф. ім. акад. М. Кравчука (16–18 травня 1996 р., Київ). – Київ, 1996.
– С. 332 – 339.
2. Петренюк Д.А. Перелік можливих типів кубічних розкладів графа К13 // Зб. доп.
третьої міжнар. наук.-практ. конф. “Математичне та програмне забезпечення
інтелектуальних систем (MPZIS-2005)” (16–18 листопада 2005 р., Дніпропетровськ).
– Дніпропетровськ, 1995. – С. 137 – 141.
3. Бараев А.М., Фараджев И.А. Построение и исследование на ЭВМ однородных и од-
нородных двудольных графов // Алгоритмические исследования в комбинаторике.–
М.: ВЦ АН СССР, 1978. – С. 47 – 53.
Отримано 29.06.2006
|