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

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

1 پاسخ

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

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

برهان خلف:فرض کنید که زیر گراف یک گراف وتری، وتری نباشد لذا دارای دوری به طول بزرگتر از 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 \}$

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