پوشش گره‌ای

پوشش گره‌ای برای یک گراف زیرمجموعه‌ای از گره‌هاست که همهٔ یال‌های این گراف را می‌پوشاند. در این جا پوشش یک یال یعنی آن که دست کم یکی از گره‌های دو سر یال در این زیرمجموعه باشد. اندازهٔ پوششی گره‌ای برابر است با شمار گره‌های درون این مجموعه. برای نمونه، در شکل ۱ ${\displaystyle (b)}$ دارای پوشش گره ${\displaystyle \left\{w,z\right\}}$ به اندازهٔ ۲ است.

پرسمان پوشش گره‌ای کمینه به یافتن پوششی گره‌ای می‌پردازد که کم‌ترین شمار گره‌ها را دربرداشته باشد. این پرسمان ان‌پی کامل است، از این روی رایانش چنین زیرمجموعه‌ای دشوار است.

تعریف

برای گرافی بی‌سو مانند ${\displaystyle G=(V,E)}$، زیرمجموعه‌ای ${\displaystyle V'\subseteq V}$ پوشش گره‌ای است اگر برای هر یال ${\displaystyle (u,v)\in E}$ یا گره ${\displaystyle v\in V'}$ یا گرهٔ ${\displaystyle u\in V'}$ یا ${\displaystyle \{u,v\}\subseteq V^{'}}$ باشد. دو پوشش گره‌ای با رنگ قرمز در شکل‌های زیر نمایانیده شده‌اند.

اندازهٔ پوششی گره‌ای مانند ${\displaystyle V^{'}}$ برابر است با شمار گره‌های این زیرمجموعه که با ${\displaystyle |V^{'}|}$ نمایش داده می‌شود. پوشش گره‌ای کمینه پوششی است که دارای کم‌ترین گره‌ها باشد. گره‌های سرخ در در دو شکل زیر پوشش گره‌ای کمینه را برای نمونه‌های بالا می‌نمایانند.

نمونه‌ها

• مجموعهٔ همهٔ گره‌ها پوشش گره‌ای است.
• گره‌های تطابق (گراف) بیشینه‌ای یک پوشش گره‌ای را می‌سازند.
• گراف دوبخشی کامل ${\displaystyle K_{m,n}}$ دارای پوششی گره‌ای کمینه با اندازه ${\displaystyle \min(m,n)}$ است.

ویژگی‌ها

• مجموعه‌ای از گره‌ها پوششی گره‌ای است اگر و تنها اگر اُسپُران (مکمل) آن مجموعه ناوابسته باشد.
• شمار گره‌های گرافی برابر است با اندازهٔ پوشش گره‌ای کمینه و اندازهٔ مجموعهٔ ناوابسته بیشینهٔ این گراف (Gallai).

پرسمان‌های رایانشی

پرسمان پوشش گره‌ای کمینه پرسمانی بهینه‌سازی است که به یافتن پوششی گره با کمترین اندازه برای یک گراف می‌پردازد. اگر گره‌ها وزن‌دار باشند، پوشش گره‌ای وزن‌دار کمینه زیرمجموعه‌ای از گره‌هاست که کمترین وزن را روی-هم-رفته داشته باشند.

پرسمان پوشش گره‌ای پرسمانی تصمیم‌گیری است: آیا پوشش گره‌ای با اندازه‌ای دست بالا ${\displaystyle k}$ در گرافی هست.

پرسمان پوشش گرهٔ ان‌پی کامل و یکی از پرسمان‌های ۲۱ پرسمان ان‌پی-کامل کارپ است.

برنامه‌نویسی درست

برای برنامه‌نویسی درست، اگر هر گرهٔ ${\displaystyle v\in V}$ در گراف ${\displaystyle G(V,E)}$ وزن ${\displaystyle c(v)\geq 0}$ دربرداشته باشد، پرسمان پوشش گره‌ای مانند برنامهٔ درست (integer program) زیر نوشته می‌شود:

${\displaystyle \min {\sum _{v\in V}{c(v)x_{v}}}}$

بنداشت‌ها:

${\displaystyle \forall \{u,v\}\in E:x_{u}+x_{v}\geq 1}$

${\displaystyle \forall v\in V:x_{v}\in \{0,1\}}$

