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] .
Î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] .