Граціозні дерева. Аналіз проблеми та перспективи

Запропоновано аналіз результатів щодо гіпотези про граціозність дерев. Розглянуто два підходи до питання правдивості гіпотези про дані дерева, описано основні класи таких дерев, способи отримання більших дерев з менших, а також результати комп’ютерних обчислень стосовно граціозності дерев. Подано де...

Full description

Saved in:

Bibliographic Details
Published in:	Управляющие системы и машины
Date:	2016
Main Author:	Петренюк, Д.А.
Format:	Article
Language:	Ukrainian
Published:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Subjects:	Фундаментальные и прикладные проблемы Computer Science
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/112893
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:	Граціозні дерева. Аналіз проблеми та перспективи / Д.А. Петренюк // Управляющие системы и машины. — 2016. — № 1. — С. 16–25, 33. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859659864551194624
author	Петренюк, Д.А.
author_facet	Петренюк, Д.А.
citation_txt	Граціозні дерева. Аналіз проблеми та перспективи / Д.А. Петренюк // Управляющие системы и машины. — 2016. — № 1. — С. 16–25, 33. — укр.
collection	DSpace DC
container_title	Управляющие системы и машины
description	Запропоновано аналіз результатів щодо гіпотези про граціозність дерев. Розглянуто два підходи до питання правдивості гіпотези про дані дерева, описано основні класи таких дерев, способи отримання більших дерев з менших, а також результати комп’ютерних обчислень стосовно граціозності дерев. Подано деякі аргументи проти гіпотези про граціозність дерев. Предложен анализ результатов относительно гипотезы о грациозности деревьев. Рассмотрены два подхода к вопросу истинности гипотезы о данных деревьях, основные классы грациозных деревьев, способы получения больших деревьев из меньших, а также результаты компьютерных вычислений о грациозности деревьев. Приведены некоторые аргументы против гипотезы о грациозности деревьев. Graceful Tree Conjecture is one of the most popular math conjectures. It was formulated almost half a century ago, but even today it is still far from being completely solved. A. Krishnaa in 2004 and J. Gilbert in 2009 [19] proposed their proofs of the Conjecture, but they turned out to be wrong or incomplete. The article contains a brief review of the state of art in solving the Conjecture, including some results that have been proposed by the author. Graceful labeling of undirected graph G with n edges is an injection from vertex set of graph G to {0, 1, 2, ..., n} such that all the induced edge labels are different. Induced edge label is the absolute value of the difference between the labels (numbers) of the two end-vertices of the edge. A graph is graceful if it admits graceful labeling. The Graceful Tree Conjecture claims that all trees are graceful. There are two approaches to solving the Graceful Tree Conjecture. The first is to prove gracefulness and obtain graceful labeling algorithms for certain classes of trees; if once gracefulness of all classes of trees is shown, then the Conjecture is proved. For today, gracefulness is proved for stars, paths, caterpillars, olive trees, some subclasses of lobsters (firecrackers, (2,2)-caterpillars, lobsters with perfect matchings), banana and generalized banana trees, and some other classes. Many methods of combining few graceful trees to obtain a new bigger graceful tree have been found. Another approach to solving the conjecture is to use computer to check if all trees with number of vertices not exceeding a given value are graceful. This approach can provide new graceful labeling algorithms and can be also used to disprove the Conjecture, once at least one tree that does not admit graceful labeling is found. However, no such tree has been found so far. It has been proved that all the trees having not more than 35 vertices are graceful. Despite all the positive results, some researchers express serious doubts about the truthfulness of the Conjecture. They point out that the most graceful labeling methods have been designed for trees with regular or very simple structure, while there are no proofs of gracefulness for sufficiently irregular trees. However, the majority or researchers tend to believe that the Graceful Tree Conjecture is true and will be once proved completely.
first_indexed	2025-11-30T09:29:07Z
format	Article
fulltext	16 УСиМ, 2016, № 1 УДК 519.17 Д.А. Петренюк Граціозні дерева. Аналіз проблеми та перспективи Предложен анализ результатов относительно гипотезы о грациозности деревьев. Рассмотрены два подхода к вопросу истинно- сти гипотезы о данных деревьях, основные классы грациозных деревьев, способы получения больших деревьев из меньших, а также результаты компьютерных вычислений о грациозности деревьев. Приведены некоторые аргументы против гипотезы о грациозности деревьев. Запропоновано аналіз результатів щодо гіпотези про граціозність дерев. Розглянуто два підходи до питання правдивості гіпо- тези про дані дерева, описано основні класи таких дерев, способи отримання більших дерев з менших, а також результати комп’ютерних обчислень стосовно граціозності дерев. Подано деякі аргументи проти гіпотези про граціозність дерев. Вступ. Гіпотеза про граціозність дерев є одні- єю з найпопулярніших математичних гіпотез, яка уперше була сформульована в 1976 р. [1], і з того часу спроби довести або спростувати її не припиняються. Незважаючи на значний ін- терес до гіпотези за кордоном, в Україні цій темі досі приділялося небагато уваги. Запро- понована функція нумерації вершин графа отри- мала назву -оцінки [1]; пізніше таку нумера- цію назвали граціозною, і зараз цей термін вживається найбільш широко [2]. Існує два основних підходи до розв’язання проблеми істинності гіпотези про граціозність дерев. Перший з них полягає в доведенні гра- ціозності та отриманні алгоритмів граціозної нумерації для окремих класів дерев. Якби вда- лося продемонструвати граціозність усіх мож- ливих класів дерев, то гіпотезу було б доведе- но. Сьогодні граціозність доведено для зірок, ланцюгів, гусениць, оливкових дерев, деяких підкласів омарів (феєрверків, (2,2)-гусениць, омарів з досконалими паросполученнями), ба- нанових та узагальнених бананових дерев та низки інших класів дерев. Знайдено значну кі- лькість методів поєднання кількох граціозних дерев для отримання більшого граціозного де- рева. Найважливіші з цих результатів розгля- нуто в даній статті. Інший підхід до відповіді на питання про граціозність усіх дерев полягає у використанні комп’ютера для перевірки граціозності дерев, кількість вершин яких не перевищує заданої скінченної величини. Такий підхід є додатко- вим джерелом алгоритмів граціозної нумерації дерев, а також може бути використаний для спростування гіпотези, якщо буде знайдено хоча б одне дерево, яке не допускає граціозної нумерації. Досі, щоправда, такого дерева не знайдено. У 2010 р. використано детермінова- ний алгоритм пошуку з поверненням і доведе- но, що всі дерева, які мають не більше 35 вер- шин, граціозні [3]. Постановка задачі Граціозною нумерацією неорієнтованого гра- фа G з n ребрами називають взаємно однозна- чну відповідність між множиною вершин гра- фа G та множиною {0, 1, 2, ..., n}, де всі інду- ковані мітки ребер є різними. Індукована мітка ребра – це абсолютна величина різниці між номерами (мітками) двох його кінців. Іншими словами, нумерація φ граціозна, якщо φ: V  {0, 1, 2, ..., \|E\|} є ін’єктивним відображен- ням і якщо всі ребра графа G мають різні но- мери з множини {1, 2, ..., \|E\|}. В [1] також по- казано, що існування граціозної нумерації для заданого графа G з n ребрами є достатньою умовою існування циклічного розкладу повно- го графа порядку 2n + 1 на підграфи, ізоморфні графу G. Приклад такого розкладу для n = 3 показано на рис. 1. Рис. 1 Граф є граціозним, якщо він допускає граці- озну нумерацію. Знаменита гіпотеза про гра- ціозність дерев (також відома як гіпотеза Рін- геля–Коціга, або гіпотеза Роси, або навіть гіпо- УСиМ, 2016, № 1 17 теза Рінгеля–Коціга–Роси) полягає в тому, що всі дерева є граціозними. Гіпотезу про граціозність дерев досі не до- ведено, тож вона продовжує привертати увагу професійних науковців та аматорів. Сьогодні потік публікацій про граціозність дерев не вщухає, тому відслідковувати усі нові резуль- тати досить важко. Далі перераховано лише основні класи дерев, граціозність яких вже до- ведено. Класи граціозних дерев Зірка Зіркою називають дерево, яке має не більше однієї вершини, степінь якої перевищує одини- цю, а усі інші вершини мають степінь одиниця. Доведено, що усі зірки є граціозними. Граціозно занумеровану зірку зображено на рис. 2. Рис. 2 Ланцюг Ланцюгом називають дерево, в якому лише дві вершини (кінці ланцюга) мають степінь одиниця, а усі інші вершини мають степінь два. У будь-якому ланцюгу допускається граціозна нумерація. Граціозно занумеровані ланцюги показано на рис. 3. Рис. 3 Гусениця Гусеницею (або однодистантним деревом [4]) називають дерево, яке після вилучення усіх висячих вершин (тобто вершин степеня один) перетворюється на ланцюг. Усі гусениці допускають граціозну нумерацію. Граціозно роз- мічену гусеницю показано на рис. 4. Рис. 4 Оливкові дерева Оливкове дерево – це сукупність i ланцюгів, з’єднаних в одній вершині, причому довжина i-го ланцюга дорівнює i. Доведено [5], що усі оливкові дерева є граціозними. Граціозно зану- мероване оливкове дерево показано на рис. 5. Рис. 5 Граціозність деяких видів омарів Омаром (або дводистантним деревом [4]) називають дерево, яке після видалення усіх висячих вершин перетворюється на гусеницю (рис. 6). Іншими словами, це є дерево, що міс- тить ланцюг (хребет), відстань від якого до кожної вершини не перебільшує двох. Рис. 6 У 1979 р. висловлено гіпотезу про те, що всі омари граціозні [6]. Зроблено багато спроб до- вести цю гіпотезу, проте нікому досі це не вда- лося. Сьогодні відомі наступні граціозні під- класи омарів. Ф е є р в е р к и Феєрверк F – це дерево, що складається з ланцюга P(F) і множини зірок, де кожну вер- шину ланцюга P(F) з’єднано з центральною вершиною однієї зірки. Доведено, що усі феєр- верки є граціозними [7]. Граціозно занумеро- ваний феєрверк показано на рис. 6. (2, k)-г у с е н и ц і Дерево, отримане приєднанням до кожної вершини ланцюга r ланцюгів довжини k, нази- вають (r, k)-гусеницею. Простий спосіб отри- мання граціозної нумерації для окремого під- класу омарів – (2, 2)-гусениць запропоновано у [8]. Граціозно занумеровану (2, 2)-гусеницю показано на рис. 7. 18 УСиМ, 2016, № 1 Рис. 7 О м а р и з д о с к о н а л и м и п а р о - с п о л у ч е н н я м и Паросполученням у графі називають множину ребер цього графа, які не мають спільних вер- шин. Досконалим паросполученням, або 1-фак- тором в графі називають таке паросполучення, яке містить усі вершини даного графа. Доведе- но [4], що усі омари з досконалими паросполу- ченнями є граціозними. Бананові дерева та узагальнені бананові дерева Бананове дерево складається з сукупності зірок та вершини v, причому одну кінцеву ве- ршину кожної зірки з’єднано з вершиною v (рис. 8). Всі бананові дерева та узагальнені ба- нанові дерева (графи, отримані сполученням однієї вершини з однією кінцевою вершиною кожної з будь-якої кількості зірок, де сполу- чення виконується за допомогою ланцюга до- вжиною не менше двох), є граціозними [9]. Рис. 8 Сімейство граціозних павуків Павук – це дерево, у якому лише одна вер- шина має степінь більшу, за два. Якщо така вершина існує, її називають вузловою верши- ною дерева. Ногою павука називають будь- який з ланцюгів, що з’єднує вузлову вершину з кінцевою вершиною дерева. Кожне дерево-павук T з l ногами, кожна з яких має довжину з проміжку  , 1m m  для деякого  1m  , граціозне [10]. Граціозну ну- мерацію дерева-павука з сімома ногами та 18 вершинами показано на рис. 9. Рис. 9 Симетричні дерева Симетричне дерево – це кореневе дерево, у якого всі вершини, розташовані на однаковій відстані від кореня, мають однаковий степінь. Граціозність всіх симетричних дерев дове- дено у 1975 р. [11]. Симетричне дерево та його граціозну нумерацію показано на рис. 10. Рис. 10 Дерева, діаметр яких не перевищує п’яти Діаметр дерева – це довжина найдовшого маршруту в цьому дереві. Всі дерева діамет- ром п’ять – граціозні [12]. Методи отримання більших граціозних дерев з менших Приєднання гусениці до граціозно зануме- рованого дерева Якщо до вершини з номером 1 граціозно за- нумерованого дерева Gn приєднати гусінь, то отримане дерево допускатиме граціозну нуме- рацію [13]; гусениця має приєднуватися край- ньою вершиною її хребта (рис. 11). Рис. 11 УСиМ, 2016, № 1 19 Поділ ребер граціозного дерева У 1998 р. у [14] показано, що всі дерева, отримані з граціозних дерев заміною кожного ребра ланцюгом довжиною два, також є граці- озними (рис. 12). a б Рис. 12 Гірляндова побудова Гірляндовою побудовою називають отриман- ня нового дерева шляхом приєднання до кож- ної висячої вершини зірки ізоморфної копії граціозного дерева T тією вершиною, що від- повідає вершині v дерева T, яка при граціозній нумерації отримує номер 1 або n. Дерево, отримане гірляндовою побудовою, є граціозним [15]. На рис. 13 показано гірляндову побудову, за допомогою якої з трьох копій бана- нового дерева порядку 11 (див. рис. 13, а) отри- мано більше граціозне дерево порядку 34 (див. рис. 13, б). a б Рис. 13 -побудова -побудовою називають отримання нового дерева з двох граціозних дерев шляхом приєд- нання до кожної вершини одного граціозного дерева (дерева–господаря) ізоморфної копії іншого граціозного дерева T вершиною, що відповідає деякій довільно обраній фіксованій вершині v дерева T. Будь-яке дерево, отримане за допомогою - побудови, є граціозним [16]. Приклад отриман- ня граціозного дерева (б) з двох менших граці- озних дерев (а) за допомогою -побудови по- дано на рис. 14. a б Рис. 14 Побудова приєднанням Побудовою приєднанням називатимемо отри- мання нового дерева шляхом ідентифікації ко- ренів довільної кількості копій заданого граці- озного дерева в одній вершині r, яку називати- мемо особливою вершиною побудованого де- рева. Будь-яке дерево, отримане шляхом побу- дови приєднанням, є граціозним [16]. Розширені гірляндова побудова, -побу- дова та побудова приєднанням У 2008 р. у [17] розширено деякі результати [16] введенням поняття граціозно сумісних де- рев та доведенням так званої теореми підста- новок. Два граціозно занумеровані дерева T1 та T2 з V (T1) =V (T2) називатимемо граціозно су- місними, якщо виконується одна з наступних умов:  граціозно занумеровані дерева T1 та T2 є ідентичними; 20 УСиМ, 2016, № 1  нумерації 1 та 2 строго граціозні з одна- ковою потужністю, а також 1(w1) = 2(w2). Сімейство граціозно сумісних дерев з поту- жністю граціозної нумерації k = 1 показано на рис. 15. Рис. 15 Розширені гірляндова побудова, -побудова та побудова приєднанням виконуються аналогіч- но звичайним, але замість копій лише одного граціозного дерева використовуються дерева з деякого сімейства граціозно сумісних дерев. У [17] доведено, що дерева, отримані розшире- ною побудовою, є граціозними. Приклади гір- ляндової побудови, розширеної побудови при- єднанням та -побудови показано на рис. 16, 17, 18 відповідно. Використано дерева T1, T2, T3 з рис. 15. Рис. 16 Рис. 17 Рис. 18 Аргументи проти гіпотези та висновки Обидва підходи до вивчення гіпотези про граціозність дерев досі давали лише підтвер- дження гіпотези. Проте деякі дослідники ви- словлюють серйозні сумніви щодо її коректно- сті. Зокрема, у [18] відзначено, що переважну більшість методів побудови граціозної нуме- рації розроблено для дерев, які мають певні риси регулярності (зірки, симетричні дерева) або характеризуються досить простою структурою (гусениці, феєрверки), в той же час повністю відсутні доведення граціозності у випадках до- статньо нерегулярних дерев (навіть граціозність усіх омарів ще досі не доведена). Серед ефек- тивних шляхів критики гіпотези названо аналіз усіх можливих граціозних нумерацій деяких граціозних дерев, що дав би можливість оціни- ти вплив структури дерева на можливі номери його вершин. На думку автора [18], деякі дере- ва зі складною будовою можуть накладати на- стільки серйозні обмеження на нумерацію ве- ршин, що граціозність цих дерев буде постав- лено під сумнів. Хоча пошук граціозних нуме- рацій для усіх дерев з кількістю вершин до 35 включно визнається вагомим аргументом на користь правдивості гіпотези, але цей факт не виключає можливості існування неграціозних дерев, що мають більше, ніж 35 вершин. Так чи інакше, сьогодні ще рано говорити про повне доведення або спростування гіпоте- зи про граціозність дерев, незважаючи на те, що з часу її появи минуло майже півстоліття. У УСиМ, 2016, № 1 21 2004 р. [19] та у 2009 р. [20] запропоновано варіанти доведення гіпотези, але вони вияви- лися хибними або неповними. Втім, переважна більшість дослідників сього- дні схиляється до віри в справедливість гіпотези про граціозність дерев, беручи до уваги граціоз- ність багатьох класів дерев, результати комп’ю- терного пошуку та повну відсутність контрпри- кладів. Як зауважив один дослідник, «віра в справедливість гіпотези про граціозність дерев настільки сильна, що, якби навіть було насправді знайдено дерево, яке не допускає граціозної ну- мерації, його, скоріше за все, не визнали б дере- вом» [21]. 1. Rosa A. On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Sympos. Rome, 1966) / Eds. Gordon and Breach. – New York; Dunod, Paris, 1967. – P. 349–355. 2. Golomb S.W. How to number a graph // Graph Theory and Computing / Ed. by R.C. Read. – New York: Aca- demic Press, 1972. – P. 23–37. 3. Fang W.A computational approach to the graceful tree conjecture. – Access Mode: arXiv:1003.3045v2 [cs.DM] 4. Morgan D. All lobsters with perfect matchings are graceful // Electron. Notes Discrete Math. – 2002. – N 11. – P. 503–508. 5. Pastel A.M., Raynaud H. Numerotation gracieuse des oliviers, in colloq. – Grenoble: Publ. University de Grenoble, 1978. – P. 218–223. 6. Bermond J.C. Graceful graphs, radio antennae and French windmills // Graph Theory and Comb. – Lon- don: Pitman, 1979. – P. 18–37. 7. Chen W.C., Lü H.I., Yeh Y.N. Operations of interlaced trees and graceful trees // Southeast Asian Bull. Math. – 1997. – № 21. – P. 337–348. 8. Настоящий В.А., Петренюк А.Я., Петренюк Д.А. Доведення існування півобертової T-факторизації для всіх півсиметричних дерев порядку n = 22 / Комбінаторні конфігурації та їх застосування: Ма- теріали Дев’ятого Міжвуз. наук.-практ. сем., 16–17 квітня 2010 р. / Відп. ред. Г.П. Донець. – Кірово- град, 2010. – С. 97–103. 9. Sethuraman G., Jesintha J. All extended banana trees are graceful // Proc. Internat. Conf. Math. Comp. Sci. – 2009. – N 1. – P. 4–8. 10. Bahl M., Lake S., Wertheim A. Gracefulness of Families of Spiders. – http://facstaff.unca.edu/pbahls/papers/Spi- ders.pdf 11. Bermond J.C., Sotteau D. Graph Decompositions and G-design // Proc. 5th British Comb. Conf. – 1975. – P. 52–72. 12. Hrnčiar P., Haviar A. All trees of diameter five are gra- ceful // Discrete Math. – 2001. – N 233. – P. 133–150. 13. Донец Г.А., Петренюк Д.А. Построение T-фактори- заций полного графа и проблема Роса // УСиМ. – 2010. – № 4. – С. 21–24. 14. Burzio M., Ferrarese G. The subdivision graph of a graceful tree is a graceful tree // Discrete Math. – 1998. – N 181. – P. 275–281. 15. Koh K.M., Rogers D.G., Tan T. On Graceful Trees // Nanta Mathematica – 1977. – N 10. – P. 207–211. 16. Koh K.M., Tan T., Rogers D.G. Two theorems on gra- ceful trees // Discrete Math. – 1979. – N 25. – P. 141–148. 17. Mavronicolas M., Michael L. A substitution theorem for graceful trees and its applications // Discrete Mathe- matics. – 2009. – 309, N 12. – P. 3757–3766. 18. Vietri A. Sailing towards, and then against, the Graceful Tree Conjecture: some promiscuous results // I.C.A. Bulletin. – 2008. – N 53. – P. 31–46. 19. Krishnaa A.A. study of the major graph labelings of trees // Informatica. – 2004. – N 15. – P. 515–524. 20. Jesse Gilbert. A Complete Proof of the Graceful Tree Conjecture Using the Concept of Edge Degree, Jan. 9, 2009. – Access Mode: arXiv:0709.2201 [cs.DM] 21. Towards the Graceful Tree Conjecture: A survey / M. Alfalayleh, L. Brankovic, H. Giggins et al. // Proc. AWOCA2004, 7–9 July, Ballina, Austrtalia, 2004. Поступила 09.04.2015 E-mail: quitar-player@meta.ua © Д.А. Петренюк, 2016 Д.А. Петренюк Грациозные деревья. Анализ проблемы и перспективы Введение. Гипотеза о грациозности деревьев – одна из наиболее популярных математических гипотез, которая впервые была сформулирована в 1976 г. [1], и с того времени попытки доказать или опровергнуть ее не пре- кращаются. Несмотря на значительный интерес к гипо- тезе за рубежом, в Украине этой теме до сих пор уделя- лось мало внимания. Предложенная функция разметки вершин графа получила название -оценки [1]; позднее такую разметку назвали грациозной, и теперь этот тер- мин употребляется наиболее широко [2]. Существует два основных подхода к решению про- блемы истинности гипотезы о грациозности деревьев. Первый из них состоит в доказательстве грациозности и получении алгоритмов грациозной разметки для отдель- ных классов деревьев. Если бы удалось продемонстри- ровать грациозность всех возможных классов деревьев, то гипотеза была бы доказана. Сегодня грациозность до- казана для целого ряда классов деревьев. Найдено зна- чительное количество методов объединения нескольких грациозных деревьев для получения большего грациоз- 22 УСиМ, 2016, № 1 ного дерева. Наиболее весомые из этих результатов рас- смотрены в данной статье. Другой подход к ответу на вопрос о грациозности всех деревьев состоит в использовании компьютера для проверки грациозности деревьев, количество вершин которых не превышает заданной конечной величины. Такой подход – дополнительный источник алгоритмов грациозной разметки деревьев. Он также может быть использован для опровержения гипотезы, если будет найдено хотя бы одно дерево, не допускающее грациоз- ной разметки. Однако такое дерево пока не найдено. В 2010 г. использован детерминированный алгоритм поис- ка с возвращением и доказано, что все деревья, имею- щие не более 35 вершин, грациозны [3]. Постановка задачи Грациозной разметкой неориентированного графа G с n ребрами называют такое взаимно однозначное соот- ветствие между множеством вершин графа G и множе- ством {0, 1, 2, ..., n}, где все индуцированные метки ре- бер различны. Индуцированная метка ребра – это абсо- лютная величина разности между номерами (метками) двух его концов. Другими словами, разметка φ грациоз- на, если φ: V  {0, 1, 2, ..., \|E\|} есть инъективным ото- бражением и если все ребра графа G имеют разные мет- ки из множества {1, 2, ..., \|E\|}. В [1] также показано, что существование грациозной разметки для заданного гра- фа G с n ребрами – достаточное условие существования циклического разложения полного графа порядка 2n + 1 на подграфы, изоморфные графу G. Пример такого раз- ложения для n = 3 показан на рис. 1. Рис. 1 Граф считается грациозным, если допускает грациоз- ную разметку. Знаменитая гипотеза о грациозности де- ревьев (также известная как гипотеза Рингеля–Коцига, гипотеза Росы или гипотеза Рингеля–Коцига–Росы) заклю- чается в том, что все деревья грациозны. Гипотеза о грациозности деревьев до сих пор не до- казана и продолжает привлекать внимание профессио- налов и любителей. Сегодня поток публикаций о граци- озности деревьев не прекращается, поэтому отслеживать все новые результаты достаточно сложно. Далее пере- числены основные классы деревьев, грациозность кото- рых уже доказана. Классы грациозных деревьев Звезда Звездой называют дерево, имеющее не более одной вершины, степень которой превышает единицу, а все остальные вершины имеют степень единица. Доказано, что все звезды грациозны. На рис. 2 изображена граци- озно размеченная звезда. Рис. 2 Цепь Цепью называют дерево, имеющее лишь две верши- ны (концы цепи) степени единица, а степень всех ос- тальных вершин равна двум. В любой цепи допускается грациозная разметка. Грациозно размеченные цепи по- казаны на рис. 3. Рис. 3 Гусеница Гусеницей (или однодистантным деревом [4]) назы- вают дерево, которое после удаления всех висячих вер- шин (т.е. вершин степени один) превращается в цепь. Во всех гусеницах допускается грациозная разметка. Гра- циозно размеченные гусеницы показаны на рис. 4. Рис. 4 Оливковые деревья Оливковое дерево – это совокупность i цепей, соеди- ненных в одной вершине, причем длина i-й цепи равна i. Доказано [5], что все оливковые деревья дерева граци- озны. Грациозно размеченное оливковое дерево показа- но на рис. 5. Рис. 5 Грациозность некоторых видов омаров Омаром (или двудистантным деревом [4]) называют дерево, которое после удаления всех висячих вершин пре- вращается в гусеницу (рис. 6). Другими словами, омаром называют дерево, содержащее цепь (хребет), расстояние от которой до каждой вершины не превышает двух. В 1979 г. автор [6] высказал гипотезу о том, что все омары грациозны. Было предпринято много попыток доказать эту гипотезу, однако до сих пор никому не уда- УСиМ, 2016, № 1 23 лось это сделать. Сегодня известны следующие граци- озные подклассы омаров. Рис. 6 Ф е й е р в е р к и Фейерверк F – это дерево, состоящее из цепи P(F) и множества звезд, когда вершина цепи P(F) соединена с центральной вершиной одной звезды. Доказано [7], что все фейерверки грациозны. На рис. 6 показан грациозно размеченный фейерверк. (2, k)-г у с е н и ц ы Дерево, полученное присоединением к каждой вер- шине некоторой цепи r цепей длины k, называют (r, k)- гусеницей. Простой способ получения грациозной раз- метки для отдельного подкласса омаров – (2, 2)-гусениц предложен в [8]. Грациозно размеченная (2, 2)-гусеница показана на рис. 7. Рис. 7 О м а р ы с с о в е р ш е н н ы м и п а р о с о- ч е т а н и я м и Паросочетанием в графе называют множество ребер этого графа, не имеющих общих вершин. Совершенным паросочетанием, или 1-фактором в графе называют паросочетание, содержащее все вершины данного графа. Доказано [4], что все омары с совершенными паросоче- таниями – грациозны. Банановые деревья и обобщенные банановые деревья Банановое дерево состоит из совокупности звезд и вершины v, причем одна конечная вершина каждой звез- ды соединена с вершиной v (рис. 8). Все банановые де- ревья и обобщенные банановые деревья (графы, полу- ченные соединением одной вершины с одной конечной вершиной каждой из любого количества звезд, где со- единение достигается при помощи цепи длиной не ме- нее двух), – грациозны [9]. Рис. 8 Семейство грациозных пауков Паук – это дерево, имеющее одну вершину со степе- нью, превышающей два. Если такая вершина существу- ет, ее называют узловой вершиной дерева. Ногой паука называют любую из цепей, соединяющую узловую вер- шину с конечной вершиной дерева. Каждое дерево-паук T с l ногами, каждая из которых имеет длину из промежутка {m, m +1} для некоторого m > 1, грациозное [10]. Грациозная разметка такого де- рева-паука с семью ногами и 18 вершинами показана на рис. 9. Рис. 9 Симметричные деревья Симметричное дерево – это корневое дерево, у кото- рого степень всех вершин, расположенных на одинако- вом расстоянии от корня, одинакова. Грациозность всех симметричных деревьев доказана в 1975 г. [11]. Грациозно размеченное симметричное дерево показано на рис. 10. Рис. 10 Деревья, диаметр которых не превышает пяти Диаметр дерева – это длина самого длинного мар- шрута в этом дереве. Все деревья диаметра пять – гра- циозны. Показано в 2001 г. [12]. Методы получения больших грациозных деревьев из меньших Присоединение гусеницы к грациозно размеченно- му дереву Если к вершине с номером 1 грациозно размеченного дерева Gn присоединить гусеницу, то полученное дерево допускает грациозную разметку [13]. Гусеница должна присоединяться крайней вершиной ее хребта (рис. 11). Рис. 11 24 УСиМ, 2016, № 1 Деление ребер грациозного дерева В 1998 г.в [14] показано, что все деревья, получен- ные из грациозных деревьев заменой каждого ребра це- пью длины два, также грациозны (рис. 12). а б Рис. 12 Гирляндное построение Гирляндным построением называют получение но- вого дерева путем присоединения к каждой висячей вершине звезды изоморфной копии грациозного дерева T вершиной, соответствующей вершине v дерева T, по- лучающей при грациозной разметке метку 1 или n. Дерево, полученное путем гирляндного построения, – грациозно [15]. Гирляндное построение, при помощи которого из трех копий бананового дерева порядка 11 (а) получено большее грациозное дерево порядка 34 (б), показано на рис. 13. а б Рис. 13 -построение -построением называют получение нового дерева из двух грациозных деревьев путем присоединения к каждой вершине одного грациозного дерева (дерева– хозяина) изоморфной копии другого грациозного дерева T вершиной, соответствующей некоторой произвольно выбранной фиксированной вершине v дерева T. Любое дерево, полученное путем -построения, – грациозно [16]. Пример получения грациозного дерева (б) из двух меньших грациозных деревьев (а) при помощи - построения показан на рис. 14. a б Рис. 14 Построение присоединением Построение присоединением – это получение нового дерева путем идентификации корней произвольного числа копий заданного грациозного дерева в одной вер- шине r; вершину r будем называть особенной вершиной построенного дерева. Любое дерево, полученное путем построения присоединением, грациозно [16]. Расширенные гирляндное построение, -построение и построение присоединением В 2008 г.в [17] расширены некоторые результаты [16] введением понятия грациозно совместимых деревь- ев и доказательством так называемой теоремы подста- новок. Два грациозно размеченных дерева T1 и T2 с V (T1)= =V (T2) будем называть грациозно совместимыми, если выполняется одно из следующих условий:  грациозно размеченные деревья T1 и T2 идентичны;  разметки 1 и 2 строго грациозны с одинаковой мощностью, а также 1(w1) = 2(w2). Семейство грациозно совместимых деревьев (мощ- ность грациозной разметки каждого из деревьев k = 1) показано га рис. 15. Рис. 15 Расширенные гирляндное построение, -построение и построение присоединением выполняются аналогич- но, но вместо копий одного грациозного дерева исполь- зуются деревья из некоторого семейства грациозно со- вместимых деревьев. В [17] доказано, что деревья, по- лученные расширенным построением, грациозны. При- меры гирляндного построения, расширенного построе- ния присоединением и -построением показаны на УСиМ, 2016, № 1 25 рис. 16, 17, 18 соответственно. Использованы деревья T1, T2, T3 из рис. 15. Рис. 16 Рис. 17 Рис. 18 Аргументы против гипотезы и заключение. Оба описанные подхода к изучению гипотезы о грациозно- сти деревьев до сих пор давали лишь подтверждения гипотезы. Однако некоторые исследователи высказыва- ют сомнения относительно ее истинности. В частности, в [18] отмечено, что подавляющее большинство методов построения грациозной разметки было разработано для деревьев, обладающих некоторыми признаками регу- лярности (звезды, симметричные деревья) либо характе- ризуются достаточно простой структурой (гусеницы, фейерверки). В то же время полностью отсутствуют до- казательства грациозности в случаях достаточно нерегу- лярных деревьев (даже грациозность всех омаров пока не доказана). Среди эффективных путей критики гипо- тезы назван анализ всех возможных грациозных разме- ток некоторых грациозных деревьев, который позволил бы оценить влияние структуры дерева на возможные номера его вершин. По мнению автора [18], некоторые деревья со сложным строением могут накладывать на- столько серьезные ограничения на метки вершин, что грациозность этих деревьев будет поставлена под со- мнение. Хотя поиск грациозных разметок для всех де- ревьев с количеством вершин до 35 включительно при- знается весомым аргументом в пользу истинности гипо- тезы. Этот факт никоим образом не исключает возмож- ности существования неграциозных деревьев, имеющих более 35 вершин. Так или иначе, рано говорить о полном доказатель- стве или опровержении гипотезы о грациозности де- ревьев, несмотря на то, что с момента ее появления прошло почти полстолетия. В 2004 г. [19] и в 2009 г. [20] предложены варианты доказательства гипотезы, но они оказались ошибочными либо неполными. Тем не менее, сегодня подавляющее большинство исследователей склоняется к вере в справедливость ги- потезы о грациозности деревьев, принимая во внимание доказанную грациозность многих классов деревьев, ре- зультаты компьютерного поиска и полное отсутствие контрпримеров. Как заметил один исследователь, «вера в справедливость гипотезы о грациозности деревьев настолько сильна, что если бы даже действительно было найдено дерево, не допускающее грациозной разметки, его, скорее всего, не признали бы деревом» [21]. UDC 519.17 D.A. Petreniuk Graceful Trees: the State of Arts and the Prospects Graceful Tree Conjecture is one of the most popular math conjectures. It was formulated almost half a century ago, but even today it is still far from being completely solved. A. Krishnaa in 2004 and J. Gilbert in 2009 [19] proposed their proofs of the Conjecture, but they turned out to be wrong or incomplete. The article contains a brief review of the state of art in solv- ing the Conjecture, including some results that have been proposed by the author. Окончание на стр. 33 УСиМ, 2016, № 1 33 Окончание статьи Д.А. Петренюка Graceful labeling of undirected graph G with n edges is an injection from vertex set of graph G to {0, 1, 2, ..., n} such that all the induced edge labels are different. Induced edge label is the absolute value of the difference between the labels (num- bers) of the two end-vertices of the edge. A graph is graceful if it admits graceful labeling. The Graceful Tree Conjecture claims that all trees are graceful. There are two approaches to solving the Graceful Tree Conjecture. The first is to prove gracefulness and obtain graceful labeling algorithms for certain classes of trees; if once gracefulness of all classes of trees is shown, then the Conjecture is proved. For today, gracefulness is proved for stars, paths, caterpillars, olive trees, some subclasses of lobsters (firecrackers, (2,2)-caterpillars, lobsters with perfect matchings), banana and generalized banana trees, and some other classes. Many meth- ods of combining few graceful trees to obtain a new bigger graceful tree have been found. Another approach to solving the conjecture is to use computer to check if all trees with number of vertices not exceeding a given value are graceful. This approach can provide new graceful labeling algorithms and can be also used to disprove the Conjecture, once at least one tree that does not admit graceful labeling is found. However, no such tree has been found so far. It has been proved that all the trees having not more than 35 vertices are graceful. Despite all the positive results, some researchers express serious doubts about the truthfulness of the Conjecture. They point out that the most graceful labeling methods have been designed for trees with regular or very simple structure, while there are no proofs of gracefulness for sufficiently irregular trees. However, the majority or researchers tend to believe that the Graceful Tree Conjecture is true and will be once proved completely.  << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice
id	nasplib_isofts_kiev_ua-123456789-112893
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0130-5395
language	Ukrainian
last_indexed	2025-11-30T09:29:07Z
publishDate	2016
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
record_format	dspace
spelling	Петренюк, Д.А. 2017-01-29T09:48:22Z 2017-01-29T09:48:22Z 2016 Граціозні дерева. Аналіз проблеми та перспективи / Д.А. Петренюк // Управляющие системы и машины. — 2016. — № 1. — С. 16–25, 33. — укр. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/112893 519.17 Запропоновано аналіз результатів щодо гіпотези про граціозність дерев. Розглянуто два підходи до питання правдивості гіпотези про дані дерева, описано основні класи таких дерев, способи отримання більших дерев з менших, а також результати комп’ютерних обчислень стосовно граціозності дерев. Подано деякі аргументи проти гіпотези про граціозність дерев. Предложен анализ результатов относительно гипотезы о грациозности деревьев. Рассмотрены два подхода к вопросу истинности гипотезы о данных деревьях, основные классы грациозных деревьев, способы получения больших деревьев из меньших, а также результаты компьютерных вычислений о грациозности деревьев. Приведены некоторые аргументы против гипотезы о грациозности деревьев. Graceful Tree Conjecture is one of the most popular math conjectures. It was formulated almost half a century ago, but even today it is still far from being completely solved. A. Krishnaa in 2004 and J. Gilbert in 2009 [19] proposed their proofs of the Conjecture, but they turned out to be wrong or incomplete. The article contains a brief review of the state of art in solving the Conjecture, including some results that have been proposed by the author. Graceful labeling of undirected graph G with n edges is an injection from vertex set of graph G to {0, 1, 2, ..., n} such that all the induced edge labels are different. Induced edge label is the absolute value of the difference between the labels (numbers) of the two end-vertices of the edge. A graph is graceful if it admits graceful labeling. The Graceful Tree Conjecture claims that all trees are graceful. There are two approaches to solving the Graceful Tree Conjecture. The first is to prove gracefulness and obtain graceful labeling algorithms for certain classes of trees; if once gracefulness of all classes of trees is shown, then the Conjecture is proved. For today, gracefulness is proved for stars, paths, caterpillars, olive trees, some subclasses of lobsters (firecrackers, (2,2)-caterpillars, lobsters with perfect matchings), banana and generalized banana trees, and some other classes. Many methods of combining few graceful trees to obtain a new bigger graceful tree have been found. Another approach to solving the conjecture is to use computer to check if all trees with number of vertices not exceeding a given value are graceful. This approach can provide new graceful labeling algorithms and can be also used to disprove the Conjecture, once at least one tree that does not admit graceful labeling is found. However, no such tree has been found so far. It has been proved that all the trees having not more than 35 vertices are graceful. Despite all the positive results, some researchers express serious doubts about the truthfulness of the Conjecture. They point out that the most graceful labeling methods have been designed for trees with regular or very simple structure, while there are no proofs of gracefulness for sufficiently irregular trees. However, the majority or researchers tend to believe that the Graceful Tree Conjecture is true and will be once proved completely. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Фундаментальные и прикладные проблемы Computer Science Граціозні дерева. Аналіз проблеми та перспективи Грациозные дерева. Анализ проблемы и перспективы Graceful Trees: the State of Arts and the Prospects Article published earlier
spellingShingle	Граціозні дерева. Аналіз проблеми та перспективи Петренюк, Д.А. Фундаментальные и прикладные проблемы Computer Science
title	Граціозні дерева. Аналіз проблеми та перспективи
title_alt	Грациозные дерева. Анализ проблемы и перспективы Graceful Trees: the State of Arts and the Prospects
title_full	Граціозні дерева. Аналіз проблеми та перспективи
title_fullStr	Граціозні дерева. Аналіз проблеми та перспективи
title_full_unstemmed	Граціозні дерева. Аналіз проблеми та перспективи
title_short	Граціозні дерева. Аналіз проблеми та перспективи
title_sort	граціозні дерева. аналіз проблеми та перспективи
topic	Фундаментальные и прикладные проблемы Computer Science
topic_facet	Фундаментальные и прикладные проблемы Computer Science
url	https://nasplib.isofts.kiev.ua/handle/123456789/112893
work_keys_str_mv	AT petrenûkda gracíozníderevaanalízproblemitaperspektivi AT petrenûkda gracioznyederevaanalizproblemyiperspektivy AT petrenûkda gracefultreesthestateofartsandtheprospects

Граціозні дерева. Аналіз проблеми та перспективи

Institution

Similar Items