یه سوال از گراف

[AMIR-T]

سلام این سوالو میشه یه نفر حل کنه؟ فردا امتحان داریم:
با رئوس (a,b,c,d,e,f) چند گراف ساده با اندازه 2 میتوان رسم کرد، بطوریکه در گراف ها ماکزیمم درجه-مینیمم درجه = 1 باشد؟
قسمت آخرش اگه نبود خودم حل میکردم.
جواب کتابم مینویسم ولی خودم هیچی ازش نفهمیدم:
وقتی "ماکزیمم درجه-مینیمم درجه = 1" یعنی 2 یال، راس مشترکی ندارند. تعداد گراف ها برابرست با:
[(5C2)*(3C2)] تقسیم بر !2 = 15

 

[mohammadi9]

پاسخ : یه سوال از گراف

وقتی می خوای هیچ دو تا یال راس مشترک نداشته باشند

2 از 5 برای تعداد طرق انتخاب 2 راس از 5 راس اولیه برای تعیین اولین یال

2 از 3 برای تعداد طرق انتخاب 2 راس از 3 راس باقی مانده برای تعیین دومین یال

طبق اصل ضرب هم داریم ضرب این دو تا ، اما ...

برای مثال ، اولین یال انتخاب شده ab و دومین یال cd باشد، از جا به جایی این دو تا یال ، گراف جدیدی ایجاد نمیشه یعنی اگر ما اولین یال رو ca و اولین یال رو bd در نطر بگیریم

هم چنان گراف مشخص شده در حالت اول، بدست اومده در صورتی که عبارت ضرب 2 از 5 و 2 از 3 ، تمامی حالت هاست. پس باید عبارت ضرب رو به 2! تقسیم کنیم تا از هر 2 گراف تکراری

یکیش شمرده بشه!