Перегляд вихідного коду сторінки Граціозна розмітка

[[Файл:Graceful_labeling.svg|міні|Граціозна розмітка. [[Вершина (теорія графів)|Вершинну]] розмітку показано чорним кольором, реберну&nbsp;— червоним]]
'''Граціозна розмітка'''<ref>{{Стаття|автор=[[Семенюта Марина Фролівна|Семенюта М. Ф.]]|назва=Частинні випадки задачі граціозності графів|посилання=http://dspace.nbuv.gov.ua/bitstream/handle/123456789/168385/11-Semenyuta.pdf?sequence=3|видання=Компьютерная математика|номер=2|сторінки=96-102|рік=2015|accessdate=2 серпня 2021|archivedate=2 серпня 2021|archiveurl=https://web.archive.org/web/20210802083823/http://dspace.nbuv.gov.ua/bitstream/handle/123456789/168385/11-Semenyuta.pdf?sequence=3}}</ref> в [[Теорія графів|теорії графів]]&nbsp;— така вершинна [[Розмітка графу|розмітка]] графу з <math>m</math> ребрами деякою підмножиною [[Цілі числа|цілих чисел]] між 0 і <math>m</math> включно, що різні вершини позначено різними числами, і така, що, якщо кожне ребро позначити [[Модуль (математика)|абсолютною]] різницею міток вершин, які воно з'єднує, то всі отримані різниці будуть різними<ref name="Vas2001">Virginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001. [http://www.cs.cmu.edu/~virgi/final1.ps PostScript] {{Webarchive|url=https://web.archive.org/web/20060925110736/http://www.cs.cmu.edu/~virgi/final1.ps |date=25 вересня 2006 }}</ref>. Граф, який допускає граціозну розмітку, називають '''''граціозним графом'''''.

Автором терміна «граціозна розмітка» є [[Соломон Ґоломб]]; Александер Роса був першим, хто виділив цей клас розміток і ввів його під назвою '''''<math>\beta</math>-розмітка''''' в статті [[1967 у науці|1967 року]] про розмітки графів.<ref name="Ros1967">{{Стаття|place=New York|pages=349—355|publisher=Gordon and Breach|title=Theory of Graphs (Internat. Sympos., Rome, 1966)|language=und|author=Rosa, A.|date=1967}}</ref>.

Однією з головних [[Відкриті математичні питання|недоведених гіпотез]] у теорії графів є '''''гіпотеза граціозності дерев''''' ({{Lang-en|Graceful Tree Conjecture}}), також відома як '''''гіпотеза Рінгеля&nbsp;— Коціга''''' за іменами її авторів {{Нп|Герхард Рінґель|Герхарда Рінґеля|ru|Рингель, Герхард}} і {{Iw|Антон Коціг|Антона Коціга|en|Anton Kotzig}}, яка стверджує, що всі [[Дерево (теорія графів)|дерева]] граціозні. {{Станом на|2017}} гіпотезу все ще не доведено, але простота формулювання привернула широку увагу математиків-аматорів (внаслідок чого з'явилося багато неправильних доведень), Коціг свого часу навіть охарактеризував масові спроби довести її як «хворобу»<ref name="Hua1982">{{Стаття|видання=Utilitas Mathematica|pages=31—48|title=Further results on tree labellings|том=21|language=und|author=Huang, C.; Kotzig, A.; Rosa, A.|date=1982}}</ref>.

== Основні результати ==
В оригінальній статті Роса довів, що [[Ейлерів ланцюг|ейлерів граф]] з числом ребер ''m'' ≡ 1 (mod 4) або ''m'' ≡ 2 (mod 4) не може бути граціозним.<ref name="Ros1967"/> У ній же показано, що цикл ''C<sub>n</sub>'' граціозний [[Тоді й лише тоді|тоді і тільки тоді]], коли ''n'' ≡ 0 (mod 4) або ''n'' ≡ 3 (mod 4).

Граціозні всі [[Шлях (теорія графів)|шляхи]], [[Гусениця (теорія графів)|гусениці]], всі {{Не перекладено|Омар (теорія графів)|омари|en|lobster graph}} з [[Парування (теорія графів)|досконалим паруванням]]<ref name="Morgan">{{Стаття|видання=Bulletin of the Institute of Combinatorics and its Applications|pages=82—85|title=All lobsters with perfect matchings are graceful|url=http://hdl.handle.net/10402/era.26923|том=53|language=und|author=Morgan, David|date=2008}}</ref>, всі [[Колесо (теорія графів)|колеса]], {{Не перекладено|Стерно (теорія графів)|стерна|en|helm graph}}, {{Не перекладено|Шестірня (теорія графів)|шестерні|en|gear graph}}, всі прямокутні [[Решітка (теорія графів)|решітки]]<ref name="Gal2015">{{Стаття|видання={{Нп3|Electronic Journal of Combinatorics}}|pages=Dynamic Survey 6 (electronic), в 1-м издании 43 стр., в 18-м&nbsp;— 389 стр|title=A dynamic survey of graph labeling|url=http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS6/pdf|том=5|language=en|author=Gallian, Joseph A.|date=1998; 18-е издание в 2015|тип=journal|accessdate=2 серпня 2021|archivedate=15 грудня 2018|archiveurl=https://web.archive.org/web/20181215105507/http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS6/pdf}}</ref>, а також всі ''n''-вимірні [[гіперкуб]]и<ref name="Kot1981">{{Стаття|doi=10.1016/0095-8956(81)90031-9|номер=3|видання=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory. Series B]]|pages=292—296|title=Decompositions of complete graphs into isomorphic cubes|том=31|language=en|тип=journal|author=Kotzig, Anton|date=1981}}</ref>. Всі [[Словник термінів теорії графів|прості графи]] з 4 і менше вершинами граціозні, неграціозними простими графами на п'яти вершинах є тільки 5-[[Циклічний граф|цикл]] ([[п'ятикутник]]), [[повний граф]] ''K''<sub>5</sub> і [[Метелик (теорія графів)|метелик]].

Граціозні всі дерева з числом вершин не більше ніж 27; цей результат отримали 1988 року за допомогою комп'ютерної програми Альдред і {{Iw|Брендан Маккей|Маккей|en|Brendan McKay}}<ref name="Gal2015"/><ref>{{Стаття|видання=Bulletin of the Institute of Combinatorics and its Applications|pages=69—72|title=Graceful and harmonious labellings of trees|том=23|language=und|author=Aldred, R. E. L.; McKay, Brendan D.|date=1998}}</ref>; удосконалення їхнього підходу (із застосуванням іншого обчислювального методу) дозволило показати 2010 року, що граціозними є всі дерева до 35 вершин включно&nbsp;— це результат проєкту розподілених обчислень ''Graceful Tree Verification Project'' під керівництвом Веньцзе Фана<ref>{{Стаття|arxiv=1003.3045|title=A Computational Approach to the Graceful Tree Conjecture|url=http://arxiv.org/abs/1003.3045|language=en|тип=journal|author=Fang, Wenjie|date=2010|accessdate=2 серпня 2021|archivedate=15 серпня 2016|archiveurl=https://web.archive.org/web/20160815184534/http://arxiv.org/abs/1003.3045}} См. также [https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html Graceful Tree Verification Project]</ref>.

== Примітка ==
{{Reflist}}

== Література ==
* K. Eshghi [http://sharif.edu/~eshghi/Graceful%20Graphs-Final%20Edition-89-12-15.pdf Introduction to Graceful Graphs] {{Webarchive|url=https://web.archive.org/web/20210802083823/http://sharif.edu/~eshghi/Graceful%20Graphs-Final%20Edition-89-12-15.pdf |date=2 серпня 2021 }}, Sharif University of Technology, 2002.
* U. N. Deshmukh and Vasanti N. Bhat-Nayak, New families of graceful banana trees&nbsp;— Proceedings Mathematical Sciences, 1996&nbsp;— Springer
* M. Haviar, M. Ivaska, Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
* Ping Zhang, A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016&nbsp;— Springer

[[Категорія:Математичні гіпотези]]
[[Категорія:Теорія графів]]