Gallai-tétel

Ez a szócikk a gráfelméleti tételről szól. A síkgeometriai tételt lásd a Sylvester–Gallai-tétel szócikkben.

A gráfelméletben a Gallai-tétel a független, illetve a lefogó pont- és élhalmazok között mond ki összefüggéseket. A tétel Gallai Tibortól származik.

Független és lefogó halmazok

Független élhalmaznak nevezzük egy gráf éleinek olyan halmazát, amelyben semelyik két élnek nincs közös pontja. Független ponthalmaznak pedig a pontok olyan halmazát, amelyben semelyik két pont nincs közös élen.

A gráf pontjainak egy halmaza lefogó ponthalmaz, ha a gráf minden élének legalább az egyik végpontját tartalmazza; hasonlóan, élek egy halmaza lefogó élhalmaz, ha a gráf minden pontjára legalább egy eleme illeszkedik.

Az alábbi jelölések használatosak a lényeges él-, illetve ponthalmazok elemszámára:

$\nu (G)$ a legnagyobb független élhalmaz elemszáma
$\tau (G)$ a legkisebb lefogó ponthalmaz elemszáma
$\rho (G)$ a legkisebb lefogó élhalmaz elemszáma
$\alpha (G)$ pedig a legnagyobb független ponthalmaz elemszáma.

Lefogó és független ponthalmaz viszonya

Minden hurokmentes $G$ gráfra $\tau (G)+\alpha (G)=|V(G)|$ , azaz a legkisebb lefogó és a legnagyobb független ponthalmaz elemszámának összege egyenlő a gráf pontjainak számával.

Bizonyítás

Az $A$ halmaz pontjai pontosan akkor függetlenek, ha $V(G)\setminus A$ lefogó halmaz. Egyébként, ha $A$ nem lenne független, akkor lenne két összekötött pont, amely közötti élet $V(G)\setminus A$ nem fogna le. A másik irányban, ha $V(G)\setminus A$ nem fogna le egy élet, akkor $A$ -ban ennek az élnek mindkét végpontja szerepel, tehát $A$ nem független. Ebből: $\tau (G)$ $\leq$ $|V(G)\setminus A|$ , és innen $\tau (G)+\alpha (G)$ $\leq$ $|V(G)|$ . Ezentúl, $\alpha (G)$ $\geq$ $|V(G)\setminus B|$ -re ahol $B$ egy tetszőleges lefogó ponthalmaz. Tehát: $\tau (G)+\alpha (G)$ $\geq$ $|V(G)|$

Független és lefogó élhalmaz viszonya

Minden olyan $G$ gráfra, amely nem tartalmaz izolált pontot, $\nu (G)+\rho (G)=|V(G)|$ , azaz a legnagyobb független és a legkisebb lefogó élhalmaz elemszámának összege egyenlő a gráf pontjainak számával.

Bizonyítás

$\nu (G)$ darab független él $2\nu (G)$ pontot fog le. A többi pont legfeljebb $|V(G)|-2\nu (G)$ éllel lefogható. Tehát, $|V(G)|-\nu (G)$ $\geq$ $\rho (G)$ . Azt is tudjuk, hogy ha $A$ egy minimális lefogó élhalmaz, akkor $A$ $k$ darab csillagból áll (ha $A$ tartalmazna kört, annak tetszőleges élét, vagy ha utat, annak középső élét elhagyhatnánk). Ezért $\rho (G)=|V(G)|-k$ ( $k$ darab csillag van). Ebből kaphatunk úgy egy független élhalmazt, hogy minden csillagból kiválasztunk egy élet. Tehát $\nu (G)$ $\geq$ $k=|V(G)|-\rho (G)$ .