• مشکی
  • سفید
  • سبز
  • آبی
  • قرمز
  • نارنجی
  • بنفش
  • طلایی
کد: 36606

پرسش

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

پاسخ

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

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

تگ ها :

UserName