کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

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

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

درخت پوشا

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

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

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

مثال

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

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

 درخت پوشا

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

درخت پوشا 

 

 درخت پوشا

 درخت پوشا

درخت پوشا

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

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

مثال

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

جمع‌بندی

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

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

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

نمونه ای از درخت پوشای کمینه چیست؟

یک شرکت کابلی را تصور کنید که می‌خواهد به چندین محله کابل بکشد. با به حداقل رساندن میزان کابل اعمال شده، شرکت کابل، در هزینه صرفه جویی می‌کند.

Prim بهتر است یا Kruskal؟

مزیت الگوریتم پریم پیچیدگی آن است که از الگوریتم کروسکال بهتر است؛ بنابراین الگوریتم Prim هنگام برخورد با گراف‌های متراکم با یال‌های زیاد مفید است. با این‌حال، الگوریتم Prim به ما اجازه نمی‌دهد تا کنترل زیادی روی یال‌های انتخاب شده زمانیکه چندین یال با وزن یکسان وجود دارد، داشته باشیم.

کجا از درخت پوشای کمینه استفاده می‌کنیم؟

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

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
بارگذاری نظرات