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 (kaasaarvatud) nii, et ükski tipule omistatud arv ei kordu ja 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 (kaasaarvatud) 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 (kaasaarvatud) ja unikaalsed.

Matemaatiline definitsioon 
Graafi  graatsiliseks märgenduseks nimetatakse sellist tippude  ja servade  märgendust, kus nii  kui  on injektiivsed ja kehtib seos .

Graatsilise märgenduse variatsioonid

a-märgendus 
Aastal 1966 defineeris Rosa a-märgenduse kui graatsilise märgenduse lisaparameetriga , kus iga servale  kehtib kas  või .

k-graatsiline märgendus 
Aastal 1982 tutvustasid Maheo ja Thuillier terminit "k-graatsilisus". Graaf  servade arvuga  on k-graatsiline, kui leidub märgendus  tippudest  nii, et servad, millele omistatakse väärtusteks nendevaheliste tippude absoluutvahe, kuuluvad hulka .

-märgendus 
Graafi  tipu arvuga  -märgenduseks nimetatakse üksühest funktsiooni  graafi  tippudest , kus iga serva  märgendatakse funktsiooniga .  -märgendust tutvustasid Chartrand, Erwin, VanderJagt ja Zhang aastal 2004.

Paaritu-graatsline märgendus 
Graafi nimetatakse paaritu-graatsiliselt märgendatuks, kui leidub injektsioon  hulgast  hulka  nii, et kui iga serv  on märgendatud , siis iga serva märgendus kuulub hulka .  on graafi servade arv.

Hammingi-graatsiline märgendus 
Graafi  nimetatakse Hammingi-graatsiliselt märgendatuks, kui leidub injektiivne märgendus  -st binaarsete -paaride  massiivi nii, et , kus d on Hammingi kaugus.

Peamised tulemused 
 Oma originaalartiklis tõestas Rosa, et Euleri graaf servade arvuga   või  ei saa olla graatsiline.
 Samuti oma originaalartiklis tõestas Rosa, et tsükkel  on graatsiline siis ja ainult siis, kui  või .
 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

Graafiteooria