به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
–1 امتیاز
2,006 بازدید
در دبیرستان و دانشگاه توسط pantea (10 امتیاز)

چگونه باید این پرسش را حل کرد؟ برای بدست اوردن درخت فراگیر از یک گراف با p راس و q یال چند یال را باید حذف کنیم؟

توسط AmirHosein (19,718 امتیاز)
@pantea کجا چنین پرسش یا گزاره‌ای دیده‌اید که بگوید برای یک گراف با فقط دانستن تعداد گره و یال آن بتوان در مورد درخت فراگیرش صحبت کرد؟ اصلا شاید گراف شما همبند نباشد! تنها با دانستن تعداد گره و یال نمی‌توان دانست که درخت فراگیری اصلا وجود دارد یا خیر (غیر از حالت‌های بدیهی). و وقتی که اصلا تضمینی نیست که شما درخت فراگیر داشته باشید، گفتن اینکه چند تا یال حذف کنم تا به درخت فراگیر برسم هم معقول نیست. اگر پرسش یا گزارهٔ خاصی دیده‌اید و از آن سوال دارید به متن اصلی اشاره کنید تا راهنمایی‌تان کنیم.
توسط pantea (10 امتیاز)
–1
@amirhosein
پاسخ را خودم یافتم.
یک گراف همبند بدون دور دارای p-1 یال می باشد.
حال مقداری یال باید از q (تعداد یال های سوال) کم کنیم که به مقدار p-1 برسیم.
پس مقدار یال هایی که باید حذف شوند برابر است با q-p+1
درواقع

q-X= p-1
X=q-p+1
توسط AmirHosein (19,718 امتیاز)
@pantea متن پرسش شما فرض همبند بودن را نیاز دارد. بعلاوه در راه حل‌تان شما نمی‌توانید هر یال دلخواهی را کم کنید. تنها یال‌هایی که در دوری ظاهر شوند را می‌توانید حذف کنید. چه در متن پرسش چه در پاسخ جزئیات خیلی مهمی را از قلم می‌اندازید که در واقع به شما گزاره‌های نادرست (دارای مثال نقض) می‌دهد. هیچ وقت فکر نکنید بعضی واژه‌ها گفتنشان دل‌بخواهی است و دکوری گذاشته شده‌اند. حتما دلیل مهمی پشت خیلی از آنها هست.
توسط pantea (10 امتیاز)
–1
@amirhosein
من سوالم را از استادم در دانشگاه پرسیدم و به پاسخ صحیح که برای شما نیز عنوان کردم رسیدم. متشکرم
توسط AmirHosein (19,718 امتیاز)
@pantea مطمئن هستید دیدگاه‌ها را کامل خواندید؟ برای پرسش دیگرتان هم همین کار را کرده‌بودید https://math.irancircle.com/19325 در آنجا هم واژهٔ متناهی را برای نیم‌گروه جا انداخته بودید که دارای مثال نقض می‌شوید. اینجا هم همینطور، برای متن پرسش و همینطور متن پاسخ‌تان هر دو مثال نقض دارید مگر اینکه شرط‌های گفته‌شده در دیدگاه‌هایم را بیفزائید.

لطفا وارد شده یا عضو شوید تا بتوانید سوال بپرسید

این چرخ فلک که ما در او حیرانیم<br> فانوس خیال از او مثالی دانیم<br> خورشید چراغ دان و عالم فانوس<br> ما چون صوریم کاندرو حیرانیم
...