مجموعه راس پس خورد

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

درقوانینریاضی ازنظریه گراف،یک مجموعه راس پس خورد از یک گراف،مجموعه ای از رئوسی است که برداشتن آن هاگراف رابدون دور باقی می گذارد.به عبارت دیگر،هرمجموعه راس پس خورد شمال حداقل یک راس در هردوری از گراف می باشد. مساله مجموعه راس پس خورد یک مساله NP کامل درنظریه ی پیچیدگی محاسباتی می باشد.این مساله در میان اولین مسائل نشان داده شده در NP کامل است.این مساله کاربرد وسیعی در سیستم های عامل،سیستم های پایگاه داده،مونتاژژنوم،و طراحی چیپ وی‌ال‌اس‌آی دارد.

تعریف[ویرایش]

مساله تصمیم گیری به این صورت است:

نمونه:یک گراف(جهت دار یا بدون جهت)G = (V, E) و یک عدد صحیح مثبت k.
سوال: آیا یک زیرمجموعه X \subseteq V با |X| \leq k وجوددارد چنان چه G بارئوس پاک شده‌ای از Xبدون دور باشد؟

گراف G[V \setminus X] که بعد از برداشتن Xاز G باقی می ماند یک جنگل مشتق است.(یک گراف بدون دور جهت دار در مورد گراف های جهت دار).بنابراین ،پیداکردن یک مجموعه راس پس خوردکمینه دریک گراف برابر باپیداکردن یک جنگل مشتق بیشینه است.(گراف بدون دور جهت دار مشتق بیشینه درمورد گراف های جهت دار).

سختی NP[ویرایش]

Karp (1972) نشان دادکه مساله مجموعه راس پس خورد برای گراف های جهت دار، NP-کامل است.مساله NP-کامل روی گراف های جهت دار بادرجه ی ورودی و خروجی 2، وروی گراف های جهت دار دو طرفه با درجه داخلی و خارجی 2 باقی می ماند..[۱] کاهش کارپ همچنین کامل بودن NP مساله مجموعه راس پس خورد را روی گراف های بدون جهت ذکر می کند،جایی که مساله روی گراف هایی از بیشینه درجه 4 ،NP سخت باقی می ماند.مساله مجموعه راس پس خورد می تواند در زمان چندجمله ای روی گراف هایی از حداکثر درجه 3 حل شود. توجه کنید مساله پاک کردن یال ها برای ایجاد گراف بدون دور معادل است با پیدا کردن یک درخت پوشای کمینه،که می تواند در زمان چندجمله ای انجام شود.در تضاد بااین،مساله پاک کردن یال ها از یک گراف جهت دار برای بدون دور کردنش،مسالع یال های پس خورد،NP-کامل است،Karp (1972) را ببینید.

الگوریتم های دقیق[ویرایش]

مساله بهینه سازی NP متناظر با پیداکردن یک مجموعه راس پس خورد کمینه می تواند در زمانO(1.7347n), حل شود،جایی که n تعداد رئوس گراف است..[۲]این الگوریتم در واقع یک جنگل مشتق شده بیشینه را محاسبه می کند،و و قتی که جنگلی به دست آمد، مکمل آن مجموعه راس پس خورد کمینه است.تعداد مجموعه های راس پس خورد در یک گراف به وسیله ی O(1.8638n).[۳]محدود می شود.مساله راس پس خورد جهت دار هنوز می تواند در زمان O*(1.9977n), حل شود،جایی که  n تعداد رئوس در گراف جهت دار داده شده است..[۴]نسخه پارامتری شده از مسائل جهت دار و بدون جهت ،هر دو غیر بغرنج باپارامتر ثابت هستند.[۵]

تخمین[ویرایش]

مساله APX-کامل است،که مستقیماً به دنبال کامل بودن APX از مساله پوشش راس می آید[۶] و وجود یک حفظ تقریبی کاهش L از مساله پوشش راس که برای آن می آید.[۷]معروفترین تخمین روی گراف های بدون جهت به وسیله ی یک عامل دو است.[۸]

محدوده ها[ویرایش]

مطابق با نظریه Erdős–Pósa اندازه مجموعه راس پس خورد کمینه در داخل یک عامل لگاریتمی از حداکثر تعداد رئوس غیرمرتبط دور ها در گراف داده شده است.

کاربردها[ویرایش]

در سیستم های عامل ،مجموعه راس پس خورد نقشی برجسته در مطالعه بازیابی بن بست بازی می کند.در به انتظار نشستن برای گراف از یک سیستم عامل،هردور جهت دار متناظر با یک موقعیت بن بست است.به منظور حل کردن همه ی بن بست ها،بعضی از فرایند های مسدود شده باید کنارگذاشته شوند.یک مجموعه راس پس خورد در این گراف متناظر است با یک حداقل تعداد از فرایند هایی که احتیاج به کنارگذاشته شدن دارد(Silberschatz & Galvin 2008). علاوه براین،مساله مجموعه راس پس خورد،کاربردهای فراوانی درطراحی چیپ وی‌ال‌اس‌آی (cf. Festa, Pardalos & Resende (2000)) و مونتاژژنوم دارد.

یادداشت ها[ویرایش]

  1. unpublished results due to Garey and Johnson, cf. Garey & Johnson (1979): GT7
  2. Fomin & Villanger (2010)
  3. Fomin et al. (2008)
  4. Razgon (2007)
  5. Chen et al. (2008)
  6. Dinur &amp Safra 2005
  7. Karp (1972)
  8. Becker & Geiger (1996)

منابع[ویرایش]

مقالات تحقیقی[ویرایش]

کتاب های درسی و مقالات مطالعاتی[ویرایش]

  • P. Festa, P.M. Pardalos, and M.G.C. Resende, Feedback set problems, Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos, Eds., Kluwer Academic Publishers, Supplement vol. A, pp. 209–259, 2000. author's version (pdf)
  • Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5