گافِ دُرُست (integral gap) برای این برنامه، ۲ است؛ بنابراین، واهِلِش[1] (relaxation) این برنامه تقریبی با کروند (فاکتور)-۲ برای پرسمان پوشش گره‌ای کمینه به دست خواهد داد. هم‌چنین، واهلش برنامهٔ درست بالا نیم-دُرُست (half integral) است؛ از این روی، در یک پاسخ بهین، هر درآیهٔ ${\displaystyle x_{v}}$ ارزش ${\displaystyle 0}$ یا ${\displaystyle {\frac {1}{2}}}$ یا ${\displaystyle 1}$ (optimal) خواهد داشت.

الگوریتم رزین

پرسمان پوشش گره‌ای ان‌پی کامل است. از این روی، الگوریتمی رزین[2] (exact algorithm) با زمانی بهینه برای این پرسمان نخواهیم داشت. ریچارد کارپ ان‌پی کامل بودن این پرسمان را با کاهش از پرسمان گروهک نشان داده است. پرسمان پوشش گره‌ای حتی برای گراف مکعبی[3] و گراف مسطح[4] با درجهٔ کم‌تر از ۳ ان‌پی کامل می‌ماند.

کونیگ نشان داده است که پوشش گره‌ای کمینه و جورسازی بیشینه در گرافی دوبخشی هم‌ارز هستند. از این روی می‌توان پاسخ بهین را در زمانی چندجمله‌ای به دست آورد.

هم‌چنین، پاسخ بهین را برای درخت‌ها می‌توان در زمانی چندجمله‌ای یافت.[5]

الگوریتم تقریب

البته در ادامه الگوریتم تقریب زیر را برای این مسئله بیان می‌داریم. الگوریتم، گراف بدون جهت ${\displaystyle G}$ را به عنوان ورودی می‌گیرد و یک پوشش گرهٔ را برمی‌گرداند که تضمین می‌شود اندازه آن بیش از دو برابر پوشش گرهٔ بهینه نیست:

${\displaystyle Approx-Vertex-Cover}$

${\displaystyle C\leftarrow \varnothing }$

${\displaystyle E'\leftarrow E\left[G\right]}$

${\displaystyle WhileE'\neq \varnothing }$

${\displaystyle \quad do\,let\,(u,v)\,be\,an\,arbitary\,edge\,of\,E'}$

${\displaystyle \quad C\leftarrow C\cup \left\{u,v\right\}}$

${\displaystyle \quad remove\,from\,E'\,every\,edge\,incident\,on\,either\,u\,or\,v}$

${\displaystyle return\,C}$

الگوریتم

شکل ۲ عملکرد- ${\displaystyle Approx-Vertex-Cover}$ را تشریح می‌کند. متغیر ${\displaystyle C}$ حاوی پوشش گرهٔ در حال ساخت است. خط ۱، ${\displaystyle C}$ را برابر با مجموعه تهی قرار می‌دهد. خط ۲ ، ${\displaystyle E'}$ را برابر با کپی مجموعه یال ${\displaystyle E\left[G\right]}$ گراف قرار می‌دهد. حلقه در خطوط ۳ تا ۶ مکرراً یال${\displaystyle (u,v)}$ را از ${\displaystyle E'}$ انتخاب می‌کند، نقاط انتهای آن ${\displaystyle u}$ و ${\displaystyle v}$ را به ${\displaystyle C}$ اضافه می‌کند، و تمام یال‌هایی را از ${\displaystyle E'}$ حذف می‌کند که توسط ${\displaystyle u}$ یا ${\displaystyle v}$ پوشش می‌شود. زمان اجرای الگوریتم ${\displaystyle O(V+E)}$ است که از لیست همجواری برای نمایش ${\displaystyle E'}$ استفاده می‌شود.

بازبُردها

1. «An Etymological Dictionary of Astronomy and Astrophysics - 1». dictionary.obspm.fr. دریافت‌شده در ۲۰۱۶-۰۴-۲۵.
2. «An Etymological Dictionary of Astronomy and Astrophysics - 1». dictionary.obspm.fr. دریافت‌شده در ۲۰۱۶-۰۴-۲۵.
3. Garey, Johnson & Stockmeyer 1974
4. Garey & Johnson 1977; Garey & Johnson 1979, pp. 190 and 195.
5. Schulz, A (CS Stack Exchange). "Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree". Retrieved 8 July 2014. Check date values in: |date= (help)

• معرفی بر الگوریتم‌ها en:CLRS
• معرفی بر الگوریتم‌ها ترجمه: جعفرنژاد قمی
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs، author: Demaine