Markup grațios

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 februarie 2021; verificările necesită 3 modificări .

Etichetarea grațioasă în teoria grafurilor este o astfel de etichetare a vârfurilor unui graf cu muchii de către un subset de numere întregi între 0 și inclusiv, încât diferite vârfuri sunt etichetate cu numere diferite și astfel încât, dacă fiecare muchie este etichetată prin diferența absolută a etichetelor vârfurile pe care le conectează, atunci toate diferențele rezultate vor fi diferite [1] . Un grafic care permite etichetarea grațioasă se numește grafic grațios .

Autorul termenului „markup grațios” este Solomon Golomb ; Alexander Rosa a fost primul care a evidențiat această clasă de etichetare și a introdus-o sub numele de marcare într-o lucrare din 1967 despre etichetarea graficelor .  [2] .

Una dintre ipotezele majore nedovedite în teoria grafurilor este Conjectura Arborelui  Grațios , cunoscută și sub numele de Conjectura Ringel-Kotzig după Gerhard Ringel și Anton Kotzig , care au formulat -o ,  care afirmă că toți copacii sunt grațioși. Începând cu 2017, conjectura nu este încă dovedită, dar datorită simplității formulării, a atras o atenție largă a iubitorilor de matematică (ca urmare a cărora au apărut multe dovezi incorecte), Kotzig a descris la un moment dat chiar încercări în masă de a o dovedi. ca „boală” [3] .

Rezultate principale

În lucrarea originală, Rosa a demonstrat că un grafic Euler cu muchii m ≡ 1 (mod 4) sau m ≡ 2 (mod 4) nu poate fi grațios. [2] , arată de asemenea că ciclul C n este grațios dacă și numai dacă n ≡ 0 (mod 4) sau n ≡ 3 (mod 4).

Grațioase sunt toate căile , omizile , toți homarii cu potrivire perfectă [4] , toate roțile , plasele , cârmele , angrenajele , toate zăbrelele dreptunghiulare [5] , precum și toate hipercuburile n - dimensionale [ 6] . Toate graficele simple cu 4 sau mai puține vârfuri sunt grațioase, singurele grafice simple negrațioase pe cinci vârfuri sunt ciclul 5 ( pentagon ) , graficul K 5 complet și fluture [7] .

Toți copacii cu cel mult 27 de vârfuri sunt grațioși; acest rezultat a fost obținut de Aldred și McKay în 1998 folosind un program de calculator [  5] [8] ; îmbunătățirea abordării lor (folosind o metodă de calcul diferită) a făcut posibil să se arate în 2010 că toți copacii de până la 35 de vârfuri inclusiv sunt grațioși - acesta este rezultatul Proiectului Graceful Tree Verification condus de Wenjie Fang [9] .

Note

  1. ↑ Virginia Vassilevska, „Codificarea și etichetarea grațioasă a copacilor”. SURF 2001. PostScript Arhivat la 25 septembrie 2006 la Wayback Machine
  2. ↑ 1 2 Rosa, A. Theory of Graphs (Internat. Sympos., Roma, 1966)  (nespecificat) . - New York: Gordon și Breach, 1967. - S. 349-355 .
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. Rezultate suplimentare privind etichetarea arborilor  (nedefinită)  // Utilitas Mathematica. - 1982. - T. 21 . - S. 31-48 .
  4. ↑ Morgan, David. Toți homarii cu potriviri perfecte sunt grațioși  //  Buletinul Institutului de Combinatorică și Aplicațiile sale. - 2008. - T. 53 . - S. 82-85 .
  5. ↑ 1 2 Gallian, Joseph A. Un studiu dinamic al etichetării graficelor  // Electronic  Journal of Combinatorics : jurnal. — 1998; Ediția a XVIII-a în 2015. - Vol. 5 . - P. Dynamic Survey 6 (electronic), în ediția I 43 pagini, în a 18-a - 389 pagini .
  6. ↑ Kotzig, Anton. Descompunerea graficelor complete în cuburi izomorfe  (engleză)  // Journal of Combinatorial Theory. Seria B  : jurnal. - 1981. - Vol. 31 , nr. 3 . - P. 292-296 . - doi : 10.1016/0095-8956(81)90031-9 .
  7. ↑ Weisstein, Eric W. Graceful graph  pe site- ul Wolfram MathWorld .
  8. ↑ Aldred, REL; McKay, Brendan D. Etichetare grațioasă și armonioasă a arborilor  (neopr.)  // Buletinul Institutului de Combinatorică și aplicațiile sale. - 1998. - T. 23 . - S. 69-72 .
  9. ↑ Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture  (în engleză)  : jurnal. - 2010. - arXiv : 1003.3045 . Vezi și Proiectul de verificare a arborelui grațios

Literatură