Gráfparaméterek, párosítások

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.

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 \)

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 $.

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.

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 \)

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.

\( \alpha(G) \leq \rho(G) \quad \nu(G) \leq \tau(G) \)

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.

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

Azokat a párosításokat nevezzük teljes párosításoknak, ami a gráf összes csúcsát lefedi.

Egy $G$ gráf akkor és csak akkor páros, ha minden $G$-ben szereplő kör páros hosszúságú.

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.