Půvabné označení

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. února 2021; kontroly vyžadují 3 úpravy .

Půvabné označování v teorii grafů je takové označení vrcholů grafu s hranami nějakou podmnožinou celých čísel mezi 0 a včetně, že různé vrcholy jsou označeny různými čísly, a pokud je každá hrana označena absolutním rozdílem značek vrcholy, které spojuje, pak všechny výsledné rozdíly budou různé [1] . Graf, který umožňuje elegantní označování, se nazývá elegantní graf .

Autorem termínu „ladné označení“ je Solomon Golomb ; Alexander Rosa byl první , kdo vyčlenil tuto třídu označování a představil ji pod názvem -markup v dokumentu z roku 1967 o označování grafem .  [2] .

Jednou z hlavních neprokázaných hypotéz v teorii grafů je Graceful Tree Conjecture , známá také jako Ringel-Kotzigova domněnka podle Gerharda Ringela a Antona Kotziga , kteří ji formulovali a která říká , že všechny stromy jsou půvabné... Od roku 2017 se domněnka stále neprokázala, ale díky jednoduchosti formulace vzbudila širokou pozornost milovníků matematiky (v důsledku čehož se objevilo mnoho nesprávných důkazů), Kotzig svého času dokonce popisoval hromadné pokusy ji dokázat jako „nemoc“ [3] .   

Hlavní výsledky

V původním článku Rosa dokázal, že Eulerův graf s hranami m ≡ 1 (mod 4) nebo m ≡ 2 (mod 4) nemůže být elegantní. [2] , také ukazuje, že cyklus C n je půvabný právě tehdy, když n ≡ 0 (mod 4) nebo n ≡ 3 (mod 4).

Půvabné jsou všechny cesty , housenky , všichni humři s dokonalým přizpůsobením [4] , všechna kola , sítě , kormidla , ozubená kola , všechny pravoúhlé mříže [5] , stejně jako všechny n - rozměrné hyperkrychle [ 6] . Všechny jednoduché grafy se 4 a méně vrcholy jsou půvabné, jediné neladné jednoduché grafy na pěti vrcholech jsou 5 -cyklus ( pětiúhelník ), úplný graf K 5 a motýl [7] .

Všechny stromy s ne více než 27 vrcholy jsou půvabné; tento výsledek získali Aldred a McKay v roce 1998 pomocí počítačového programu [  5] [8] ; zlepšení jejich přístupu (pomocí jiné výpočetní metody) umožnilo v roce 2010 prokázat, že všechny stromy do 35 vrcholů včetně jsou půvabné – to je výsledek projektu Graceful Tree Verification Project pod vedením Wenjie Fang [9] .

Poznámky

  1. ↑ Virginia Vassilevska, "Kódování a půvabné označování stromů." SURF 2001. PostScript Archivováno 25. září 2006 na Wayback Machine
  2. ↑ 1 2 Rosa, A. Teorie grafů (Internat. Sympos., Řím, 1966)  (neurčeno) . - New York: Gordon and Breach, 1967. - S. 349-355 .
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. Další výsledky o označování stromů  (neurčité)  // Utilitas Mathematica. - 1982. - T. 21 . - S. 31-48 .
  4. ↑ Morgan, David. Všichni humři s perfektním spojením jsou elegantní  //  Bulletin Institutu kombinatoriky a jeho aplikací. - 2008. - T. 53 . - S. 82-85 .
  5. ↑ 1 2 Gallian, Joseph A. Dynamický přehled označování grafů  // Electronic  Journal of Combinatorics : deník. — 1998; 18. vydání v roce 2015. - Sv. 5 . - P. Dynamic Survey 6 (elektronický), v 1. vydání 43 stran, v 18. - 389 stran .
  6. ↑ Kotzig, Anton. Rozklad kompletních grafů na izomorfní krychle  (anglicky)  // Journal of Combinatorial Theory. Řada B  : deník. - 1981. - Sv. 31 , č. 3 . - str. 292-296 . - doi : 10.1016/0095-8956(81)90031-9 .
  7. ↑ Weisstein, Eric W. Graceful graph  na webu Wolfram MathWorld .
  8. ↑ Aldred, REL; McKay, Brendan D. Půvabné a harmonické označování stromů  (neopr.)  // Bulletin Institutu kombinatoriky a její aplikace. - 1998. - T. 23 . - S. 69-72 .
  9. ↑ Tesák, Wenjie. A Computational Approach to the Graceful Tree Conjecture  (anglicky)  : journal. - 2010. - arXiv : 1003.3045 . Viz také projekt Graceful Tree Verification Project

Literatura