Gráfok színezése

A MathWikiből

(Változatok közti eltérés)

A lap 2007. április 28., 12:49-kori változata

A gráfelméletben, gráfok színezésének nevezzük azt, amikor színeket (vagy számokat) rendelünk egy gráf külön részeihez. Ezek alatt a részek alatt csúcsokat, éleket, vagy lapokat értünk.

A leggyakoribb a csúcsok színezésének a problémája, ugyanis a másik két esetet is tudjuk csúcsszínezésként vizsgálni: egy gráf élszínezése megfelel az élgráfjának a csucsszinezesevel, es egy graf lapszinezese megfelel a graf dualisanak a csucsszinezesevel.

Egy grafban azt nevezzuk egy "jo" csucsszinezesnek, amikor ket szomszedos csucs (ket csucs amely kozott fut el) kulonbozo szinu.

Nagyon sok megoldatlan kerdes van a grafok szinezese teren, viszont szamtalan erdekes hasznalata is van a grafszinezesnek. Peldaul az ismert Sudoku jatekot is lehet egy grafnak tekinteni, ahol a sorokat, oszlopokat, es 3x3-as negyzeteket klikkeknek vesszuk.

Kromatikus Szam

Egy grafnal gyakori kerdes, hogy minimalisan hany szin kell ahhoz, hogy "jol" kitudjuk szinezni a graf csucsait. Ezt a szamot nevezzuk a kromatikus szamnak es $χ(G)$ -vel jeloljuk.

$χ(G)$ -nek nehany tulajdonsaga:

$χ(G) = 1$ akkor es csak akkor ha graf fuggetlen pontokbol all (eleket nem tartalmaz)

$χ(G) = 2$ ha G paros graf

$χ(G)$ $\geq$ $3$ ha G tartalmaz paratlan kort.

$χ(G)$ $\geq$ $ω(G)$ (ahol $ω(G)$ G klikkszamat jeloli)

$χ(G)$ $\leq$ $Δ(G) + 1$ (ahol $Δ(G)$ G maximalis fokszamat jeloli)

$χ(G)$ $\leq$ $Δ(G)$ ha G nem teljes graf es nem paratlan hosszu kor (ld. Brooks tetelet)

$χ(K n) = n$ ahol $K n$ az n csucsu teljes grafot jeloli.

Egy grafnak az elkromatikus szama az a minimalis ertek, ahany szinnel ki tudjuk ugy szinezni a graf eleit, hogy tetszoleges ket el, melynek egy kozos csucs a vegpontja, ne legyen azonos szinu. Az elkromatikus szamot $χ e (G)$ -vel jeloljuk.

Brooks tétel

Ha G egy egyszeru, osszefuggo, nem teljes graf es nem paratlan hosszusagu kor, akkor $χ(G)$ $\leq$ $Δ(G)$ , ahol $Δ(G)$ G maximalis fokszamat jeloli.

Bizonyitas:

$Δ(G)$ = 2 -re nyilvanvalo az allitas, ugyanis ha a maximalis fokszam 2, akkor vagy egy kort, vagy egy utat kapunk. Egy ut vagy egy paros kor eseteben 2 szinnel ki tudjuk szinezni a grafot, es ha a kor paratlan hosszusagu akkor csak harommal.

Most mar feltehetjuk hogy $Δ(G)$ $\geq$ 3. Csucsszamra valo indukcioval bizonyitjuk az allitast.

Elso lepesben azt latjuk be, hogy eleg ketszeresen osszefuggo grafokat vizsgalnunk. Indirekt tegyuk fel hogy nem ketszeresen osszefuggo a vizsgalando grafunk, ami azt jelenti hogy letezik $x$ pont melyet elhagyva legalabb ket komponensre esik szet a grafunk. Ha pontosan ket komponensre esik szet, akkor minket komponensbe visszaillesztve $x$ -et, nevezzuk ezeket a komponenseket $G 1$ es $G 2$ -nek. Ha tobb mint ket komponensre esik szet, akkor maradjon $G 1$ tovabbra is egy komponens es $G 2$ meg legyen az osszes tobbi komponens es x unioja: $G 2$ = ( $G$ \ $G 1$ ) $\cup$ { $x$ }. A ket komponensben minden csucs fokszama ugyanannyi marad, csak x fokszama csokken. Tehat tovabbra sem lesz egyik fokszam negyobb mint $Δ(G)$ viszont $x$ feltetlenul kisebb lesz mindket komponensben $Δ(G)$ -nel. Ebbol kovetkezik, hogy egyik komponens sem lehet $Δ(G)$ + 1 pontu teljes graf. Tehat, az indukcios feltevesunk miatt, mindket komponenes kiszinezheto $Δ(G)$ szinnel, es ha $x$ -et mindket komponensben ugyanolyan szinure valasztjuk, akkor ha ujra "osszerakjuk" a grafot akkor az eredeti grafunknak egy $Δ(G)$ szinnel valo jo szinezeset kapjuk.

