- 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
Gráfparaméterek, párosítások
Független ponthalmaz
A független ponthalmaz precíz definíciójára mindjárt kettő is van.
Íme az egyik:
Egy $G$ gráfban független csúcshalmaznak nevezzük a csúcsoknak az $A \subset V(G)$ részhalmazát, ha nincs olyan él, amelynek mindkét végpontja $A$-ban van.
És itt jön a másik:
Egy $G$ gráfban független csúcshalmaznak nevezzük a csúcsoknak az $A \subset V(G)$ részhalmazát, ha az $A$ által feszített részgráf nem tartalmaz élt.
Egy $G$ gráfban a független csúcsok maximális számát $\alpha(G)$-vel jelöljük.
Gallai első tétele
Ha vesszük egy gráfban a maximális számú független pontokat és a minimális számú lefogó pontokat, akkor épp megkapjuk a gráf összes pontját.
Ezt hívjuk első Gallai tételnek:
\( \tau(G) + \alpha(G) = n \)
Lefogó ponthalmaz
Egy $G$ gráfban a $T \subset V(G)$ ponthalmaz lefogó ponthalmaz, ha $G$ minden élének legalább az egyik végpontja $T$-ben van.
Egy gráfban a minimális méretű lefogó ponthalmaz elemszámát $\tau(G)$-vel jelöljük.
A maximális lefogó ponthalmaz pedig a gráf összes csúcsa, és elemszáma éppen $ \mid V(G) \mid = n $.
Független élhalmaz
Egy $G$ gráf éleinek $M$ részhalmaza független élhalmaz, ha $M$ semelyik két elemének nincs közös végpontja.
Egy gráf független éleinek maximális számát $\nu(G)$-vel jelöljük.
Gallai második tétele
Ha vesszük egy gráfban a minimális számú lefogó éleket, és a maximális számú független éleket, akkor a gráf minden pontjához pontosan egy él fog tartozni.
Ez Gallai második tétele:
Ha egy $n$ csúcsú gráf nem tartalmaz izolált pontot, akkor
\( \rho(G) + \nu(G) = n \)
Lefogó élhalmaz
Egy $G$ gráf éleinek $R$ részhalmaza lefogó élhalmaz, ha a gráf minden csúcsa valamelyik $R$-beli él végpontja.
Egy $G$ gráfban a lefogó élek minimális számát $\rho(G)$-vel jelöljük.
Gráfparaméterek közti összefüggések
\( \alpha(G) \leq \rho(G) \quad \nu(G) \leq \tau(G) \)
Párosítás
Egy $G$ gráfban az $E(G)$ élhalmaznak egy $M$ részhalmazát párosításnak nevezzük, ha $M$ semelyik két elemének nincs közös végpontja.
Párosítás javító útja
Egy $G$ gráfban az $e_1, e_2, e_3, \dots , e_n$ élsorozat az $M$ párosítás javító útja, ha
1) a megadott élsorozat egy páratlan hosszú út $G$-ben
2) az élek felváltva elemi $M$-nek:
$ e_{2k} \in M$ és $e_{2k+1} \notin M $
3) az út kezdő és végpontja nem illeszkedik semelyik $M$-beli élre sem
Teljes párosítás
Azokat a párosításokat nevezzük teljes párosításoknak, ami a gráf összes csúcsát lefedi.
Tétel páros gráfokra
Egy $G$ gráf akkor és csak akkor páros, ha minden $G$-ben szereplő kör páros hosszúságú.
Tutte-tétel
Egy gráfban akkor és csakis akkor létezik teljes párosítás, ha bárhogyan hagyunk el a gráfból néhány pontot, a megmaradt gráfban a páratlan komponensek száma nem több az elhagyott pontok számánál.