منظورت اینه که n-1 یال دارد. درسته؟
اگر این‌طوره، متن رو ویرایش کن.
آمار پرسش:
- پرسیده شده: 2020-12-25 07:56:59 -0600
- مشاهده شده: 210 بار
- بروز شده: 2021-01-04 05:23:13 -0600
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
اثبات گراف همبند با n راس یک درخت باشد،n-1 راس دارد.
به کمک استقرا اثبات کنید گراف همبند با n راس یک درخت باشد،n-1 راس دارد.
2020-12-25 07:56:59 -0600
جهانی 21 ● 1 ● 1 ● 2
نظرات
1 پاسخ
فکر کنم منظورت این بوده از سوال:
«به کمک استقرا اثبات کنید اگر یک گراف همبند با n راس، یک درخت باشد، n-1 یال (شاخه) دارد.»
به گراف‌های همبند بدون دور میگیم درخت.
به راسی از درخت که فقط یک شاخه بهش وصل باشه، میگیم برگ.
خب. حالا فرض کن این حکم مساله برای همه گراف‌های با کمتر از n راس صادقه.
یک گراف n راسی رو در نظر بگیر. اگر درخت باشه، باید دست کم ۲ تا برگ داشته باشه (چرا؟). حالا یکی از اون برگ‌ها رو از گراف قیچی کن. به یک گراف n-1 راسی همبند می‌رسی. طبق فرض استقرا، اگر این n-۲ شاخه داشته باشه یعنی درخته. وگرنه نیست.
حالا فرض می‌کنیم هست. اون یدونه برگ رو که کنده بودی، بهش اضافه کن دوباره. گراف هم‌چنان هم‌بنده و دور هم ایجاد نشده. پس یک درخته. از طرفی چون فقط یک شاخه بهش اضافه کردی، پس جمع شاخه‌هایش برابر n-1 میشه. تمام □
2021-01-04 05:23:13 -0600
سی پلاس پلاس 439 ● 3 ● 4 ● 12