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

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

1 پاسخ

می توانید به پاسخ(ها) امتیاز دهید یا آن را انتخاب کنید.

+2 امتیاز
توسط erfanm (13,881 امتیاز)

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

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

ریاضیدان، کسی است که شباهت ها را بین قضایا دریابد. ریاضیدان بهتر کسی است که بتواند شباهت بین برهان ها را ببیند. بهترین ریاضیدان کسی است که بتواند به شباهت بین نظریه ها توجه کند. و می توان تصور کرد که ریاضیدان نهایی کسی است که بتواند شباهت بین شباهت ها را مشاهده کند.
...