Grafikon jelölés

A gráfcímkézés a matematikában  a címkék hozzárendelése, amelyeket hagyományosan egész számok , élek , csúcsok vagy élek és csúcsok ábrázolnak a gráfban [1] .

Formálisan egy G = ( V , E ) gráf esetén a csúcscímke a V csúcshalmaz és a címkekészlet közötti függvény . Az ilyen függvényt tartalmazó gráfot csúcscímkés gráfnak nevezzük . Hasonlóképpen, az élek címkézése egy függvény az E élek halmazától a címkék halmazáig. Ebben az esetben a gráfot élcímkés gráfnak nevezzük .

Abban az esetben, ha az élcímkék egy rendezett halmaz elemei (vagyis valós számok ), a címkézést súlyozott gráfnak nevezhetjük .

Hacsak nincs kifejezetten kijelentve, a gráfcímkézés kifejezés általában csúcscímkézést jelent, ahol minden címke különbözik. Egy ilyen gráf ekvivalens módon címkézhető egymást követő egész számokkal {1, …, | V |}, ahol | v | a gráf csúcsainak száma [1] . Sok alkalmazásnál az élek vagy csúcsok olyan címkéket kapnak, amelyek értelmet adnak a megfelelő területen. Például az élekhez súlyokat lehet rendelni , amelyek a két szomszédos csúcs közötti utazás "költségét" jelentik [2] .

A fenti definícióban a gráf véges irányítatlan egyszerű gráf. A jelölés fogalma azonban a gráfok minden kiterjesztésére és általánosítására vonatkozik. Például az automaták elméletében és a formális nyelvek elméletében általában címkézett multigráfokat szoktak figyelembe venni , vagyis olyan gráfokat, amelyekben egy csúcspár több címkézett éllel összekapcsolható [3] .

Történelem

A legtöbb gráfcímkézés eredete Alex Rosa 1967-es cikkében [4] bemutatott címkézéséből származik . Rosa háromféle jelölést azonosított, amelyeket α-, β- és ρ-címkéknek nevezett [5] . A β-jelölést később S. V. Golomb átnevezte kecsesre , és ez a név népszerűvé vált.

Különleges alkalmak

Kecses jelölés

Egy gráfot kecsesnek nevezünk, ha csúcsai 0-tól |-ig terjedő számokkal vannak megjelölve E |, a gráf mérete, és ez a címkézés 1 és | közötti élcímkézést generál E |. Bármely e él esetén az e él címkéje egyenlő az e él két csúcsa közötti pozitív különbséggel . Más szóval, ha az e él két i és j címkével ellátott csúcsra esik, akkor az e él címkézett | i − j |. Így egy G = ( V , E ) gráf akkor és csak akkor kecses, ha van olyan beágyazás, amely E -ből bijekciót generál pozitív egész számokig | E |.

Rosa munkájában bebizonyította, hogy az 1-hez vagy 2-höz ( modulo 4) hasonló méretű Euler-ciklusok nem kecsesek. Jelenleg intenzív vizsgálat alatt áll, hogy mely gráfcsaládok kecsesek. A gráfcímkézés talán legnagyobb bizonyítatlan sejtése a Ringel-Kotzig sejtés, amely szerint minden fa kecses. Ez minden ösvénynél , hernyóknál és sok más végtelen facsaládnál bevált. Maga Kotzig "gonosznak" nevezte a sejtés bizonyítására tett kísérletet [6] .

Szélezett kecses jelölések

A p csúcsokkal és q élekkel rendelkező egyszerű gráfok (hurkok és több él nélküli gráfok) élkecses címkézése az élek címkézése az {1, …, q } halmaz különböző egészeivel , úgy, hogy a csúcscímkézés által generált csúcscímkézés a szomszédos élek összege a p modul felett , amely 0-tól p − 1 -ig minden értéket hozzárendel a csúcsokhoz. A G gráfot élkecsesnek mondjuk, ha lehetővé teszi az él-kecses címkézést .

A kecses bordajelölést S. Lo vezette be először 1985-ben [7] .

A gráf élkecses címkézésének szükséges feltétele a Lo feltétel :

Harmonikus jelölés

A G gráf harmonikus címkézése a G gráf csúcsainak halmazának beágyazása egy modulo k kongruenciájú egész számok csoportjába , ahol k a G gráf éleinek száma , amely bijekciót generál a gráf élei között. G gráfot és a modulo k számokat úgy, hogy kiválasztjuk két x , y (mod k ) csúcs címkéinek él ( x , y ) összegét . A harmonikus gráf olyan gráf, amelynek harmonikus címkézése van. A páratlan ciklusok harmonikus gráfok, akárcsak a Petersen-gráf . Van egy olyan sejtés, hogy minden fa harmonikus gráf, ha egy csúcsot megengedünk újrafelhasználni [8] . A hét oldalas K 1,7 × K 2 könyv példát ad egy nem-harmonikus gráfra [9] .

Grafikon színezése

A grafikon színezése a grafikonok jelölésének egy alosztálya. A csúcsszínezés különböző címkéket rendel a szomszédos csúcsokhoz, az élszínezés más- más címkét rendel a szomszédos élekhez.

Szerencsés jelölés

G szerencsés címkézése az , ha pozitív egész számokat rendelünk G csúcsaihoz oly módon, hogy ha S ( v ) a v szomszédos csúcsainak címkéinek összege , akkor S a G csúcsszínezése . A G gráf szerencsés száma a legkisebb k , amelyen a G gráf {1, …, k } egész számokkal rendelkezik szerencsés címkével [10] .

Jegyzetek

  1. ↑ 1 2 Weisstein, Eric W. Címkézett gráf  (angol) a Wolfram MathWorld webhelyen .
  2. ↑ Calderbank, 1995 , p. 53.
  3. ↑ Nyelvelméleti fejlemények, 2005 .
  4. ↑ Gallian, 1998 .
  5. ↑ Rosa .
  6. ↑ Vietri, 2008 , p. 31–46.
  7. ↑ Lo, 1985 , p. 231–241.
  8. ↑ Guy, 2004 , p. 190–191.
  9. ↑ Gallian, 1998 , p. Dinamikus felmérés 6.
  10. ↑ Czerwiński, Grytczuk, Ẓelazny, 2009 , p. 1078–1081.

Irodalom