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 é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:

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

Minden hurokmentes ${\displaystyle G}$ gráfra ${\displaystyle \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.

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

Minden olyan ${\displaystyle G}$ gráfra, amely nem tartalmaz izolált pontot, ${\displaystyle \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.

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

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

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