درخت پوشا و درخت پوشای کمینه

درخت پوشا زیرگرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ...ی از یک متصل بدون جهت است که شامل تمام رئوس نمودار با حداقل تعداد ممکن یال است. در این مقاله به معرفی درخت پوشا و حداقل درخت پوشا می‌پردازیم.

درخت پوشا

یک درخت پوشا را می‌توان به عنوان زیرگراف یک گراف متصل بدون جهت تعریف کرد که شامل تمام رئوس به همراه کمترین تعداد ممکن یال است. اگر هر رأسی از قلم افتاده باشد، درخت پوشا نیست؛ در‌واقع درخت پوشا زیر مجموعه‌ای از گراف است که دور ندارد.

یک درخت پوشا شامل(n-1) یال است که در آن 'n' تعداد رئوس(یا گره‌ها) است. به یال‌های درخت پوشا ممکن است وزنی اختصاص داده شده باشد یا نباشد. همه‌ی درختان پوشای ممکن ایجاد شده از گراف G، دارای تعداد رئوس یکسانی هستند، اما تعداد یال‌های درخت پوشا برابر با تعداد رئوس در گراف، منهای 1 خواهد بود.

یک گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... کامل بدون جهت می‌تواند n^n-2 درخت پوشا داشته باشد که n تعداد رئوس نمودار است. اگر n = 5 باشد، حداکثر تعداد درختان پوشای ممکن 125= ^2-5⁵ خواهد بود. برخی از خواص درخت پوشا به شرح زیر است:

• می‌شود بیش از یک درخت پوشا از یک گراف متصل G وجود داشته باشد.
• درخت پوشا هیچ دور یا حلقه‌ای ندارد.
• یک درخت پوشا دارای حداقل تعداد یال است، بنابراین حذف یک یال از درخت باعث قطع ارتباط بین رئوس درخت می‌شود.
• درخت پوشا دارای حداکثر تعداد یال بدون دور است، بنابراین افزودن یک یال به درخت یک دور ایجاد می‌کند.
• حداکثر n^n-2 درخت پوشا می‌تواند وجود داشته باشد که می‌توان از یک گراف کامل با تعداد راس n ایجاد کرد.
• یک درخت پوشا دارای n-1 یال است که در آن 'n' تعداد گره‌ها است.
• اگر گراف یک گراف کامل باشد، درخت پوشا را می‌توان با حذف حداکثر (e-n+1) یال ساخت، که 'e' تعداد یال‌ها و 'n' تعداد رئوس است.

مثال

بیایید درخت پوشا را با مثال زیر درک کنیم:

فرض کنید گراف اصلی به صورت زیر باشد:

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

درخت پوشای کمینه

یک درخت پوشای کمینه را می‌توان به عنوان درخت پوشایی تعریف کرد که در آن مجموع وزن یال‌ها کمینه است. وزن درخت پوشا مجموع وزن‌هایی است که یال‌های درخت پوشا دارند.

مثال

بیایید تعریف فوق را با کمک مثال زیر درک کنیم.

فرض کنید گراف اولیه بصورت زیر باشد:

درختان پوشای ممکن از نمودار بالا عبارتند از:

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

الگوریتم‌ های پیدا کردن درخت پوشای کمینه

الگوریتم کروسکال

یک الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد حریصانه، برای یافتن درخت پوشای کمینه است که یک گراف را به عنوان ورودی می‌گیرد و زیرمجموعه یال‌های آن گراف را پیدا می‌کند. این ورودی، درختی را تشکیل می‌دهد که شامل هر رأس می‌شود، بصورتیکه وزن کل تمام یال‌های درخت به حداقل می‌رسد. این الگوریتم به این صورت کار می‌کند که یال‌های گراف را بر اساس وزن مرتب می‌کند، سپس یال با کمترین وزن را از گراف می‌گیرد و به درخت اضافه می‌کند. این روند تا زمانیکه تمام رئوس در درخت گنجانده شود تکرار می‌شود.

الگوریتم پریم

الگوریتم پریم نیز حریصانه است و درخت پوشای کمینه را برای یک گراف وزن‌دار بدون جهت پیدا می‌کند. این الگوریتم با یک گره شروع می‌شود و سپس کم‌وزن‌ترین یال را از آن گره به درخت اضافه می‌کند؛ درنهایت این فرآیند تا زمانی تکرار می‌شود که n-1 یال در درخت وجود داشته باشد، که n تعداد گره‌های نمودار است.

الگوریتم بروکا(سولین)

الگوریتم Borůvka یک الگوریتم حریصانه برای یافتن یک درخت پوشای کمینه در یک گراف است. الگوریتم Boruvka ساده و شهودی است. این الگوریتم یک راه‌حل جهانی "بهینه" را با استفاده از راه‌حل‌های کوچک‌تر و محلی بهینه برای زیر‌مسائل کوچک‌تر می‌سازد.

کاربردهای درخت پوشای کمینه

از کاربرد های درخت پوشای کمینه می‌توان به موارد زیر اشاره کرد:

• برای طراحی شبکه‌های آبرسانی، شبکهمعرفی و بررسی رشته شبکه های کامپیوتریرشته شبکه های کامپیوتری یکی از رشته های مقطع ارشد کامپیوتر است، در این صفحه مواردی همچون دروس ارشد شبکه های کامپیوتری، بازار کار رشته شبکه های کامپیوتری، ظرفیت این رشته در دانشگاه‌های دولتی بررسی شده استهای مخابراتی و شبکه‌های برق می‌توان از درخت پوشای کمینه استفاده کرد.
• می‌توان از آن برای یافتن مسیرهای روی نقشه استفاده کرد.

جمع‌بندی

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

مطالب مرتبط

همه مقالات

سورس کد چیست؟ آیا سورس کد یا سورس برنامه قابلیت اجرا دارند؟

از چه زبان های برنامه نویسی برای علم داده استفاده می شود؟

پایتون یا سی شارپ؟ – آینده پایتون بهتر است یا سی شارپ

مدیریت حافظه در زبان سی شارپ