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

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

1 پاسخ

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

یک درخت دلخواه با درجهٔ بیشینهٔ $\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$ چه تک‌گره چه نا تک‌گره دست‌کم یک برگ به درخت اصلی می‌دهد بنابراین حکم پرسش ثابت شد. این کران پائین برای تعداد برگ‌های یک درخت ناتک‌گره دقیق است چون برای نمونه گراف‌های ستاره که درخت هم هستند این کران را اتخاذ می‌کنند. برای قسمت دوم پرسش‌تان نیز یک گراف ستاره بردارید و هر یال را با یک درخت دو برگی به درازای دلخواه جایگزین کنید. تمام درخت‌هایی که به اندازهٔ درجهٔ بیشینه‌شان برگ داشته‌باشند در این خانواده قرار می‌گیرند.

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