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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автор:	Петренюк, Д.А.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Назва видання:	Управляющие системы и машины
Теми:	Фундаментальные и прикладные проблемы Computer Science
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/112893
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Граціозні дерева. Аналіз проблеми та перспективи / Д.А. Петренюк // Управляющие системы и машины. — 2016. — № 1. — С. 16–25, 33. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-112893
record_format	dspace
spelling	irk-123456789-1128932017-01-30T03:03:04Z Граціозні дерева. Аналіз проблеми та перспективи Петренюк, Д.А. Фундаментальные и прикладные проблемы Computer Science Запропоновано аналіз результатів щодо гіпотези про граціозність дерев. Розглянуто два підходи до питання правдивості гіпотези про дані дерева, описано основні класи таких дерев, способи отримання більших дерев з менших, а також результати комп’ютерних обчислень стосовно граціозності дерев. Подано деякі аргументи проти гіпотези про граціозність дерев. Предложен анализ результатов относительно гипотезы о грациозности деревьев. Рассмотрены два подхода к вопросу истинности гипотезы о данных деревьях, основные классы грациозных деревьев, способы получения больших деревьев из меньших, а также результаты компьютерных вычислений о грациозности деревьев. Приведены некоторые аргументы против гипотезы о грациозности деревьев. 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. 2016 Article Граціозні дерева. Аналіз проблеми та перспективи / Д.А. Петренюк // Управляющие системы и машины. — 2016. — № 1. — С. 16–25, 33. — укр. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/112893 519.17 uk Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science
spellingShingle	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science Петренюк, Д.А. Граціозні дерева. Аналіз проблеми та перспективи Управляющие системы и машины
description	Запропоновано аналіз результатів щодо гіпотези про граціозність дерев. Розглянуто два підходи до питання правдивості гіпотези про дані дерева, описано основні класи таких дерев, способи отримання більших дерев з менших, а також результати комп’ютерних обчислень стосовно граціозності дерев. Подано деякі аргументи проти гіпотези про граціозність дерев.
format	Article
author	Петренюк, Д.А.
author_facet	Петренюк, Д.А.
author_sort	Петренюк, Д.А.
title	Граціозні дерева. Аналіз проблеми та перспективи
title_short	Граціозні дерева. Аналіз проблеми та перспективи
title_full	Граціозні дерева. Аналіз проблеми та перспективи
title_fullStr	Граціозні дерева. Аналіз проблеми та перспективи
title_full_unstemmed	Граціозні дерева. Аналіз проблеми та перспективи
title_sort	граціозні дерева. аналіз проблеми та перспективи
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2016
topic_facet	Фундаментальные и прикладные проблемы Computer Science
url	http://dspace.nbuv.gov.ua/handle/123456789/112893
citation_txt	Граціозні дерева. Аналіз проблеми та перспективи / Д.А. Петренюк // Управляющие системы и машины. — 2016. — № 1. — С. 16–25, 33. — укр.
series	Управляющие системы и машины
work_keys_str_mv	AT petrenûkda gracíozníderevaanalízproblemitaperspektivi
first_indexed	2024-03-30T09:24:19Z
last_indexed	2024-03-30T09:24:19Z
_version_	1796149931898044416

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

Репозитарії

Схожі ресурси