12. Gráfok színezései

Question 1

Gráfok színezései:

Answer 1

Egy tetszőleges $f:V→ N$ függvényt csúcsszínezésnek nevezünk. A színeszés k-színezés ha $f:V→ {1, …, k}$($k ∈ \N, k ≥ 1$ tetszőleges szám). Egy $f:V→ N$ színezés jólszínezés, ha éllel összekötött csúcsok színei különbözőek, azaz
$∀x, y ∈ V {x, y} ∈ E ⇒ f(x) 6 \neq f(y)$

Question 2

Kromatikus szám:

Answer 2

• Egy tetszőleges (egyszerű) G gráf kromatikus száma, $χ(G)$ a legkisebb olyan $k∈ \N$ természetes szám amelyhez létezik a gráfnak k-színnel jólszínezése, azaz
  $χ(G):=min{k ∈ \N : vanf : V → {1, …, k} jólszínezés}.$
  Ha $χ(G)=k$, akkor G-t k-kromatikus gráfnak nevezzük

Question 3

Elemi állítások:

Answer 3

• Ha van jólszínezés, G-ben nincs hurokél.
• Bármely gráf jólszínezhető annyi színnel, ahány csúcsa van
• Ha a G hurokmentes gráf minden pontjának a foka legfeljebb k, akkor $G(k+1)$ színezhető.
• G gráf üres (nincs benne él) akkor és csak akkor, ha $χ(G) = 1$ (van rá algoritmus)
• G páros gráf, akkor és csak akkor ha $χ(G) = 2$. (van rá gyors algoritmus)
• a) $χ(G)=?$ van algoritmus, exponenciálisan lassú
• b) $χ(G)=k$ $(k≥ 3)$, $|V|=n, F:V→1,2,…,k$ véges sok
• b,a NP-teljes, állítás: $χ(G) ≤ ∆(G) + 1, ∆ = maxδ(v), v ∈ V$

Question 4

Mohó algoritmus (az erdő és fák témakörében)

Answer 4

Kruskál ≈ Prim algoritmusa:

• Minimális költségű feszítőfa keresésére tetszőleges G súlyozott élű összefüggő gráfban. Legyen tehát $G=(V,E)$ egy tetszőleges (nem feltétlen egyszerű) súlyozott élű gráf a $W:E→ R^+$ súlyfüggvénnyel.
  Lépésenként konstruálunk:
  $T_1 \nsubseteq T_2 \nsubseteq … \nsubseteq T_{n−1} \nsubseteq G$
  részgráfokat G-ben úgy, hogy Ti mindig fa (összefüggő és körmentes) legyen: START:T1 legyen G minimális súlyú éle, azaz T_1 : {e1} ahol e1 ∈ E és w(e1) minimá CIKLUS: Ha Ti már adott, akkor $T_{i+1}$ legyen a következő: olyan $e_{i+1}$ élét keressük meg G-nek, melyet $T_i$-hez csatolva összefüggő és körmentes részgráfokat kapnánk és ei+1 az ilyen tulajdonságú élek között minimális súlyú. Ekkor csatoljuk hozzá az ei+1 élt, azaz legyen
  $T_{i+1} := T_i ∪ {e_{i+1}}.$
  Mohó algoritmus, vagyis mindig a lokális minimumot választja. (Ez Prim algoritmusa, a szakirodalom gyakran egy hasonlót nevez Kruskalnak, a könyvnek a fejezet címe Kruskal algoritmus, de a Prim-et írja le…)

Question 5

Brooks tétele:

Answer 5

Tetszőleges G összefüggő gráfra, ami nem páratlan kör és nem teljes gráf, igaz a
$χ(G) ≤ D(G)$
becslés.
$(D(G): G$ csúcsainak maximális fokszáma)

Question 6

NP teljes probléma (6. tétel környékén is):

Answer 6

NP(Nondeterministic polinomial) teljes egy probléma, ha a következő igaz rá: “ha erre a problémára lenne gyors algoritmus, akkor a világ összes problémájára lenne gyors algoritmus”.
Hamilton körök keresése NP teljes probléma, csak $O(2^n)$ lassú algoritmusok ismertek rá. De van algoritmus Hamilton utakra.

Question 7

Őt- és négyszíntétel

Answer 7

Ötszín tétel:

• Minden síkba rajzolható gráf kromatikus száma legfeljebb 5.
• Bármely síkba rajzolható gráf csúcsai színezhetők legfeljebb öt színnel.
• Biz.: Heawood, 1890, indukción alapul, és a síkba rajzolható gráfok speciális tulajdonságait használja ki.
• Gyengébb de könnyebben bizonyítható tétel.

Négyszín tétel:

• Minden síkba rajzolható gráf kromatikus száma legfeljebb 4.
• Biz.: 1976-ban Kenneth Appel és Wolfgang Haken számítógépes segédlettel.

A négyszín tétel és a Kuratoswki tétel egy kombinációja a következő: “Ha egy gráf nem színezhető ki 4 színnel, akkor tartalmaz $K_5$ vagy $K_{3,3}$ részgráfot minorként.”