تفاوت میان نسخه‌های «درخت پوشای کمینه»

کمی ویرایش
جز (ربات:برداشتن تصویر حذف شده)
(کمی ویرایش)
== '''درخت پوشای بهینه(کمینه/با''' حداقلدر هزینه[[گراف|گراف‌های]] ارزش دار (وزن دار) ==ساخته می‌شود.
درخت پوشای بهینه در گراف های ارزش دار (وزن دار ) ساخته می‌شود.فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گرف همبند وزن دار) درختی است که بین درخت های پوشای آن گراف، مجموع وزن یال های آن، کمترین مقدار ممکن باشد.براي به دست آوردن درخت پوشاي بهینه يک گراف جهت دار متصل مي توان از الگوريتم های متفاوتی استفاده نمود.البته بطور کلی دو الگوریتم برای درخت پوشای مینیمم وجود دارد که عبارتند از :
[[الگوریتم Kruskal]]
[[الگوریتم prim]]
 
درخت پوشای بهینه در گراف های ارزش دار (وزن دار ) ساخته می‌شود.فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گرف همبند وزن دار) درختی است که بین درخت های پوشای آن گراف، مجموع وزن یال های آن، کمترین مقدار ممکن باشد.براي به دست آوردن درخت پوشاي بهینه يک گراف جهت دار متصل مي توان از الگوريتم های متفاوتی استفاده نمود.البته بطور کلی دو الگوریتم برای درخت پوشای مینیمم وجود دارد که عبارتند از :
== الگوریتم Kruskal ==
[[الگوریتم primکراسکال]]
در الگوریتم کراسکال , یالهای گراف را به ترتیب صعودی مرتب می کنیم . از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد . این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.
[[الگوریتم Kruskalپریم]]
 
== الگوریتم Kruskal کراسکال==
در الگوریتم کراسکال , یالهاییال‌های گراف را به ترتیب صعودی مرتب می کنیم . از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد . این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.
 
{{چپ چین}}
{{پایان چپ چین}}
 
نحوهٔ کار الگوریتم Kruskalکراسکال به این صورت است که یک جنگل از درخت هارا به ترتیب با هم ادغام می‌کند تا به یک درخت واحد برسد. در اینجا نمونه‌ای از چگونگی عملکرد الگوریتم کراسکال آورده ایمآورده‌ایم:
 
[[پرونده:kruskal.jpg|center|frame|شکل ۱]]
 
== الگوریتم primپریم ==
در این روش از یک رأس شروع می کنیم و کمترین یال (یال با کمترین وز ن وزن) که از آن می گذرد را انتخاب می کنیم . در مرحله بعد یالی انتخاب می‌شود که کمترین وزن را در بین یالهایییال‌هایی که از دو گره موجود می گذرد داشته باشیم . به همین ترتیب در م رحلهمرحله بعد یالی انتخاب می‌گردد که کمترین وزن را در بین یالهایی که از سه گره موجود می گذرد داشته باشد . این روال را آنقدر تکرار می کنیم تا درخت پوشای بهینه حاصل شود . باید توجه کرد که یال انتخابی در هر مرحله در صورتی انتخاب می‌شود که در گراف دور ایجاد نکند . تفاوت روش پریم با روش کراسکال در این است که گراف حاصل در مراحل میانی تشکیل درخت پوشای بهینه در روش پریم همیشه متصل است ولی در الگوریتم کراسکال در آخرین مرحله قطعاً متصل است.
{{چپ چین}}
<source lang=cpp>
 
* ممکن است درختهایی که الگوریتم مذکور تولید می‌کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همهٔ درخت ها یکسان است.
*مرتبهٔ زمانی الگوریتم primپریم برابر (o(n^2 است. (حلقهٔ while، برای n دفعه و عمل یافتن از میان لبه‌های متصل به یک مجموعه دور خاص n دفعه اتفاق می افتد؛ که در مجموع برابر n^2 دفعه می‌شود).
 
 
از روش های دیگر برای یافتن درخت پوشای بهینه می‌توان الگوریتم های زیر را نام برد:
[[الگوریتم سولین]]
 
== الگوریتم دایکسترا (Dijkstra) ==
این الگوریتم بصورت حریصانه عمل نموده و به‌دنبال یافتن کوتاه ترین مسیر ممکن بین یک نود و هر نود دلخواه دیگر، در یک گراف وزن دار و جهت دار می‌باشد. ورودی این الگوریتم همیشه یک ماتریس دو بعدی است که همان ماتریس وزن گراف است.
 
*[http://www.erfanrad.blogfa.com]
{{پایان چپ چین}}
 
[[رده:نظریه گراف]]
 
[[en:Minimum spanning tree]]