مجموعه گره‌های بازخورد

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

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

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

نمونۀ تصمیمی مجموعه گره‌های بازخورد:

  • درون‌داد: گراف و عدد درست .
  • برون‌داد: آیا برداشتن گره از می‌تواند گراف را بدون دور کند؟

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

سختی 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 & 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