کد: 36606

پرسش

آیا رابطه ای بین یالها و راسهای یك گراف وجود دارد كه همبند و یا ناهمبند
بودن گراف را نشان دهد؟(با توضیح!)

پاسخ

می دانیم كه اگر از یك درخت هر یالی را حذف كنید ناهمبند می شود پس اگر یك گراف با n راس كمتر از n-1 یال داشته باشد حتما ناهمبند خواهد بود.
در ضمن یك گراف با n راس را طوری در نظر بگیرید كه شامل یك گراف كامل با n-1 است و یك راس تنها .هر یالی به این گراف اضافه شود گراف همبند خواهد بود پس اگر یك گراف با n راس شامل بیش از انتخاب 2 از n-1 یال باشد حتما همبند خواهد بود.

مشاور : ۰ بهبودي | پرسش : دوشنبه 26/8/1382 | پاسخ : سه شنبه 27/8/1382 | پیش دانشگاهی | | 0 سال | رياضي | تعداد مشاهده: 23 بار

تگ ها :

UserName