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

[GUST]

سلام .این سوالو معلم گسسته حل کرد اما روش و استدلال حلشو نفهمیدم!
چرت از تعدال یال های ماکسیمم ۲ تا کم کرد؟ چرا از ۵ تا یکدونه کم کرد؟ توضیح پلیز

[mkh-ana]

سلام دوست من

اولا ما تعداد حداکثر یال ممکن رو بدست میاریم. که 15 میشه

و چون q برابر 5 هست باید 5 یال داشته باشیم.

یعنی باید 5 یال از 15 یال ممکن وجود داشته باشند.

اما با فرض سوال یک یال حتما باید وجود داشته باشد(v1v2)

پس آزادی انتخاب ما 4 یال است که باید از 14 یال ممکن انتخاب شود.((15 یال ممکن تبدیل به 14 شد.))

و چون با فرض نبودن یال (v2v5) مواجهیم پس ما یکی از حالات وجود یال را باز هم از دست میدهیم.

پس در آخر باید 4 از 13 انتخاب شود.

امیدوارم فهمیده باشید.

موفق و پیروز باشید.