- Kombinatorika
- Gráfelméleti alapok
- Gráfok bejárása és gráfalgoritmusok
- Gráfok izomorfiája és síkbarajzolhatósága
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Menger tételei, többszörös összefüggőség
- CPM és PERT algoritmus
- Páros gráfok, párosítások
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák
- Maximális folyam, Ford-Fulkerson-algoritmus
Kromatikus szám, klikk, perfekt gráfok
Kromatikus szám
A legkevesebb színt, amivel egy gráf csúcsait kiszinezhetjük úgy, hogy a szomszédos csúcsok ne legyenek egyforma színűek, a gráf kromatikus számának nevezzük.
Jele: $\chi (G)$.
Klikk
Egy $G$ egyszerű gráfban klikknek nevezzük azokat a részgráfokat, amelyek teljes gráfok.
Klikkszám
Egy gráf klikkszáma a gráfban található maximális klikk elemszáma.
A $G$ gráf klikkszámát $\omega (G)$-vel jelöljük.
Minden gráfban a klikkszám alsó becslés a kromatikus számra:
\( \omega (G) \leq \chi (G) \)
Feszített részgráf
A $G$ gráfban a $G'$ részgráf feszített részgráf, ha bármely két csúcs a $G'$ gráfban pontosan akkor szomszédos, ha $G$-ben is szomszédos.
Perfekt gráf
Ha egy $G$ gráf minden $G'$ feszített részgráfjára igaz, hogy
\( \omega (G') = \chi (G') \)
akkor a $G$ gráfot perfekt gráfnak nevezzük.
Ha egy gráf perfekt, akkor a kromatikus száma egyenlő a klikkszámával. Az állítás fordítva nem igaz, abból, hogy $\omega (G') = \chi (G')$ még nem következik, hogy a gráf perfekt.
Kromatikus szám alsó és felső becslése
\( \omega(G) \leq \chi(G) \leq \Delta(G) + 1 \)
ahol $\omega(G)$ a gráf klikkszáma, $\chi(G)$ a kromatikus száma és $\Delta(G)$ a maximális fokszáma.
Mohó színezés
A mohó színezés egy algoritmus a gráfok színezésére.
Lényege, hogy sorba rakjuk a gráf csúcsait, és elkezdjük színezni úgy, hogy minden csúcs színezéséhez a lehető legkisebb sorszámú színt használjuk. Ezt addig folytatjuk, amíg az összes csúcs ki nem lesz színezve, és így elhasználunk legfeljebb $\Delta(G)+1$ darab színt.
Brooks-tétel
Ha $G$ nem teljes gráf, vagy páratlan csúcsú kör, akkor
\( \chi(G) \leq \Delta(G) \)
Élkromatikus szám
Egy $G$ gráfban azt a legkisebb számot, amire a gráfnak már van jó élszínezése, a $G$ gráf élkromatikus számának nevezzük.
Jele: $\chi_e$
Vizing-tétel
A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést:
\( \Delta(G) \leq \chi_e(G) \leq \Delta(G) + 1 \)
Vagyis a $G$ egyszerű gráfok két osztályba sorolhatók:
Első osztály: $\chi_e(G) = \Delta(G)$
Második osztály: $\chi_e(G) = \Delta(G)+1 $
Intervallumgráfok
Az intervallumgráf egy olyan gráf, melynek csúcsai megfeleltethetőek a valós számok egy-egy intervallumának, és két csúcs között akkor vezet él, ha a nekik megfeleltethető két intervallum metszete nem üres.
Az intervallumgráfok mindig perfekt gráfok.
Páros gráf
Egy $G$ gráfot páros gráfnak nevezünk, ha csúcsainak a $V(G)$ halmaza felbontható az $A$ és $B$ diszjunkt részhalmazokra, úgy hogy $A$-n és $B$-n belül nem vezetnek élek.
A páros gráfok kromatikus száma 2, élkromatikus számukra pedig König Dénesnek van egy remek tétele:
Ha $G$ páros gráf, akkor $ \chi_e(G) = \Delta(G) $
Mycielski-gráfok
Jan Mycielski lengyel matematikust nyugtalanította az a kérdés, hogy léteznek-e olyan gráfok, amelyeknek a kromatikus száma nagyon nagy, de a klikkszáma csak 2.
Létrehozott egy konstrukciót, amivel olyan gráfokat lehet alkotni, amelyek klikkszáma 2, a kromatikus számuk pedig bármilyen nagy lehet. Ezeket a gráfokat Mycielski-gráfoknak nevezzük.