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: a legnagyobb független élhalmaz elemszáma a legkisebb lefogó ponthalmaz elemszáma a legkisebb lefogó élhalmaz elemszáma pedig a legnagyobb független ponthalmaz elemszáma.

Lefogó és független ponthalmaz viszonya

Minden hurokmentes gráfra , 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 halmaz pontjai pontosan akkor függetlenek, ha lefogó halmaz. Egyébként, ha nem lenne független, akkor lenne két összekötött pont, amely közötti élet nem fogna le. A másik irányban, ha nem fogna le egy élet, akkor -ban ennek az élnek mindkét végpontja szerepel, tehát nem független. Ebből: , és innen . Ezentúl, -re ahol egy tetszőleges lefogó ponthalmaz. Tehát:

Független és lefogó élhalmaz viszonya Minden olyan gráfra, amely nem tartalmaz izolált pontot, , 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 darab független él pontot fog le. A többi pont legfeljebb éllel lefogható. Tehát, . Azt is tudjuk, hogy ha egy minimális lefogó élhalmaz, akkor darab csillagból áll (ha tartalmazna kört, annak tetszőleges élét, vagy ha utat, annak középső élét elhagyhatnánk). Ezért ( darab csillag van). Ebből kaphatunk úgy egy független élhalmazt, hogy minden csillagból kiválasztunk egy élet. Tehát .

+minmaxeredményponthalmaz +=|V(G)|élhalmaz +=|V(G)|

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

Kategória:Gráfelmélet Kategória:Gráfelméleti tételek