Вікіпедія

Граціозна розмітка

вершинна розмітка графу з m ребрами підмножиною цілих чисел між 0 і m включно, така, що різні вершини позначено різними числами, а абсолютна р

Граціозна розмітка[1] в теорії графів — така вершинна розмітка графу з ребрами деякою підмножиною цілих чисел між 0 і включно, що різні вершини позначено різними числами, і така, що, якщо кожне ребро позначити абсолютною різницею міток вершин, які воно з'єднує, то всі отримані різниці будуть різними[2]. Граф, який допускає граціозну розмітку, називають граціозним графом.

Граціозна розмітка. Вершинну розмітку показано чорним кольором, реберну — червоним

Автором терміна «граціозна розмітка» є Соломон Ґоломб; Александер Роса був першим, хто виділив цей клас розміток і ввів його під назвою -розмітка в статті 1967 року про розмітки графів.[3].

Однією з головних недоведених гіпотез у теорії графів є гіпотеза граціозності дерев (англ. Graceful Tree Conjecture), також відома як гіпотеза Рінгеля — Коціга за іменами її авторів Герхарда Рінґеля[ru] і Антона Коціга[en], яка стверджує, що всі дерева граціозні. Станом на 2017 гіпотезу все ще не доведено, але простота формулювання привернула широку увагу математиків-аматорів (внаслідок чого з'явилося багато неправильних доведень), Коціг свого часу навіть охарактеризував масові спроби довести її як «хворобу»[4].

Основні результати ред.

В оригінальній статті Роса довів, що ейлерів граф з числом ребер m ≡ 1 (mod 4) або m ≡ 2 (mod 4) не може бути граціозним.[3] У ній же показано, що цикл Cn граціозний тоді і тільки тоді, коли n ≡ 0 (mod 4) або n ≡ 3 (mod 4).

Граціозні всі шляхи, гусениці, всі омари[en] з досконалим паруванням[5], всі колеса, стерна[en], шестерні[en], всі прямокутні решітки[6], а також всі n-вимірні гіперкуби[7]. Всі прості графи з 4 і менше вершинами граціозні, неграціозними простими графами на п'яти вершинах є тільки 5-цикл (п'ятикутник), повний граф K5 і метелик.

Граціозні всі дерева з числом вершин не більше ніж 27; цей результат отримали 1988 року за допомогою комп'ютерної програми Альдред і Маккей[en][6][8]; удосконалення їхнього підходу (із застосуванням іншого обчислювального методу) дозволило показати 2010 року, що граціозними є всі дерева до 35 вершин включно — це результат проєкту розподілених обчислень Graceful Tree Verification Project під керівництвом Веньцзе Фана[9].

Примітка ред.

  1. ↑ Семенюта М. Ф. Частинні випадки задачі граціозності графів // Компьютерная математика. — 2015. — № 2. — С. 96-102. Архівовано з джерела 2 серпня 2021. Процитовано 2 серпня 2021.
  2. ↑ Virginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001. PostScript [Архівовано 25 вересня 2006 у Wayback Machine.]
  3. ↑ а б Rosa, A. Theory of Graphs (Internat. Sympos., Rome, 1966). — New York : Gordon and Breach, 1967. — 21 April. — С. 349—355.
  4. ↑ Huang, C.; Kotzig, A.; Rosa, A. Further results on tree labellings // Utilitas Mathematica. — 1982. — Т. 21 (21 April). — С. 31—48.
  5. ↑ Morgan, David. All lobsters with perfect matchings are graceful // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 53 (21 April). — С. 82—85.
  6. ↑ а б Gallian, Joseph A. A dynamic survey of graph labeling // Electronic Journal of Combinatorics[en] : journal. — . — Vol. 5. — P. Dynamic Survey 6 (electronic), в 1-м издании 43 стр., в 18-м — 389 стр. Архівовано з джерела 15 грудня 2018. Процитовано 2 серпня 2021.
  7. ↑ Kotzig, Anton. Decompositions of complete graphs into isomorphic cubes // Journal of Combinatorial Theory. Series B : journal. — 1981. — Vol. 31, no. 3 (21 April). — P. 292—296. — DOI:10.1016/0095-8956(81)90031-9.
  8. ↑ Aldred, R. E. L.; McKay, Brendan D. Graceful and harmonious labellings of trees // Bulletin of the Institute of Combinatorics and its Applications. — 1998. — Т. 23 (21 April). — С. 69—72.
  9. ↑ Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture. — 2010. — 21 April. — arXiv:1003.3045. Архівовано з джерела 15 серпня 2016. Процитовано 2 серпня 2021. См. также Graceful Tree Verification Project

Література ред.

  • K. Eshghi Introduction to Graceful Graphs [Архівовано 2 серпня 2021 у Wayback Machine.], Sharif University of Technology, 2002.
  • U. N. Deshmukh and Vasanti N. Bhat-Nayak, New families of graceful banana trees — Proceedings Mathematical Sciences, 1996 — 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 — Springer
Отримано з https://uk.wikipedia.org/w/index.php?title=Граціозна_розмітка&oldid=36631495