پوشش راسی

تعریف

پوشش راس در گراف بدون جهت $G=(V,E) \!$، زیر مجموعه$V' \subseteq V$ است که اگر $(u,v) \in E$، آن گاه$v \in V'$ یا $u \in V'$ (یا هردو). یعنی، هر راس، یال‌های منطبق خود را پوشش می دهد، پوشش برای $G$، مجموعه ای از رئوس است که تمام یال‌ها را در $E$ پوشش می دهد. اندازه پوشش راس، برابر با تعداد رئوس موجود در آن است. به عنوان مثال، در شکل 1 $(b)$ دارای پوشش راس $\left \{ w , z \right \}$ به اندازهٔ 2 است.

الگوریتم حل مسئله

مسئله پوشش راس، یافتن پوشش راس با کمترین اندازه در یک گراف است. با بیان این مسئلهٔ بهینه سازی به صورت مسئله تصمیم گیری، می خواهیم تعیین کنیم آیا گراف دارای پوشش راسی به اندازهٔ $k$ هست یا خیر. تعریف زیر را به صورت یک زبان ارائه می کنیم.: گراف $G$ دارای پوشش راسی به اندازهٔ $k$ است : $Vertex - Cover \le <G,k>$

البته قابل ذکر است که مسئلهٔ پوشش راسی یک مسئله $NP$ کامل است. بدین جهت انتظار نداریم یک الگوریتم زمان چند جمله ای برای یافتن پوشش راسی با کمترین اندازه وجود داشته باشد.

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

$Approx-Vertex-Cover$

$C \leftarrow \varnothing$

$E' \leftarrow E \left [ G \right ]$

$While E' \neq \varnothing$

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

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

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

$return\,C$

تشریح الگوریتم

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

منبع

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