حل تشریحی سوال شماره 48 دروس مشترک

مجموعه رأس‌های گراف و را به دو زبرمجموعه افرازکرده‌ایم، فرض کنید بین ابن دو مجموعه سه یال cوbوa به ترتیب با وزن‌ها 2,4,6 وجود دارند (وزن a برابر ۲ است)، چتد تا از گزاره های زیر درست است؟

یال a درهر درخت پوشای کمینه G وجود دارد.

یال C در هیچ درخت پوشای کمینه‌ای وجود ندارد.

بال b می‌تواند در یک درخت پوشای کمینه حاضر باشند.