Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Граціозна розмітка в теорії графів така вершинна розмітка графу з m displaystyle m ребрами деякою підмножиною цілих чисе

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

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

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

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

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

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

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

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

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

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

Примітка

  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. — 8 July. — С. 349—355.
  4. Huang, C.; Kotzig, A.; Rosa, A. Further results on tree labellings // Utilitas Mathematica. — 1982. — Т. 21 (8 July). — С. 31—48.
  5. Morgan, David. All lobsters with perfect matchings are graceful // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 53 (8 July). — С. 82—85.
  6. Gallian, Joseph A. A dynamic survey of graph labeling // [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. — 1981. — Vol. 31, no. 3 (8 July). — 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 (8 July). — С. 69—72.
  9. Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture. — 2010. — 8 July. — arXiv:1003.3045. з джерела 15 серпня 2016. Процитовано 2 серпня 2021. См. также

Література

  • 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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Graciozna rozmitka v teoriyi grafiv taka vershinna rozmitka grafu z m displaystyle m rebrami deyakoyu pidmnozhinoyu cilih chisel mizh 0 i m displaystyle m vklyuchno sho rizni vershini poznacheno riznimi chislami i taka sho yaksho kozhne rebro poznachiti absolyutnoyu rizniceyu mitok vershin yaki vono z yednuye to vsi otrimani riznici budut riznimi Graf yakij dopuskaye gracioznu rozmitku nazivayut gracioznim grafom Graciozna rozmitka Vershinnu rozmitku pokazano chornim kolorom rebernu chervonim Avtorom termina graciozna rozmitka ye Solomon Golomb Aleksander Rosa buv pershim hto vidiliv cej klas rozmitok i vviv jogo pid nazvoyu b displaystyle beta rozmitka v statti pro rozmitki grafiv Odniyeyu z golovnih nedovedenih gipotez u teoriyi grafiv ye gipoteza gracioznosti derev angl Graceful Tree Conjecture takozh vidoma yak gipoteza Ringelya Kociga za imenami yiyi avtoriv ru i en yaka stverdzhuye sho vsi dereva graciozni Stanom na 2017 gipotezu vse she ne dovedeno ale prostota formulyuvannya privernula shiroku uvagu matematikiv amatoriv vnaslidok chogo z yavilosya bagato nepravilnih doveden Kocig svogo chasu navit oharakterizuvav masovi sprobi dovesti yiyi yak hvorobu Osnovni rezultatiV originalnij statti Rosa doviv sho ejleriv graf z chislom reber m 1 mod 4 abo m 2 mod 4 ne mozhe buti gracioznim U nij zhe pokazano sho cikl Cn gracioznij todi i tilki todi koli n 0 mod 4 abo n 3 mod 4 Graciozni vsi shlyahi gusenici vsi en z doskonalim paruvannyam vsi kolesa en en vsi pryamokutni reshitki a takozh vsi n vimirni giperkubi Vsi prosti grafi z 4 i menshe vershinami graciozni negracioznimi prostimi grafami na p yati vershinah ye tilki 5 cikl p yatikutnik povnij graf K5 i metelik Graciozni vsi dereva z chislom vershin ne bilshe nizh 27 cej rezultat otrimali 1988 roku za dopomogoyu komp yuternoyi programi Aldred i en udoskonalennya yihnogo pidhodu iz zastosuvannyam inshogo obchislyuvalnogo metodu dozvolilo pokazati 2010 roku sho gracioznimi ye vsi dereva do 35 vershin vklyuchno ce rezultat proyektu rozpodilenih obchislen Graceful Tree Verification Project pid kerivnictvom Vencze Fana PrimitkaChastinni vipadki zadachi gracioznosti grafiv Kompyuternaya matematika 2015 2 S 96 102 z dzherela 2 serpnya 2021 Procitovano 2 serpnya 2021 Virginia Vassilevska Coding and Graceful Labeling of trees SURF 2001 PostScript 25 veresnya 2006 u Wayback Machine Rosa A Theory of Graphs Internat Sympos Rome 1966 New York Gordon and Breach 1967 8 July S 349 355 Huang C Kotzig A Rosa A Further results on tree labellings Utilitas Mathematica 1982 T 21 8 July S 31 48 Morgan David All lobsters with perfect matchings are graceful Bulletin of the Institute of Combinatorics and its Applications 2008 T 53 8 July S 82 85 Gallian Joseph A A dynamic survey of graph labeling en journal Vol 5 P Dynamic Survey 6 electronic v 1 m izdanii 43 str v 18 m 389 str z dzherela 15 grudnya 2018 Procitovano 2 serpnya 2021 Kotzig Anton Decompositions of complete graphs into isomorphic cubes journal 1981 Vol 31 no 3 8 July P 292 296 DOI 10 1016 0095 8956 81 90031 9 Aldred R E L McKay Brendan D Graceful and harmonious labellings of trees Bulletin of the Institute of Combinatorics and its Applications 1998 T 23 8 July S 69 72 Fang Wenjie A Computational Approach to the Graceful Tree Conjecture 2010 8 July arXiv 1003 3045 z dzherela 15 serpnya 2016 Procitovano 2 serpnya 2021 Sm takzheLiteraturaK Eshghi Introduction to Graceful Graphs 2 serpnya 2021 u 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

Дата публікації:
Топ