Ugrás a tartalomhoz

Kritikus gráf

A Wikipédiából, a szabad enciklopédiából
Baloldalt felül egy 6 kromatikus számú csúcskritikus gráf található; a többi gráf ennek N−1 részgráfja, 5 kromatikus számmal.

A kritikusság általánosságban bármilyen tulajdonságra vagy mértékre utalhat. A gráfelmélet területén a kifejezést szinte mindig egy gráf kromatikus számával kapcsolatban használjuk. A kritikus gráfok érdekességét az adja, hogy a gráfelméletileg fontos tulajdonság, a kromatikus szám szempontjából minimálisak. Precízebben:

Egy G gráf csúcsa vagy éle a gráf kritikus eleme, ha törlésével G kromatikus száma csökkenne. Nyilvánvalóan a csökkenés legfeljebb 1-gyel történhet.

Egy kritikus gráf olyan gráf, melynek minden csúcsa vagy éle kritikus elem. Egy k-kritikus gráf olyan kritikus gráf, aminek kromatikus száma k; ha egy k kromatikus számú G gráf minden csúcsa kritikus elem, akkor a gráf k-csúcskritikus, ha pedig egy k élkromatikus számú (kromatikus indexű) gráf minden éle kritikus elem, akkor a gráf k-élkritikus.

Az n csúccsal és m éllel rendelkező k-kritikus G gráfok néhány tulajdonsága:

  • G egyetlen komponensből áll.
  • G véges (ez a de Bruijn–Erdős-tétel: de Bruijn & Erdős 1951).
  • δ(G) ≥ k − 1, tehát minden csúcs legalább k − 1 csúccsal szomszédos. Ami ennél erősebb G (k − 1)-szeresen élösszefüggő. Lásd (Lovász 1992)
  • Ha G (k − 1)-reguláris, tehát minden csúcs pontosan k − 1 csúccsal szomszédos, akkor G vagy a Kk vagy egy páratlan kör. Ez a Brooks-tétel; lásd (Brooks & Tutte 1941)).
  • 2 m ≥ (k − 1) n + k − 3 (Dirac 1957).
  • 2 m ≥ (k − 1) n + [(k − 3)/(k2 − 3)] n (Gallai 1963a).
  • G vagy felbontható két kisebb kritikus gráfra, ahol minden csúcsot a másik részgráf minden csúcsával él köti össze, vagy G-nek legalább 2k − 1 csúcsa van (Gallai 1963b). Ennél erősebb állítás is igaz: G vagy felbontható az előbbi módon, vagy G minden v csúcsához tartozik olyan k-színezés, amiben v színe nem szerepel más csúcsnál, minden más színosztályba pedig legalább két csúcs tartozik (Stehlík 2003).

Könnyen belátható, hogy G pontosan akkor csúcskritikus, ha minden v csúcsához tartozik egy optimális, jó színezése, melyben v egyelemű színosztály.

(Hajós 1961) alapján minden k-kritikus gráf előállítható a Kk teljes gráfból a Hajós-konstrukció és a két nem szomszédos csúcs azonosításának művelete segítségével. Az így megalkotott gráfok jó színezéséhez mindig legalább k színre van szükség.

Egy kétszeresen kritikus gráf vagy duplakritikus gráf (double-critical graph) olyan összefüggő gráf, melyben bármely két szomszédos csúcs törlése a kromatikus számot kettővel csökkenti. Nyitott kérdés, hogy a Kk teljes gráfon kívül létezik-e más duplakritikus k-kromatikus számú gráf (Erdős 1966).

Kapcsolódó szócikkek[szerkesztés]

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Critical graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek[szerkesztés]

További információk[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Kritikus_gráf&oldid=22013223”