Lefogó ponthalmaz | mateking
 

Lefogó ponthalmaz

Egy $G$ gráfban a $T \subset V(G)$ ponthalmaz lefogó ponthalmaz, ha $G$ minden élének legalább az egyik végpontja $T$-ben van.

Egy gráfban a minimális méretű lefogó ponthalmaz elemszámát $\tau(G)$-vel jelöljük.

A maximális lefogó ponthalmaz pedig a gráf összes csúcsa, és elemszáma éppen $ \mid V(G) \mid = n $.