احاطه‌گر مینیمال

احاطه‌گر مینیمال

تعریف

مجموعه ای احاطه‌گر که با حذف هر یک از رئوسش دیگر احاطه‌گر نباشد.

نکات

یک مجموعه احاطه‌گر مینیمم حتما یک مجموعه احاطه‌گر مینیمال است. اما یک مجموعه احاطه‌گر مینیمال لزوما یک مجموعه احاطه‌گر مینیمم نیست.

می‌توان هر مجموعه احاطه‌گر دلخواه غیر مینیمال را با حذف برخی رئوس به یک مجموعه احاطه‌گر مینیمال تبدیل کرد.

مثال

مجموعه \(\left\{a,b,d,e,f,g\right\}\ \)  یک مجموعه احاطه‌گر است ولی مینیمال نیست چون می‌توان رأس \(b\) را حذف کرد ولی به احاطه‌گری مجموعه ایرادی وارد نشود. با حذف رأس  \(b\) به مجموعه\(\left\{a,d,e,f,g\right\}\ \)   می‌رسیم، حال رأس \(f\) را حذف می‌کنیم تا به مجموعه احاطه‌گر مینیمال\(\left\{a,d,e,g\right\}\ \)  برسیم.