Označení grafu

Označování grafů v matematice  je přiřazení štítků, které jsou tradičně reprezentovány celými čísly , hranami , vrcholy nebo hranami a vrcholy grafu [1] .

Formálně, daný graf G = ( V , E ) , štítek vrcholu je funkce z množiny vrcholů V do množiny štítků . Graf s takovou funkcí se nazývá graf označený vrcholem . Podobně je označování hran funkcí od množiny hran E k množině popisků. V tomto případě se graf nazývá graf s hranou .

V případě, že jsou popisky hran prvky uspořádané množiny (tj. reálná čísla ), lze označení nazvat váženým grafem .

Pokud není výslovně uvedeno, pojem označení grafu obvykle znamená označení vrcholů, kde jsou všechna označení odlišná. Takový graf lze ekvivalentně označit po sobě jdoucími celými čísly {1, …, | V |}, kde | v | je počet vrcholů grafu [1] . Pro mnoho aplikací jsou hrany nebo vrcholy opatřeny štítky, které dávají smysl v odpovídající oblasti. Hranám lze například přiřadit váhy , které představují „náklady“ na cestu mezi dvěma sousedními vrcholy [2] .

Ve výše uvedené definici je graf chápán jako konečný neorientovaný jednoduchý graf. Pojem značkování však platí pro všechna rozšíření a zobecnění grafů. Například v teorii automatů a teorii formálních jazyků se obvykle uvažuje o značených multigrafech , tedy o grafech, ve kterých může být dvojice vrcholů spojena několika značenými hranami [3] .

Historie

Většina označení grafů má svůj původ v označeních, která představil Alex Rosa ve svém článku z roku 1967 [4] . Rosa identifikoval tři typy značení, které nazval α-, β- a ρ-označení [5] . β-markup byl později přejmenován S. V. Golombem na graceful a tento název zlidověl.

Zvláštní příležitosti

Půvabné označení

Graf se nazývá ladný, pokud jsou jeho vrcholy označeny čísly od 0 do | E |, velikost grafu, a toto označení generuje označení hrany od 1 do | E |. Pro jakoukoli hranu e se označení hrany e rovná kladnému rozdílu mezi dvěma vrcholy hrany e . Jinými slovy, pokud hrana e spadá do dvou vrcholů označených i a j , pak je hrana e označena | i − j |. Graf G = ( V , E ) je tedy půvabný tehdy a pouze tehdy , pokud existuje vložení , které generuje bijekci z E na kladná celá čísla až | E |.

Rosa ve své práci dokázal, že všechny Eulerovy cykly velikosti srovnatelné s 1 nebo 2 ( modulo 4) nejsou půvabné. Které rodiny grafů jsou půvabné, je v současné době předmětem intenzivního zkoumání. Snad největší neprokázaná domněnka v označování grafů je domněnka Ringel-Kotzig, která říká, že všechny stromy jsou půvabné. To bylo prokázáno u všech cest , housenek a mnoha dalších nekonečných rodin stromů. Sám Kotzig nazval pokus dokázat domněnku „zlou“ [6] .

Hranatá půvabná označení

Hranové ladné označování jednoduchých grafů (grafy bez smyček a více hran) s p vrcholy a q hranami je označení hran různými celými čísly z množiny {1, …, q } tak, že označení vertexu generované označením vertexu jako součet sousedních hran nad modulem p , který přiřadí vrcholům všechny hodnoty od 0 do p − 1 . O grafu G se říká, že je ladný na hraně, pokud umožňuje označování s ladností hran.

Půvabné značení žeber jako první zavedl S. Lo v roce 1985 [7] .

Nezbytnou podmínkou pro existenci okrajového ladného označení pro graf je podmínka Lo :

Harmonické značení

Harmonické označení grafu G je vložení množiny vrcholů grafu G do skupiny celých čísel kongruence modulo k , kde k je počet hran grafu G , které generují bijekci mezi hranami grafu G . grafu G a čísel modulo k výběrem hran ( x , y ) součtů značek dvou vrcholů x , y (mod k ). Harmonický graf je graf, který má harmonické označení. Liché cykly jsou harmonické grafy, stejně jako Petersenův graf . Existuje domněnka, že všechny stromy jsou harmonické grafy, pokud je dovoleno znovu použít jeden vrchol [8] . Kniha o sedmi stranách K 1,7 × K 2 uvádí příklad neharmonického grafu [9] .

Barvení grafu

Barvení grafu je podtřídou značkování grafu. Barvení vrcholů přiřadí různé popisky sousedním vrcholům, vybarvení hran přiřadí různé popisky sousedním okrajům.

Lucky markup

Šťastné označení G je přiřazení kladných celých čísel k vrcholům G takovým způsobem, že pokud S ( v ) je součtem značek sousedních vrcholů v , pak S je zbarvení vrcholu G. Šťastné číslo grafu G je nejmenší k , které má graf G šťastné označení celými čísly {1, …, k } [10] .

Poznámky

  1. ↑ 1 2 Weisstein, Eric W. Označený graf  (anglicky) na webu Wolfram MathWorld .
  2. ↑ Calderbank, 1995 , s. 53.
  3. ↑ Vývoj v teorii jazyků, 2005 .
  4. ↑ Gallian, 1998 .
  5. ↑ Rosa .
  6. ↑ Vietri, 2008 , str. 31–46.
  7. ↑ Lo, 1985 , str. 231–241.
  8. ↑ Chlap, 2004 , str. 190–191.
  9. ↑ Gallian, 1998 , s. Dynamický průzkum 6.
  10. ↑ Czerwiński, Grytczuk, Ẓelazny, 2009 , str. 1078–1081.

Literatura