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

	min		max		eredmény
ponthalmaz	$\tau (G)$	+	$\alpha (G)$	=	|V(G)|
élhalmaz	$\rho (G)$	+	$\nu (G)$	=	|V(G)|

Hivatkozások

• Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 59,60.