به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+2 امتیاز
68 بازدید
سوال شده در دانشگاه توسط سوسن

زیر گراف هر گراف وتری،وتری است؟ مجتمع خوشه ای را با یه مثال شرح دهید

1 پاسخ

+2 امتیاز
پاسخ داده شده توسط erfanm

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

برهان خلف:فرض کنید که زیر گراف یک گراف وتری، وتری نباشد لذا دارای دوری به طول بزرگتر از 3 است که کورد(وتر) ندارد اما این دور ، یه دور در گراف اصلی نیز است پس نتیجه می شود که گراف اصلی هم وتری نیست که تناقض است.

کافیست دقت کنید که وقتی زیر گراف با یک مجموعه رئوس داریم یالها ی زیر گراف تمام یالهای گراف اصلی هستند که رئوسشان در زیر گراف آمده است

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

در مورد مجتمع خوشه ای گراف زیر را در نظر بگیرید.

enter image description here

اگر تمام خوشه ها را در نظر بگیریم یک مجتمع سادکی بدست می آید مثلا خوشه های زیر را داریم:

$\{1,2,5 \}$ و$\{2,3 \}$ و$\{3,4 \}$ و$\{4,5 \}$ و $\{4,6 \}$ حتی$\{1,2 \}$ و$\{2,5 \}$ و $\{1,5 \}$ خوشه هستند که زیر مجموعه خوشه ی $\{1,2,5 \}$ هستند لذا فست ها برابر است با :

$\{1,2,5 \}$ و$\{2,3 \}$ و$\{3,4 \}$ و$\{4,5 \}$ و $\{4,6 \}$

لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
تلگرام محفل ریاضی
45 نفر آنلاین
0 عضو و 45 مهمان در سایت حاضرند
بازدید امروز: 2161
بازدید دیروز: 4860
بازدید کل: 5007813
...