Question

سلام دوستان،سوال اینه که الگوریتمی برای یافتن درخت فراگیر از یک گراف همبند بنوسید. ممنون میشم جوابشو بگین بهم

Answer 1

گراف G=(V,E) داده شده

قرار بده Vt و Et تهی باشد.(مجموعه رئوس و یالهای درخت فراگیر)

مجموعه رئوس ملاقات نشده U=V

یک راس دلخواه از G را انتخاب کن و در Vt قرار بده

قرا بده U=U-{v}

تا زمانیکه (U تهی نباشد) تکرار کن

   یک یال مجاور e از رئوس Vt را انتخاب کن و در Et قرار بده
  انتهای دیگر یال e را در Vt قرار بده
   قرا بده U=U-{v}

T=(V,E) را برگردان

Answer 2

سلام ^__^

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

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

آمار پرسش:

پرسش‌های مشابه:

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

استفاده از ویرایشگر:

علائم ریاضی:

الگوریتمی برای یافتن درخت فراگیر از یک گراف همبند ینویسید.

2 پاسخ

پاسخ شما

پیش‌نمایش: