احاطه گری

تعریف

زیر مجموعه \(D\) از مجموعه رئوس گراف \(G\) را مجموعه احاطه‌گر می‌نامیم هر گاه هر رأس از گراف با در \(D\) باشد یا حداقل با یکی از رئوس \(D\) مجاور باشد.

مثال:

مجموعه‌های زیر مجموعه احاطه‌گری برای گراف زیر هستند.

\[\left\{a,c,e,f,g\right\}\ \] \[\left\{a,,b,c,d,e,f,g,h\right\}\ \] \[\left\{c,d,h\right\}\ \] \[\left\{b,f\right\}\ \]