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

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

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 \}$

سال نو مبارک!


حمایت مالی


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