پوشش گرهی کیست؟ توضیح بده.
در نظریه گراف ، پوشش راسی ( پوشش گره‌ای ) در یک گراف ، زیرمجموعه ای از رئوس است که که همهٔ یال‌های این گراف را می‌پوشاند. در این جا پوشش یک یال یعنی آن که دست کم یکی از گره‌های دو سر یال در این زیرمجموعه باشد. اندازهٔ پوششی گره‌ای برابر است با شمار گره‌های درون این مجموعه. برای نمونه، شکل زیر دارای یک پوشش گره‌ای ، به اندازهٔ ۲ است.پرسمان یافتن پوشش گره‌ای کمینه به یافتن پوششی گره‌ای می‌پردازد که کم‌ترین شمار گره‌ها را دربرداشته باشد. این پرسمان ان‌پی کامل است، از این روی رایانش چنین زیرمجموعه‌ای دشوار است .این مسئله در علوم کامپیوتر ، یک مسئله بهینه سازی کلاسیک است. پس این پرسمان NP-سخت است درنتیجه اگر P ≠ NP باشد، نمی توان آن را با یک الگوریتم زمان چند جمله ای حل کرد. علاوه بر این، تخمین زدن آن دشوار است - اگر حدس بازی های منحصر به فرد درست باشد، نمی توان آن را تا ضریب کوچکتر از 2 تقریب زد.تعریف.برای گرافی بی‌سو مانند formula_1، زیرمجموعه‌ای formula_2 پوشش گره‌ای است اگر برای هر یال formula_3 یا گره formula_4 یا گرهٔ formula_5 یا formula_6 باشد. دو پوشش گره‌ای با رنگ قرمز در شکل‌های زیر نمایانیده شده‌اند.اندازهٔ پوششی گره‌ای مانند formula_7 برابر است با شمار گره‌های این زیرمجموعه که با formula_8 نمایش داده می‌شود. پوشش گره‌ای کمینه پوششی است که دارای کم‌ترین گره‌ها باشد. گره‌های سرخ در در دو شکل زیر پوشش گره‌ای کمینه را برای نمونه‌های بالا می‌نمایانند.پرسمان‌های رایانشی.پرسمان پوشش گره‌ای کمینه پرسمانی بهینه‌سازی است که به یافتن پوششی گره با کمترین اندازه برای یک گراف می‌پردازد. اگر گره‌ها وزن‌دار باشند، پوشش گره‌ای وزن‌دار کمینه زیرمجموعه‌ای از گره‌هاست که کمترین وزن را روی-هم-رفته داشته باشند.پرسمان پوشش گره‌ای پرسمانی تصمیم‌گیری است: آیا پوشش گره‌ای با اندازه‌ای دست بالا formula_11 در گرافی هست.پرسمان پوشش گرهٔ ان‌پی کامل و یکی از پرسمان‌های ۲۱ پرسمان ان‌پی-کامل کارپ است.برنامه‌نویسی درست.برای برنامه‌نویسی درست، اگر هر گرهٔ formula_12 در گراف formula_13 وزن formula_14 دربرداشته باشد، پرسمان پوشش گره‌ای مانند برنامهٔ درست (integer program) زیر نوشته می‌شود:formula_15بنداشت‌ها:formula_16formula_17گافِ دُرُست (integral gap) برای این برنامه، ۲ است؛ بنابراین، واهلش این برنامه تقریبی با کروند (فاکتور)-۲ برای پرسمان پوشش گره‌ای کمینه به دست خواهد داد. هم‌چنین، واهلش برنامهٔ درست بالا نیم-دُرُست (half integral) است؛ از این روی، در یک پاسخ بهین، هر درآیهٔ formula_18 ارزش formula_19 یا formula_20 یا formula_21 (optimal) خواهد داشت.الگوریتم رزین.پرسمان پوشش گره‌ای ان‌پی کامل است. از این روی، الگوریتمی دقیق با زمانی بهینه برای این پرسمان نخواهیم داشت. ریچارد کارپ ان‌پی کامل بودن این پرسمان را با کاهش از پرسمان گروهک نشان داده است. پرسمان پوشش گره‌ای حتی برای گراف مکعبی و گراف مسطح با درجهٔ کم‌تر از ۳ ان‌پی کامل می‌ماند.کونیگ نشان داده است که پوشش گره‌ای کمینه و جورسازی بیشینه در گرافی دوبخشی هم‌ارز هستند. از این روی می‌توان پاسخ بهین را در زمانی چندجمله‌ای به دست آورد.هم‌چنین، پاسخ بهین را برای درخت‌ها می‌توان در زمانی چندجمله‌ای یافت.الگوریتم تقریب.البته در ادامه الگوریتم تقریب زیر را برای این مسئله بیان می‌داریم. الگوریتم، گراف بدون جهت formula_22 را به عنوان ورودی می‌گیرد و یک پوشش گرهٔ را برمی‌گرداند که تضمین می‌شود اندازه آن بیش از دو برابر پوشش گرهٔ بهینه نیست:formula_23formula_24formula_25formula_26formula_27formula_28formula_29formula_30الگوریتم.شکل ۲ عملکرد- formula_23 را تشریح می‌کند. متغیر formula_32 حاوی پوشش گرهٔ در حال ساخت است. خط ۱، formula_32 را برابر با مجموعه تهی قرار می‌دهد. خط ۲ ، formula_34 را برابر با کپی مجموعه یال formula_35 گراف قرار می‌دهد. حلقه در خطوط ۳ تا ۶ مکرراً یالformula_36 را از formula_34 انتخاب می‌کند، نقاط انتهای آن formula_38 و formula_39 را به formula_32 اضافه می‌کند، و تمام یال‌هایی را از formula_34 حذف می‌کند که توسط formula_38 یا formula_39 پوشش می‌شود. زمان اجرای الگوریتم formula_44 است که از لیست همجواری برای نمایش formula_34 استفاده می‌شود.