***3
درخت پوشا
درختT درخت پوشای گراف Gاست اگرT زیرگرافG باشد که حاوی تمامی رئوس G است.
درخت پوشا را می توان با استفاده از BFSو DFS بدست آورد…
یکی از خواص جالب درخت پوشا: درخت پوشا کوچک ترین زیرگراف است...
***6
درخت پوشای مینیمم
تعریف1:منظورازهزینه درخت پوشای یک گراف بدون جهت وزن دار،مجموع هزینه (وزن)های یال های درخت پوشا است.
تعریف2: درخت پوشا با کمترین هزینه ،درخت پوشایی است که کمترین هزینه را دارد.
3 الگوریتم برای بدست آوردن MSTوجود دارد.
–الگوریتم کراسکال
–الگوریتم پریم
–الگوریتم سالین
***6
برای ایجاد درخت پوشا با کمترین هزینه از معیار کمترین هزینه استفاده می کنیم:
راه حل مطلوب تحت شرایط زیر حاصل می شود:
1.تنها باید از یال های گراف استفاده کند.
2.تنها باید دقیقا از n-1یال استفاده کند.
3.از یال هایی که دور ایجاد می کنند نمی توانداستفاده کند.
***7
الگوریتم کراسکال
این الگوریتم با اضافه کردن یال ها به صورت مرحله به مرحله بهT،درخت پوشا با کمترین هزینه ی T را تولید می کند.
یال ها به ترتیب غیر نزولی انتخاب می شوند.
یک یال بهTاضافه می شود مشروط بر اینکه با یال های اضافه شده قبلی دور تشکیل ندهد.
گراف Gهمبند است وn>0راس دارد پس دقیقا n-1 یال برای اضافه شدن در Tانتخاب میشود.