Masodik lepesben pedig azt igazoljuk, hogy eleg haromszorosan osszefuggo grafokat neznunk. Ismet indirekt tegyuk fel hogy egy $x$ es $y$ pont elhagyasaval szetesik a grafunk $G 1$ es $G 2$ -re. Vegezzuk el ugyanazt az eljarast mint az elso lepesben. Itt csak akkor van gond, ha az egyik komponens minden szinezese olyan hogy $x$ es $y$ egyforma szinu, es a masik komponens minden szinezesenel $x$ es $y$ kulonbozo szinu. Ebben az esetben nem tudjuk ujra "osszerakni" a grafunkat. Ebben az esetben tekintsuk a $G 1$ es $G 2$ komponenst es mindkettoben huzzunk be $x$ es $y$ kozott egy elt. Igy $x$ es $y$ fokszama tovabbra is legfeljebb $Δ(G)$ marad, vagyis az indukcios felteves miatt vagy mindket komponens kiszinezheto $Δ(G)$ szinnel, vagy legalabb az egyik komponensunk egy $Δ(G)$ + 1 csucsu teljes graf. Ha szinezheto mindketto $Δ(G)$ szinnel, akkor mindket komponensben kulonbozo szinu $x$ es $y$ , tehat "ossze tudjuk illeszteni" a ket komponenst es keszen vagyunk. Ha pedig az egyik komponensunk egy $Δ(G)$ + 1 pontu teljes graf, akkor ebben a komponensben $x$ -nek es $y$ -nak is csak egy szomszedja volt a masik komponensben. Jeloljuk ezeket $x'$ es $y'$ -vel. Ha most elvesszuk mondjuk az $x$ es $y'$ csucsot az eredeti grafukbol, akkor ismet ket reszre esik a grafunk. Ha ezzel a ket ponttal vegezzuk el az elobbi algoritmust akkor nem kapunk olyan komponenst ami teljes graf, tehat megkapjuk a graf egy $Δ(G)$ szinnel valo jo szinezeset.

Innentol mar csak haromszorosan osszefuggo grafokra kell bizonyitanunk az allitast. Legyenek $v 1$ , $v 2$ , $v n$ olyan csucsi $G$ -nek, hogy $v 1$ es $v n$ kozott fut el, $v 2$ es $v n$ kozott is fut el, viszont $v 1$ es $v 2$ kozott nem fut el (mivel $G$ nem teljes graf es osszefuggo, ezert ilyen csucsokat minden esetben talalunk). Jeloljuk a graf tobbi pontjat a kovetkezokeppen: $v 3$ , $v 4$ ,..., $v (n - 1)$ es minden pontnak legyen nagyobb indexu szomszedja is. folyamatban...

@@ 1. sor: / 1. sor: @@
+A gráfelméletben, gráfok színezésének nevezzük azt, amikor színeket (vagy számokat) rendelünk egy gráf külön részeihez. Ezek alatt a részek alatt csúcsokat, éleket, vagy lapokat értünk.
+A leggyakoribb a csúcsok színezésének a problémája, ugyanis a másik két esetet is tudjuk csúcsszínezésként vizsgálni: egy gráf élszínezése megfelel az élgráfjának a csucsszinezesevel, es egy graf lapszinezese megfelel a graf dualisanak a csucsszinezesevel.
+Egy grafban azt nevezzuk egy "jo" csucsszinezesnek, amikor ket szomszedos csucs (ket csucs amely kozott fut el) kulonbozo szinu.
+Nagyon sok megoldatlan kerdes van a grafok szinezese teren, viszont szamtalan erdekes hasznalata is van a grafszinezesnek. Peldaul az ismert Sudoku jatekot is lehet egy grafnak tekinteni, ahol a sorokat, oszlopokat, es 3x3-as negyzeteket [[klikk]]eknek vesszuk.
 == Kromatikus Szam ==
