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

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

1 پاسخ

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

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

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

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

برای ترجمه ی یک جمله از انگلیسی به فرانسوی دو چیز ضروری است. اول، باید جمله ی انگلیسی را تماما بفهمیم. دوم، باید با اصطلاحات ویژه ای که در زبان فرانسوی هستند آشنا باشیم. این وضعیت خیلی شبیه هنگامی است که سعی داریم شرط را که با کلمات بیان شده است با نمادهای ریاضی بیان کنیم. اول، باید آن را تمام درک کنیم. دوم، باید با اصطلاحات ریاضی ریاضی آشنا باشیم.
...