Graatsiline märgendus

**Graatsiline märgendus** on selline *m*-servalise graafi märgendus, kus igale graafi tipule on omistatud väärtus vahemikus 0 kuni *m* (kaasa arvatud) nii, et ükski tipule omistatud arv ei kordu ning igale tippude *x* ja *y* vahelisele servale omistatud väärtus, mis on *x* ja *y* väärtuse absoluutvahe, on samuti unikaalne. Graafi, millele on võimalik graatsilist märgendust teha, nimetatakse graatsiliseks graafiks.

Termini "graatsiline märgendus" autor on Solomon W. Golomb. Originaalis oli märgenduse klassifikatsiooni nimetus beetamärgendus (*ß*-märgendus). Nimetust kasutas esimesena Alexander Rosa graafide märgenduste artiklis 1967. aastal.

Üks peamistest tõestamata hüpoteesidest graafiteoorias on graatsiliste puude hüpotees, samuti tuntud kui Ringel-Kotzigi hüpotees. Hüpotees sai nime autorite Gerhard Ringeli ja Anton Kotzigi järgi. Hüpotees väidab, et kõik puud on graatsilised.

Graatsilise märgenduse nõrgem versioon on peaaegu graatsiline märgendus, kus tippude väärtused on arvuvahemiku 0 kuni *m*+1 (kaasa arvatud) alamhulk. Nagu graatsilise märgenduse puhulgi, ei tohi peaaegu graatsilise märgenduse tippudele omistatud väärtused kattuda ning servade väärtused on määratud tippude absoluutvahega. Servade väärtused peavad olema vahemikus 1 kuni m+1 (kaasa arvatud) ja unikaalsed.

## Matemaatiline definitsioon
Graafi G graatsiliseks märgenduseks nimetatakse sellist tippude f:V\rightarrow[0,m] ja servade f_\gamma:E\rightarrow[1,m] märgendust, kus nii f kui f_\gamma on injektiivsed ja kehtib seos f_\gamma(u,v) = |f(u)-f(v)|.

## Graatsilise märgenduse variatsioonid
### ''a''-märgendus
1966. aastal defineeris Rosa *a*-märgenduse kui graatsilise märgenduse lisaparameetriga k, kus iga servale xy kehtib kas f(x) \leq k  või f(y) \leq k .

### ''k''-graatsiline märgendus
1982. aastal tutvustasid Maheo ja Thuillier terminit "*k*-graatsilisus". Graaf G servade arvuga q on *k*-graatsiline, kui leidub märgendus f tippudest \{0,1,2,...,q+k-1\} nii, et servad, millele omistatakse väärtusteks nendevaheliste tippude absoluutvahe, kuuluvad hulka \{k,k+1,...,q+k-q\}.

### ''<math>\gamma</math>''-märgendus
Graafi G tipu arvuga m \gamma-märgenduseks nimetatakse üksühest funktsiooni f graafi G tippudest \{0,1,2,...,m\}, kus iga serva uv märgendatakse funktsiooniga f_\gamma(u,v) = |f(u)-f(v)|. \gamma-märgendust tutvustasid Chartrand, Erwin, VanderJagt ja Zhang aastal 2004.

### Paaritu-graatsline märgendus
Graafi nimetatakse paaritu-graatsiliselt märgendatuks, kui leidub injektsioon f hulgast V(G) hulka \{0,1,2,...,2q-1\}
 nii, et kui iga serv xy on märgendatud |f(x)-f(y)|, siis iga serva märgendus kuulub hulka \{1,3,5,...,2q-1\}. q on graafi servade arv.

### Hammingi-graatsiline märgendus
Graafi G=(V,E) nimetatakse Hammingi-graatsiliselt märgendatuks, kui leidub injektiivne märgendus g V-st binaarsete |E|-paaride massiivi nii, et \{d(g(v),g(u))|uv \in E   \} = \{1,2,...,|E|\}, kus d on Hammingi kaugus.

## Peamised tulemused
* Oma originaalartiklis tõestas Rosa, et Euleri graaf servade arvuga m = 1 või m = 2 ei saa olla graatsiline.
* Samuti oma originaalartiklis tõestas Rosa, et tsükkel C_n on graatsiline siis ja ainult siis, kui n = 0 või n = 3.
* On tõestatud, et kõik ahelad ja röövikgraafid on graatsilised.
* On tõestatud, et kõik perfektsete paaridega *lobster*-graafid on graatsilised.
* Kõik kuni 27-servalised puud on graatsilised. Selle tulemuseni jõudsid Aldred ja McKay aastal 1998, kasutades arvuteid. Aastal 2010 jõuti tulemuseni, et kõik kuni 35-servalised graafid on graatsilised.
* On tõestatud, et kõik *n*-dimensionaalsed hüperkuubid on graatsilised.

## Viited

## Välislingid
*Graatsiliste puude kontrollimise projekt