Разноразмерные древесные разложения полных графов
In this paper we explore the problem on decomposition of complete graphs into trees with various amounts of chain-, star-, comet-, and double-star-like vertices. The results of stadies are presented in the form of tables.
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2004 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2004
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84875 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Разноразмерные древесные разложения полных графов / О.В. Мироненко // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 41-47. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859619947388338176 |
|---|---|
| author | Мироненко, О.В. |
| author_facet | Мироненко, О.В. |
| citation_txt | Разноразмерные древесные разложения полных графов / О.В. Мироненко // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 41-47. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | In this paper we explore the problem on decomposition of complete graphs into trees with various amounts of chain-, star-, comet-, and double-star-like vertices. The results of stadies are presented in the form of tables.
|
| first_indexed | 2025-11-29T03:11:49Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2004, № 3 41
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Исследуется задача разложения
полных графов на деревья с раз-
личным количеством вершин типа
цепей, звезд, комет и двойных
звезд. Результаты приводятся в
виде таблиц.
О.В. Мироненко, 2004
ÓÄÊ 519.1
Î.Â. ÌÈÐÎÍÅÍÊÎ
ÐÀÇÍÎÐÀÇÌÅÐÍÛÅ ÄÐÅÂÅÑÍÛÅ
ÐÀÇËÎÆÅÍÈß ÏÎËÍÛÕ ÃÐÀÔÎÂ
Введение. В работах [1–10] исследуются
разложения полных графов на подграфы
разных типов, в частности на деревья. Инте-
ресными и содержательными оказались за-
дачи о существовании упомянутых разложе-
ний и их перечислении с точностью до изо-
морфизма.
В этой работе рассматриваются вопросы
перечисления разноразмерных древесных
разложений полных графов.
Пусть T1, T2, …, Tn–1 (n ≥ 2) – последова-
тельность деревьев, такая, что дерево Ti име-
ет число вершин i (i = 1, …, n –1). Семейство
подграфов {g1, g2, …, gn –1} полного графа Kn
называют (T1, T2, …, Tn –1)-разложением
графа Kn в том случае, если (1) любой под-
граф gi (i=1, …, n–1) представляет собой де-
рево, изоморфное Ti ; (2) деревья gi и gj не
имеют общих ребер при i ≠ j (1 ≤ i, j ≤ n–1);
(3) g1 ∪ g2 ∪ … ∪ gn–1 = Kn.
Вышеописанную последовательность T1,
T2, …, Tn–1 будем называть заголовком соот-
ветствующих (T1, T2, …, Tn–1)-разложений.
Деревья g1, g2, …, gn–1 называют компонен-
тами (T1, T2, …, Tn–1)-разложения, при этом
компоненту gn–1 называют старшей.
Гьярфас и Легель [1] сформулировали сле-
дующую гипотезу: для всякого заголовка T1,
T2, …, Tn–1 существует (T1, T2, …, Tn–1)-разло-
жение. Они доказали, что эта гипотеза верна
для заголовков, в которых только два дерева
не звезды. В попытках доказать эту гипотезу
появились новые задачи существования раз-
ложений рассматриваемых видов [2, 3].
О.В. МИРОНЕНКО
42 Теорія оптимальних рішень. 2004, № 3
Хобс, Бурже и Касирай [4] высказали и частично доказали другую гипотезу:
(T1, T2, …, Tn–1)-разложение полного двудольного графа
−
2
,1
n
n
K существует для
всех возможных заголовков.
Автора заинтересовала задача о перечислении, с точностью до изоморфиз-
ма, (T1, T2, …, Tn–1)-разложений; в данной работе эта задача решена для опреде-
ленных заголовков малых порядков n.
Первоначальная классификация разноразмерных древесных разложе-
ний. Для удобства мы разделяем множество всех (T1, T2,…, Tn–1)-разложений на
четыре типа в соответствии с типами взаиморасположения компонент g1 и g2,
которые определяются классами изоморфизма графов взаиморасположения
g1 ∪ g2, изображенных на рис.1.
Тип 1 Тип 2 Тип 3 Тип 4
РИС.1. Четыре типа (T1, T2, …, Tn–1) – разложений
Разноразмерные звездные древесные разложения. Рассмотрим задачу
перечисления в случае, если Ti = Zi (i = 1,2,…), где Zi – звезда с i ребрами. Сле-
дующая теорема решает указанную задачу при всех значениях n.
Звезду Zі будем изображать в виде (a)a1a2...aі , где a - центральная вершина
звезды, а a1, a2, ..., aі – ее концевые вершины.
Теорема 1. С точностью до изоморфизма, существует единственное (Z1, Z2,
..., Zn–1}-разложение графа Kn для любого n ≥ 2. Группа автоморфизмов этого
разложения имеет порядок 2.
Доказательство. Существование докажем рекурсивным построением. Для
n = 2 справедливость утверждения очевидна. Предположим, что оно справедли-
во для порядка n – 1. Тогда существует разноразмерное звездное разложение
графа Kn-1, построенного на множестве вершин {1, ..., n-1}.
Рассмотрим граф Kn с множеством вершин {1, 2, ..., n}. Пусть R – разнораз-
мерное звездное разложение графа Kn-1= Kn\{n}. Прибавив к звездам разложения
R звезду Zn = (n)12...n-1, получим искомое разноразмерное звездное разложение
графа Kn, этим существование доказано.
Единственность. Применим метод математической индукции. В случае
n = 2 единственность очевидна. Пусть n > 2. Предположим, что единственность
РАЗНОРАЗМЕРНЫЕ ДРЕВЕСНЫЕ РАЗЛОЖЕНИЯ ПОЛНЫХ ГРАФОВ
Теорія оптимальних рішень. 2004, № 3 43
имеет место для всех порядков, меньших, чем n. Пусть, вопреки утверждению
теоремы, для графа Kn с множеством вершин {1, ..., n} существуют два неизо-
морфные разноразмерные звездные разложения R1, R2. Если нужно, перенумеру-
ем вершины основных графов этих разложений так, чтобы центры старших
компонент совместились с вершиной n.
Изъяв из обоих разложений вершину n и старшие компоненты, получим
разноразмерные звездные разложения (обозначим их Ř1, Ř2) графа Kn–1. По
предположению индукции, эти разложения изоморфны. Итак, существует такая
подстановка ϕ, которая переводит Ř1 в Ř2 . Но тогда подстановка вершин графа
Kn, которая действует на вершинах его подграфа Kn-1 как ϕ и оставляет на месте
вершину n, переводит R1 в R2, а это противоречит предположению, что R1 и R2 не
изоморфны. Установленное противоречие доказывает единственность разнораз-
мерного звездного разложения графа Kn для каждого значения n ≥ 2.
Относительно группы автоморфизмов вышепостроенного разложения заме-
тим, что под действием произвольного автоморфизма центр любой его звезды,
кроме звезды Z1, остается на месте. Поэтому автоморфизмом может быть лишь
подстановка α = (1, 2). И она действительно является автоморфизмом этого раз-
ложения, так как вершины 1, 2 – концевые вершины всех его звезд, (поскольку в
Z1 центром можно считать любую из двух ее вершин, то в ней центр не указыва-
ем). Теорема доказана.
Разноразмерные цепные разложения. Цепью длины n – 1 называют граф
Pn–1 порядка n, у которого ровно две вершины имеют степень 1, а все остальные
имеют степень 2. На рис. 2 изображено несколько цепей малых длин.
P1 P2 P3 P4 P5 P6
РИС. 2. Малые цепи
Цепь Pk будем изображать в виде последовательности a1a2…ak, где aj – вер-
шины, а (a1,a2), (a2, a3),…, (ak–1, ak) – ребра цепи. Цепь a1a2…ak называем стан-
дартной, если a1 < ak.
(P1, P2, …, Pn–1)-разложения графа Kn будем называть разноразмерными
цепными разложениями. Для этих разложений задача перечисления с точностью
О.В. МИРОНЕНКО
44 Теорія оптимальних рішень. 2004, № 3
до изоморфизма не имеет такого красивого, лаконичного и универсального ре-
шения, как для разноразмерных звездных разложений.
Мы составили компьютерную программу, которая строит список неизо-
морфных разноразмерных цепных разложений порядка 7, и с ее помощью полу-
чили количественные результаты перечисления этих разложений, которые пред-
ставлены в табл. 1.
ТАБЛИЦА 1. Результаты перечисления разноразмерных цепных разложений
графа K7
Типы разложений 1 2 3 4 Всего
Количество разложений 42401 56412 24462 6732 130007
Из них симметричных 20 0 0 10 30
Очевидно, что группа автоморфизмов цепного разложения графа Kn являет-
ся подгруппой группы автоморфизмов старшей компоненты этого разложения,
т.е. , эта группа или тривиальная, или же вмещает единственную нетривиальную
подстановку α = (a1, an) (a2, an–1)…( 1
22
,
+− nnn aa ).
Разноразмерные цепные разложения, которые имеют нетривиальный авто-
морфизм, будем называть симметричными. Как видно выше из табл. 1, сущест-
вует точно 30 симметричных разложений порядка 7.
Список всех 130007 разноразмерных цепных разложений порядка 7 в дан-
ной работе не помещается. Мы помещаем все симметричные разложения поряд-
ка 7. В изображениях этих разложений пропущена общая им всем старшая ком-
понента 1234567.
Список симметричных разложений порядка 7
Тип 1
1. 136257 16427 3715 147 35 2. 136257 27416 1537 246 17
3. 136257 27416 3715 246 35 4. 136257 37415 2716 246 35
5. 152637 16427 3175 147 35 6. 152637 27416 1357 246 17
7. 152637 27416 3175 246 35 8. 152637 31457 2716 246 35
9. 251736 16427 1357 147 26 10. 251736 31475 1627 246 35
11. 257136 16427 1537 147 26 12. 257136 37415 1627 246 35
13. 273516 31475 3625 246 17 14. 273516 36425 3175 147 26
15. 275316 36425 3715 147 26 16. 275316 37415 3625 246 17
17. 316275 36425 3715 147 35 18. 316275 37415 2536 246 17
19. 372615 31475 2536 246 17 20. 372615 36425 3175 147 35
Тип 4
21. 136257 16427 1537 147 17 22. 152637 16427 1357 147 17
23. 163527 31475 3715 246 26 24. 163527 37415 3175 246 26
25. 251736 27416 1357 246 26 26. 257136 27416 1537 246 26
27. 316275 36425 1537 147 17 28. 361725 31475 1537 246 26
РАЗНОРАЗМЕРНЫЕ ДРЕВЕСНЫЕ РАЗЛОЖЕНИЯ ПОЛНЫХ ГРАФОВ
Теорія оптимальних рішень. 2004, № 3 45
29. 361725 37415 1357 246 26 30. 372615 36425 1357 147 17
Заметим, что в состав симметричных разложений со старшей компонентой
12...n входят только такие компоненты a1a2.. ak, в которых ai + ak–i+1 = n + 1
(i = 1, 2, ...,
2
k
); цепи с таким свойством естественно можно назвать симмет-
ричными. Отсутствие симметричных разложений типов 2 и 3 порядка 7 – не
случайное явление. Следующее утверждение обобщает этот факт.
Теорема 2. Симметричные разложения порядка n типов 2 и 3 не существу-
ют при всех значениях n.
Доказательство. Если бы существовало симметричное разложение графа
Kn типа 2, то подстановка α = (1, n) (2, n–1)… должна переводить рис.1 для типа
2 в этот же рисунок. Но это невозможно, так как тогда в общую вершину двух
компонент перешли бы две вершины – противоположные концы двух наимень-
ших компонент (компоненты под действием α неподвижными оставаться не мо-
гут). Из тех же соображений рис. 2, тип 3 не может переходить сам в себя под
действием этой подстановки. Теорема доказана.
Заметим, что группа автоморфизмов любого (T1, T2, …, Tn–1)-разложения
R = {g1, g2, …, gn–1} имеет вид Aut (R) = Aut (g1) ∩ Aut (g2) ∩ … ∩ Aut (gn–1).
Учитывая это, не следует ждать мощных групп автоморфизмов у рассмат-
риваемых разложений.
Разноразмерные кометные разложения. Вообще , (k, s)-кометой называют
дерево, которое состоит из звезды Zk и цепи Ps, единственная общая вершина
которых является концевой вершиной в каждом из этих графов. В частном слу-
чае (k, 0)-комета представляет собой звезду Zk , (1, s)-комета – цепь Ps+1.
В дальнейшем будем понимать под кометой Comk (k, 1)-комету. Кометы
малых размеров изображены на рис. 3.
Com0 Com1 Com2 Com3 Com4 Com5
РИС. 3. Малые кометы
С помощью программы, аналогичной вышеиспользованной для перечисле-
ния цепных разложений, мы получили количественные результаты перечисле-
ния (Com0, Com1, …, Comn–2)-разложений, представленные в табл. 2.
О.В. МИРОНЕНКО
46 Теорія оптимальних рішень. 2004, № 3
ТАБЛИЦА 2. Результаты перечисления кометных разложений графа K7
Типы разложений 1 2 3 4 Всего
Количество разложений 879 1276 894 252 3361
Заметим, что все кометные разложения порядка 7 имеют тривиальные груп-
пы автоморфизмов.
Разноразмерные разложения на двойные звезды. Двойной звездой DS2k+2
(k = 0,1,2, …) называют дерево порядка 2k+2, в котором все вершины концевые,
кроме двух смежных вершин, степени которых равны k. В случае нечетного по-
рядка будем называть двойной звездой DS2k+1 (k = 1,2, …) дерево порядка 2k + 1,
все вершины которого концевые, кроме двух смежных вершин, степени которых
равны k и k–1. На рис. 4. изображены двойные звезды порядков, которые не пре-
вышают 7.
DS1 DS2 DS3 DS4 DS5 DS6 DS7
РИС. 4. Малые двойные звезды
Полученные в этом случае компьютерные количественные результаты пе-
речисления (DS1, DS2, DS3, DS4, DS5, DS6, DS7) – разложений приведены в табл. 3.
ТАБЛИЦА 3. Результаты перечисления разноразмерных разложений графа K7 на
двойные звезды
Типы разложений 1 2 3 4 Всего
Количество разложений 1211 1582 610 0 3403
Сокращенное изложение части приведенных результатов представлено в те-
зисах [11].
РАЗНОРАЗМЕРНЫЕ ДРЕВЕСНЫЕ РАЗЛОЖЕНИЯ ПОЛНЫХ ГРАФОВ
Теорія оптимальних рішень. 2004, № 3 47
О.В. Мироненко
РІЗНОРОЗМІРНІ ДЕРЕВНІ РОЗКЛАДИ ПОВНИХ ГРАФІВ
Досліджується задача розкладу повних графів на дерева з різною кількістю вершин типу лан-
цюгів, зірок, комет та подвійних зірок. Отримані результати наводяться у вигляді таблиць.
O.V. Mironenko
DECOMPOSITION OF COMPLETE GRAPHS INTO TREES OF VARIOUS DIMENTION
In this paper we explore the problem on decomposition of complete graphs into trees with various
amounts of chain-, star-, comet-, and double-star-like vertices. The results of stadies are presented in
the form of tables.
1. Gyarfas A., Lehel J. Packіng trees of dіfferent order іnto Kn, Combіnatorіcs (Proc. Fіfth
Hungar. Colloq. Keszthely 1976) Colloq. Math. Soc. Janos Bolyaі 18, North. – Holland,
New York. – 1976. – P.75 – 82.
2. Fіshburn P.G. Packіng graphs wіth odd and even trees, J. Graphs Theory. – 1983. – №7. –
P. 369 – 383.
3. Balakrіshnan R., Paulraja P., Basha A. Rahіm Packіng half – complete graphs wіth trees,
Utіlіtas Mathematіca. – 1987. – 31. – P. 131–148.
4. Hobbs A.V., Bourgeoіs B.A., Kasіraj J. Packіng trees іn complete graphs, Dіscrete Math. –
1987, – 67. – P. 27–42.
5. Huang C., Rosa A. Decomposіtіon of complete graphs іnto trees, ARS Combіnatorіa. –
1978. – 5. – P. 23–63.
6. Petrenjuk A.J. Enumeratіon of mіnіmal tree decomposіtіons of complete graphs, JCMCC.
– 1992. – 12. – P. 197–199.
7. Petrenjuk A. J. On tree factorіzatіons of K10., J. of Combіn. Math. and Combіn. Computіng (іn
prіnt).
8. Донец A.Г., Петренюк A. Я. О перечислении разнокомпонентных древесных разло-
жений // Теория оптимальных решений. – Киев: Ин–т кибернетики им. В.М. Глу-
шкова НАН Украины, 2000. – С. 70–75.
9. Петренюк А. Я. Древесные факторизации полных графов: существование, постро-
ение, перечисление // Мат. 7 Междунар. семинара "Дискретная математика и ее
приложения". – М. – 2001. – С. 26–30.
10. Петренюк А. Я. Півобертові деревні факторизації повних графів // Укр. матем.
журнал. – 2001. – 53, №5. – С. 710–716.
11. Мироненко О.В. Різнорозмірні деревні розклади повних графів // Матеріали ІІ
Міжнар. наук. – практичної конф. “Динаміка наукових досліджень,2003”, (Дніпро-
петровськ–Кіровоград–Одеса, 20–27 жовтня 2003). – Дніпропетровськ: Математи-
ка, 2003. – т. 32. – С. 27–30.
Получено 10.06.2004
|
| id | nasplib_isofts_kiev_ua-123456789-84875 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-11-29T03:11:49Z |
| publishDate | 2004 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Мироненко, О.В. 2015-07-16T17:42:41Z 2015-07-16T17:42:41Z 2004 Разноразмерные древесные разложения полных графов / О.В. Мироненко // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 41-47. — Бібліогр.: 11 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84875 519.1 In this paper we explore the problem on decomposition of complete graphs into trees with various amounts of chain-, star-, comet-, and double-star-like vertices. The results of stadies are presented in the form of tables. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Разноразмерные древесные разложения полных графов Decomposition of complete graphs into trees of various dimention Article published earlier |
| spellingShingle | Разноразмерные древесные разложения полных графов Мироненко, О.В. |
| title | Разноразмерные древесные разложения полных графов |
| title_alt | Decomposition of complete graphs into trees of various dimention |
| title_full | Разноразмерные древесные разложения полных графов |
| title_fullStr | Разноразмерные древесные разложения полных графов |
| title_full_unstemmed | Разноразмерные древесные разложения полных графов |
| title_short | Разноразмерные древесные разложения полных графов |
| title_sort | разноразмерные древесные разложения полных графов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84875 |
| work_keys_str_mv | AT mironenkoov raznorazmernyedrevesnyerazloženiâpolnyhgrafov AT mironenkoov decompositionofcompletegraphsintotreesofvariousdimention |