الگوریتم زیر را بر روی یک گراف همبندG بدون جهت و وزن دار در نظر بگیرید:
تا وقتی ک گراف دوری بنامC دارد این کار را تکرار کن:
یال با بیشترین وزن در C را بدست آور و آن را حذف کن
۱ این الگوریتم ممکن است ختم نشود
۲ گراف حاصل ممکن است همبند نباشد
۳ گراف حاصل یک درخت فراگیر کمینه برای گراف اولیه است
۴ گراف حاصل درخت فراگیر برای اولیه است ولی لزوما کمینه نیست
گزینه ۳ تو چند کتاب جواب اعلام شده
سوالم اینه ک برای گراف زیر فقط یالی کب بین گره ۱ و گره ۲ سنگین تره حذف میشه و الگوریتم ادامه پیدا نمیکنه تا گره ۳ هم وصل شه؟؟
۱<----->2 <-----3
سلام
من تا جایی که متوجه سوال شما شدم
در صورت سوال همبندی گراف مطرح شده و همین طور در توضیح الگوریم قید شده
تا زمانی که دوری وجود دارد
پس بین گره ۱ و ۲ اگه دو مسیر وجود داشته باشه سنگین ترین یال حذف میشه به شرطی که دور گراف وجود داشته باشه
اگه اشتباه متوجه منظورتون شدم بفرمایید.
موفق باشید
(۲۹ آبان ۱۳۹۲ ۰۲:۳۳ ق.ظ)rahayi نوشته شده توسط: سلام
من تا جایی که متوجه سوال شما شدم
در صورت سوال همبندی گراف مطرح شده و همین طور در توضیح الگوریم قید شده
تا زمانی که دوری وجود دارد
پس بین گره ۱ و ۲ اگه دو مسیر وجود داشته باشه سنگین ترین یال حذف میشه به شرطی که دور گراف وجود داشته باشه
اگه اشتباه متوجه منظورتون شدم بفرمایید.
موفق باشید
شکل گرافی ک مد نظرمه رو اصلاح کردم قبلا درست نبود
سوالم اینه ک گره ۳ ک بواسطه دور ب دو گره دیگه وصل نیست پس اصلا بهش مراجعه نمیشه چون جز شرط الگوریتم نیست
همونطور که روی سوال ذکر شده "گراف همبند "
ولی با این شکل گرافی که رسم کردین از گره یک به سه دوری وجود نداره که خلاف فرض مسئله است !!!