Kecses jelölés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. február 6-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A kecses címkézés a gráfelméletben az élekkel rendelkező gráf csúcscímkézése 0 és inkluzív egész számok valamilyen részhalmazával , hogy a különböző csúcsok különböző számokkal vannak címkézve, és ha minden élt a gráf címkéinek abszolút különbsége jelöl meg. csúcsokat, amelyeket összeköt, akkor az összes eredő különbség eltérő lesz [1] . A kecses címkézést lehetővé tevő grafikonokat kecses gráfnak nevezzük .

A "kecses jelölés" kifejezés szerzője Solomon Golomb ; Alexander Rosa volt az első, aki kiemelte ezt a címkézési osztályt, és -markup néven bevezette azt egy 1967 -es , grafikonos címkézésről szóló tanulmányában .  [2] .

A gráfelmélet egyik fő bizonyítatlan hipotézise a Graceful Tree Conjecture , más néven Ringel-Kotzig sejtés Gerhard Ringel és Anton Kotzig után, akik megfogalmazták , és amely kimondja , hogy minden fa kecses. 2017-ben a sejtés még mindig nem bizonyított, de a megfogalmazás egyszerűsége miatt a matematika szerelmeseinek széles figyelmét felkeltette (aminek eredményeként sok helytelen bizonyíték jelent meg), Kotzig egy időben még tömeges bizonyítási kísérleteket is leírt. mint „betegség” [3] .   

Fő eredmények

Az eredeti cikkben Rosa bebizonyította, hogy az m ≡ 1 (mod 4) vagy m ≡ 2 (mod 4) élekkel rendelkező Euler-gráf nem lehet kecses. [2] , azt is mutatja, hogy a C n ciklus akkor és csak akkor kecses, ha n ≡ 0 (mod 4) vagy n ≡ 3 (mod 4).

Kecses minden ösvény , hernyó , minden homár tökéletes illeszkedéssel [ 4] , minden kerék , háló , kormánylapát , fogaskerekek , minden téglalap alakú rács [5] , valamint minden n - dimenziós hiperkocka [ 6] . Minden 4 vagy kevesebb csúcsú egyszerű gráf kecses, az egyetlen nem kecses egyszerű gráf öt csúcson az 5- ciklus ( ötszög ), a teljes K 5 gráf és a pillangó [7] .

Minden fa, amelynek legfeljebb 27 csúcsa van, kecses; ezt az eredményt Aldred és McKay kapta 1998 -ban egy számítógépes program segítségével [  5] [8] ; megközelítésük továbbfejlesztése (más számítási módszerrel) lehetővé tette 2010-ben annak kimutatását, hogy minden fa 35 csúcsig kecses – ez a Wenjie Fang által vezetett Graceful Tree Verification Project [9] eredménye .

Jegyzetek

  1. ↑ Virginia Vassilevska, "A fák kódolása és kecses címkézése". SURF 2001. PostScript archiválva : 2006. szeptember 25. a Wayback Machine -nél
  2. ↑ 1 2 Rosa, A. Graphs Theory of Graphs (Internat. Sympos., Róma, 1966)  (meghatározatlan) . - New York: Gordon and Breach, 1967. - S. 349-355 .
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. További eredmények a  facímkézésről (határozatlan)  // Utilitas Mathematica. - 1982. - T. 21 . - S. 31-48 .
  4. ↑ Morgan, David. Minden tökéletesen illeszkedő homár kecses  //  Bulletin of the Institute of Combinatorics and its Applications. - 2008. - T. 53 . - S. 82-85 .
  5. ↑ 1 2 Gallian, Joseph A. A graph labeling dinamikus felmérése  // Electronic  Journal of Combinatorics : folyóirat. – 1998; 18. kiadás 2015-ben. - 1. évf. 5 . - P. Dynamic Survey 6 (elektronikus), az 1. kiadásban 43 oldal, a 18. -ban - 389 oldal .
  6. ↑ Kotzig, Anton. Teljes gráfok dekompozíciói izomorf kockákra  (angol)  // Journal of Combinatorial Theory. B sorozat  : folyóirat. - 1981. - 1. évf. 31 , sz. 3 . - P. 292-296 . - doi : 10.1016/0095-8956(81)90031-9 .
  7. ↑ Weisstein, Eric W. Graceful grafikon  a Wolfram MathWorld webhelyen .
  8. ↑ Aldred, REL; McKay, Brendan D. Graceful and harmonious labellings of trees  (neopr.)  // Bulletin of the Institute of Combinatorics and its Applications. - 1998. - T. 23 . - S. 69-72 .
  9. ↑ Fang, Wenjie. A kecses fa sejtés számítási megközelítése  (angolul)  : folyóirat. - 2010. - arXiv : 1003.3045 . Lásd még: Graceful Tree Verification Project

Irodalom