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:
- 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 .
min | max | eredmény | |||
---|---|---|---|---|---|
ponthalmaz | + | = | |V(G)| | ||
élhalmaz | + | = | |V(G)| |
Hivatkozások
- Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 59,60.
Matematikaportál • összefoglaló, színes tartalomajánló lap