-Egy hurokelmentes G graf csucsai jol szinezhetok k szinnel, ha tetszoleges ket szomszedos csucsa nem azonos szinu. Ennek a k szamnak a minimalis erteket nevezzuk a G graf kromatikus szamanak es <math>\chi(G)</math>-vel jeloljuk.
+Egy grafnal gyakori kerdes, hogy minimalisan hany szin kell ahhoz, hogy "jol" kitudjuk szinezni a graf csucsait. Ezt a szamot nevezzuk a kromatikus szamnak es <math>\chi(G)</math>-vel jeloljuk.
+<math>\chi(G)</math>-nek nehany tulajdonsaga:
+<math>\chi(G) = 1</math> akkor es csak akkor ha graf fuggetlen pontokbol all (eleket nem tartalmaz)
+<math>\chi(G) = 2</math> ha G [[paros graf]]
+<math>\chi(G)</math> <math>\geq</math> <math>3</math> ha G tartalmaz paratlan kort.
+<math>\chi(G)</math> <math>\geq</math> <math>\omega(G)</math> (ahol <math>\omega(G)</math> G klikkszamat jeloli)
+<math>\chi(G)</math> <math>\leq</math> <math>\Delta(G) + 1</math> (ahol <math>\Delta(G)</math> G maximalis [[fokszam]]at jeloli)
+<math>\chi(G)</math> <math>\leq</math> <math>\Delta(G)</math> ha G nem [[teljes graf]] es nem paratlan hosszu kor (ld. Brooks tetelet)
+<math>\chi(K_n) = n</math> ahol <math>K_n</math> az n csucsu teljes grafot jeloli.
+Egy grafnak az elkromatikus szama az a minimalis ertek, ahany szinnel ki tudjuk ugy szinezni a graf eleit, hogy tetszoleges ket el, melynek egy kozos csucs a vegpontja, ne legyen azonos szinu. Az elkromatikus szamot <math>\chi_e(G)</math>-vel jeloljuk.
+== Brooks tétel ==
+Ha G egy egyszeru, osszefuggo, nem teljes graf es nem paratlan hosszusagu kor, akkor <math>\chi(G)</math> <math>\leq</math> <math>\Delta(G)</math>, ahol <math>\Delta(G)</math> G maximalis fokszamat jeloli.
+===Bizonyitas:===
+<math>\Delta(G)</math> = 2 -re nyilvanvalo az allitas, ugyanis ha a maximalis fokszam 2, akkor vagy egy kort, vagy egy utat kapunk. Egy ut vagy egy paros kor eseteben 2 szinnel ki tudjuk szinezni a grafot, es ha a kor paratlan hosszusagu akkor csak harommal.
+Most mar feltehetjuk hogy <math>\Delta(G)</math> <math> \geq</math> 3. Csucsszamra valo indukcioval bizonyitjuk az allitast.
+Elso lepesben azt latjuk be, hogy eleg ketszeresen osszefuggo grafokat vizsgalnunk. Indirekt tegyuk fel hogy nem ketszeresen osszefuggo a vizsgalando grafunk, ami azt jelenti hogy letezik <math>x</math> pont melyet elhagyva legalabb ket komponensre esik szet a grafunk. Ha pontosan ket komponensre esik szet, akkor minket komponensbe visszaillesztve <math>x</math>-et, nevezzuk ezeket a komponenseket <math>G_1</math> es <math>G_2</math>-nek. Ha tobb mint ket komponensre esik szet, akkor maradjon <math>G_1</math> tovabbra is egy komponens es <math>G_2</math> meg legyen az osszes tobbi komponens es x unioja: <math>G_2</math> = (<math>G</math> \ <math>G_1</math>) <math>\cup</math> {<math>x</math>}. A ket komponensben minden csucs fokszama ugyanannyi marad, csak x fokszama csokken. Tehat tovabbra sem lesz egyik fokszam negyobb mint <math>\Delta(G)</math> viszont <math>x</math> feltetlenul kisebb lesz mindket komponensben <math>\Delta(G)</math>-nel. Ebbol kovetkezik, hogy egyik komponens sem lehet <math>\Delta(G)</math> + 1 pontu teljes graf. Tehat, az indukcios feltevesunk miatt, mindket komponenes kiszinezheto <math>\Delta(G)</math> szinnel, es ha <math>x</math>-et mindket komponensben ugyanolyan szinure valasztjuk, akkor ha ujra "osszerakjuk" a grafot akkor az eredeti grafunknak egy <math>\Delta(G)</math> szinnel valo jo szinezeset kapjuk.
+Masodik lepesben pedig azt igazoljuk, hogy eleg haromszorosan osszefuggo grafokat neznunk. Ismet indirekt tegyuk fel hogy egy <math>x</math> es <math>y</math> pont elhagyasaval szetesik a grafunk <math>G_1</math> es <math>G_2</math>-re. Vegezzuk el ugyanazt az eljarast mint az elso lepesben. Itt csak akkor van gond, ha az egyik komponens minden szinezese olyan hogy <math>x</math> es <math>y</math> egyforma szinu, es a masik komponens minden szinezesenel <math>x</math> es <math>y</math> kulonbozo szinu. Ebben az esetben nem tudjuk ujra "osszerakni" a grafunkat. Ebben az esetben tekintsuk a <math>G_1</math> es <math>G_2</math> komponenst es mindkettoben huzzunk be <math>x</math> es <math>y</math> kozott egy elt. Igy <math>x</math> es <math>y</math> fokszama tovabbra is legfeljebb <math>\Delta(G)</math> marad, vagyis az indukcios felteves miatt vagy mindket komponens kiszinezheto <math>\Delta(G)</math> szinnel, vagy legalabb az egyik komponensunk egy <math>\Delta(G)</math> + 1 csucsu teljes graf. Ha szinezheto mindketto <math>\Delta(G)</math> szinnel, akkor mindket komponensben kulonbozo szinu <math>x</math> es <math>y</math>, tehat "ossze tudjuk illeszteni" a ket komponenst es keszen vagyunk. Ha pedig az egyik komponensunk egy <math>\Delta(G)</math> + 1 pontu teljes graf, akkor ebben a komponensben <math>x</math>-nek es <math>y</math>-nak is csak egy szomszedja volt a masik komponensben. Jeloljuk ezeket <math>x'</math> es <math>y'</math>-vel. Ha most elvesszuk mondjuk az <math>x</math> es <math>y'</math> csucsot az eredeti grafukbol, akkor ismet ket reszre esik a grafunk. Ha ezzel a ket ponttal vegezzuk el az elobbi algoritmust akkor nem kapunk olyan komponenst ami teljes graf, tehat megkapjuk a graf egy <math>\Delta(G)</math> szinnel valo jo szinezeset.
-== Elkromatikus Szam ==
+Innentol mar csak haromszorosan osszefuggo grafokra kell bizonyitanunk az allitast.
-Egy G graf elei jol szinezhetok m szinnel, ha tetszoleges ket szomszedos ele kulonbozo szinu. Ennek a m szamnak a minimalis erteket nevezzuk G elkromatikus szamanak es <math>\chi_e(G)</math>-vel jeloljuk.
+Legyenek <math>v_1</math>,<math>v_2</math>,<math>v_n</math> olyan csucsi <math>G</math>-nek, hogy <math>v_1</math> es <math>v_n</math> kozott fut el, <math>v_2</math> es <math>v_n</math> kozott is fut el, viszont <math>v_1</math> es <math>v_2</math> kozott nem fut el (mivel <math>G</math> nem teljes graf es osszefuggo, ezert ilyen csucsokat minden esetben talalunk). Jeloljuk a graf tobbi pontjat a kovetkezokeppen: <math>v_3</math>,<math>v_4</math>,...,<math>v_(n-1)</math> es minden pontnak legyen nagyobb indexu szomszedja is.
+folyamatban...

Gráfok színezése

A lap 2007. április 28., 12:49-kori változata

Kromatikus Szam

Brooks tétel

Bizonyitas:

Nézetek

Személyes eszközök

Navigáció

Keresés

Eszközök