چنانچه محفل ریاضی را سودمند یافتید، لطفا برای حمایت از ما به کانال تلگرامی محفل ریاضی بپیوندید!
به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
34 بازدید
سوال شده در دانشگاه توسط 3329806990

الف) نشان دهید که هر درخت با ماکزیمم درجه kحداقل kبرگ دارد. ب) چه درختهایی دقیقا دارای kبرگ هستند.

1 پاسخ

+1 امتیاز
پاسخ داده شده توسط AmirHosein
انتخاب شده توسط 3329806990
 
بهترین پاسخ

یک درخت دلخواه با درجهٔ بیشینهٔ $\Delta$ بردارید. یکی از گره‌هایی که درجه‌اش $\Delta$ است را $v_0$ بنامید. گره‌های همسایهٔ آن را $v_i$، $i=1,\dots,\Delta$ نامگذاری کنید و برای هر $i$ تعریف کنید $N_i$ مجموعه‌ای از گره‌ها غیر از $v_0$ باشد که با گرهٔ $v_i$ همسایه هستند (یالی بین آن دو هست). راحت می‌توانید نشان دهید که اگر یالی بین دو $N_i$ و $N_j$ -ِ متمایز وجود داشته‌باشد آنگاه دوری در گراف اصلی می‌شود یافت که تناقض با درخت بودن آن دارد. پس $N_i$ها دو به دو مجزا هستند. اکنون توجه کنید که زیرگراف همیند از یک درخت، یک درخت می‌شود. زیرگراف القا شده بوسیلهٔ $N_i$ها همیند هستند زیرا اگر بین هر دو گره‌شان باید یک مسیر در گراف اصلی باشد. چون یالی از دو گره در یک $N_i$ به داخل بقیهٔ $N_i$ها نمی‌رود این مسیر باید از گره‌های $N_i$ و $v_0$ استفاده کند. اما اگر از $v_0$ بگذرد یعنی دو همسایه از $v_0$ در یک $N_i$ هست که تناقض است. پس $\Delta$ تا درخت داریم. اگر درختی تک‌گره نباشد آنگاه دست‌کم دو برگ دارد. از این دو برگ حداکثر یکی می‌تواند $v_i$ باشد پس یکی از برگ‌هایش همسایهٔ $v_0$ نیست یعنی تمامی یالهایش در گراف اصلی و این زیرگراف یکسان هستند پس در درخت اصلی نیز برگ بوده‌اند. اگر درختی تک‌گره باشد آنگاه برگی ندارد ولی توجه کنید که تک گره بودن $N_i$ یعنی $v_i$ برگی در درخت اصلی بوده‌است. پس ثابت کردیم که هر $N_i$ چه تک‌گره چه نا تک‌گره دست‌کم یک برگ به درخت اصلی می‌دهد بنابراین حکم پرسش ثابت شد. این کران پائین برای تعداد برگ‌های یک درخت ناتک‌گره دقیق است چون برای نمونه گراف‌های ستاره که درخت هم هستند این کران را اتخاذ می‌کنند. برای قسمت دوم پرسش‌تان نیز یک گراف ستاره بردارید و هر یال را با یک درخت دو برگی به درازای دلخواه جایگزین کنید. تمام درخت‌هایی که به اندازهٔ درجهٔ بیشینه‌شان برگ داشته‌باشند در این خانواده قرار می‌گیرند.

لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
76 نفر آنلاین
0 عضو و 76 مهمان در سایت حاضرند
بازدید امروز: 5774
بازدید دیروز: 8256
بازدید کل: 4500894
...