مرجع کلمات و اصطلاحات اختصاری

درخت پوشای کمینه یا درخت فراگیر مینیمم در گراف‌های ارزش دار (وزن دار) ساخته می‌شود.

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

در مسائلی که هدف ایجاد شبکه‌ای است که برای ایجاد ارتباط بین هر دو عضو آن هزینه‌ای باید بپردازیم و می‌خواهیم در نهایت در این شبکه بین هر دو عضو ارتباط وجود داشته باشد، درخت پوشای کمینه همان کم هزینه‌ترین شبکه است. برای مثال فرض کنید در کشوری می‌خواهیم طوری جاده‌سازی کنیم که بتوان از هر شهری به هر شهر دیگری سفر کرد و هزینه ساخت جاده بین هر دو شهر را داریم(این هزینه می‌تواند تابعی بر اساس فاصله ۲ شهر، آب و هوای بین دو شهر فاصله آنها از شرکت راه‌سازی و … باشد). برای پیدا کردن کم هزینه ترین راه، باید درخت پوشای کمینه را بیابیم.

در الگوریتم کراسکال یال‌های گراف را به ترتیب صعودی مرتب می کنیم. از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد. این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.

این الگوریتم نیزمشابه الگوریتم پریم برای یافتن درخت پوشای کمینه ی یک گراف به کارمی رود.دراین الگوریتم ابتدایال هاازکمترین وزن به بیشترین وزن مرتب می گردندسپس یال هابه ترتیب انتخاب شده واگریالی ایجادحلقه کندوکنارگذاشته می شود.عملیات هنگامی خاتمه می یابدکه تمام رأس هابه هم وصل شوند یااینکه تعداد یال های موجود در F برابر n-1 شود که n تعداد رأس ها است. که در بعضی کتابها با نام راشال مطرح شده است.

ارسال نظر