سلام
کسی جواب این سوال رو میدونه؟
پویا سمت راست شکل زیر را رسم کرده و به شاندیز داده است. این شکل از ۱۲ دایره سیاه و ۱۸ تکه خط (پاره خطی که دو سر آن دایره سیاه وجود دارد) تشکیل شده است.
![[تصویر: 184127_1_1379083290.jpg]](https://img.manesht.ir/184127_1_1379083290.jpg)
شاندیز در هر مرحله می تواند سه دایره سیاه A، B و C را که A به B و A به C با تکه خط متصل اند ولی B به C متصل نیست انتخاب کند و تکه خط AB و AC را حذف و تکه خط BC را بجای آن دو رسم کند (مانند شکل چپ). با تکرار این عمل تا جای ممکن، دست کم چه تعداد تکه خط ممکن است باقی بماند؟ (دقت کنید که در شکل سمت راست هیچ سه نقطه ای در یک خط نیستند)
کسی نمیتونه کمک کنه؟
لطفا دوستان کمک کنین
چرا هیچکــــــــــی جواب سوال منو نمیده این همه از این سایت تعریف میکردن که جواب سوال بچه ها رو میدن این بود؟
تا جایی که من میدونم گراف برای اگوریتم کراسکال باید همبند باشه و نتیجه نهایی هم همبنده.که این گراف همبند نیست و ربطی به الگوریتم کراسکال نداره
نمیتونم شباهتی به راه حل این مسئله با کروسکال پیدا کنم. کاری که باید انجام بدیم اینه که در هر مرحله دو یال از داسی رو که به دو راس غیر همجوار وصلن رو پاک کنیم و اون دو راس رو همجوار کنیم. پس به هیچ وجه نمیتونیم با با مربع وسطی که قطراش رسم شدن کاری انجام بدیم. توی تمام مراحل زوج یا فرد بودن درجه رئوس ثابت میمونه. یعنی فقط دوتا میتوه کم بشه یا تغییر نکنه. با یک بار مرور الگوریتم میتونید ۸ یال رو حذف کنید. ۱۰ یال یاقی خواهد موند. ۶ یال از مربع وسطی بهمراه قطرش و چهار یال بین ۸ راس دیگه.