شمردن تعداد درخت ها¶

راهنمایی¶

رابطه ای ارائه دهید که تعداد درخت های با دنباله درجه ای \(d_1, d_2, ..., d_n\) را بشمارد. برای اثبات این رابطه به صورت استقرایی برگ حذف می کنیم!

حل¶

رابطه مورد نظر برابر است با \(\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times ... (d_n-1)!}\) . توجه کنید که \(\sum d_i-1\) برابر با همان \(n-2\) است پس عبارت بالا در واقع یک ترکیب با تکرار است!

برای اثبات رابطه از استقرا روی \(n\) استفاده کنید. به عنوان پایه در نظر داشته باشید که به ازای \(n \leq 2\) رابطه برقرار است. حالا کافیست تنها یک برگ خاص را در نظر بگیرید (راسی مثل \(u\) که \(d_u = 1\) است). سپس حالت بندی کنید که تنها مجاور این راس چه راسی باشد.‌ اگر تنها مجاور راس \(u\) راس \(v\) باشد (توجه کنید چون \(n > 2\) می توان نتیجه گرفت \(v\) نباید برگ باشد) آنگاه تعداد درخت های ممکن در این حالت برابر است با \(\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times ... (d_v-2)! (d_n-1)!}\) . همانطور که گفتیم عبارت بالا شبیه به یک ترکیب با تکرار است. طبق اتحاد تعمیم اتحاد پاسکال جمع عبارات (بعد از حالت بندی ها) برابر با \(\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times ... (d_n-1)!}\) خواهد شد. همانطور که می خواستیم.

حالا توجه کنید که عبارت بالا در واقع تعداد رشته های متفاوتی را می شمارد که از حرف \(i\) به تعداد \(d_i-1\) بار در آن آمده است. پس مثل این است که هر درخت را به یک دنباله \(n-2\) تایی از اعداد \(1\) تا \(n\) نسبت دادیم. پس اگر به ازای همه \(d_1,d_2,...,d_n\) های ممکن عبارت را جمع کنیم حاصل برابر با \(n^{n-2}\) خواهد شد که تعداد کل درخت های متفاوت \(n\) راسی است.

راهنمایی¶

تناظری یک به یک از درخت های \(n\) راسی به دنباله های \(n-2\) تایی از اعداد \(1\) تا \(n\) ایجاد می کنیم.

حل¶

تابع تناظر ما به اینصورت عمل می کند که در ابتدا درخت \(T\) را در نظر می گیریم و تا زمانی که تعداد راس های آن بیشتر از 2 است هر بار برگ \(u\) که برچسب آن کمینه است را حذف می کنیم. سپس برچسب تنها راس مجاور \(u\) را در روی کاغذ می نویسیم. در انتها \(n-2\) عددی که روی کاغذ نوشتیم را به ترتیب نوشتن در نظر بگیرید. آن ها دنباله \(n-2\) ما را تشکیل می دهند.

برای اثبات یک به یک بودن تناظر باید ثابت کنیم هر دنباله \(n-2\) تایی از اعداد \(1\) تا \(n\) به صورت یکتایی به درخت های \(n\) راسی متناظر شده اند. دنباله \(s_1,s_2,...,s_{n-2}\) را در نظر بگیرید. می خواهیم درختی که به آن تناظر داده شده است را پیدا کنیم.

اول از همه توجه کنید که در فرایند تناظر دادن ما راس \(i\) دقیقا \(d_i-1\) بار در رشته ظاهر شده است(چرا؟).

پس اعدادی که در بین \(s_1,s_2,...,s_{n-2}\) ظاهر نشده اند باید برگ های درخت باشند. در فرایند تناظر در اولین گام برگی که برچسب آن کمینه بود را حذف کردیم. پس کمترین عددی که در بین \(s_1,s_2,...,s_{n-2}\) ظاهر نشده است را \(u\) بنامید. ابتدا باید \(u\) حذف شده باشد و تنها مجاور \(u\) راس \(s_1\) می باشد. حالا به صورت استقرایی می توان درخت متناظر با \(s_2,...,s_{n-2}\) را به صورت یافت. سپس یال بین \(u,s_1\) را به درخت اضافه می کنیم و درخت متناظر با \(s_1,s_2,...,s_{n-2}\) به دست خواهد آمد.

راهنمایی¶

درخت دو رنگ را درختی تعریف می کنیم که راس \(A\) در آن به رنگ آبی در آمده و رنگ \(B\) به رنگ قرمز (حتی ممکن است \(A, B\) یک راس باشند).

واضح است که به ازای هر درخت \(n\) راسی دقیقا \(n^2\) درخت دورنگ داریم پس اگر \(c\) تا درخت \(n\) راسی داشته باشیم آنگاه \(c \times n^2\) تا درخت دورنگ \(n\) راسی داریم.

در این قسمت تناظری یک به یک بین گراف های تابعی \(n\) راسی (که تعداد آن ها \(n^n\) تا است) و درخت های دو رنگ ایجاد می کنیم.

حل¶

گراف تابعی را در نظر بگیرید. همانطور که می دانید در هر گراف تابعی از هر مولفه همبندی (در گراف زمینه) از یک دور جهت دار تشکیل شده است که از هر راس آن یک درخت آویزان است. شهودا برای تبدیل این گراف تابعی به درخت کافیست یک یال از هر دور را حذف کنیم سپس مولفه های همبندی گراف تابعی را به هم وصل کنیم تا تبدیل به درخت شود اما باید طوری این فرایند را انجام دهیم که تناظر یک به یک باشد و بتوان از روی درخت دو رنگ فهمید کدام یال حذف شده است!

فرض کنید به ازای هر مولفه همبندی گراف تابعی (در گراف زمینه) کمترین برچسب در دور آن را زیبایی مولفه می نامیم و راسی که این برچسب کمینه را دارد راس زیبای مولفه بنامید. حالا برای تناظر فرایند زیر را انجام دهید.

• مولفه ها طوری چپ به راس مرتب کنید که زیبایی مولفه ها از چپ به راست نزولی باشد.
• در هر کدام از مولفه ها فرض کنید دور آن \(p_1,p_2,...,p_k\) باشد به طوریکه \(p_1\) راس زیبای مولفه باشد. ابتدا یال \(p_kp_1\) را حذف کنید. سپس \(p_k\) را به راس زیبای مولفه بعدی (در سمت راست) وصل کنید.
• راس \(p_1\) در چپ ترین مولفه را آبی کنید و راس \(p_k\) در راست ترین مولفه را قرمز کنید. سپس جهت دهی یال ها را از بین ببرید.

به این صورت از گراف تابعی که داشتیم یک درخت دو رنگ ساختیم.

چرا زیبایی مولفه را کوچکترین راس دور تعریف کردیم و چرا مولفه ها را طوری مرتب کردیم که زیبایی ها نزولی باشد؟ دلیل این کار تنها این بود که مسیر راس آبی به قرمز این ویژگی را داشته باشد که به آن ویژگی جذاب می گوییم.

ویژگی جذاب : ابتدا توجه کنید که هر کدام از دور های گراف تابعی در واقع الان یک بازه از مسیر بین راس آبی و قرمز هستند. از راس آبی شروع کنید و به سمت راس قرمز بروید و برچسب ها را نگاه کنید. فرض کنید الان روی راس \(u\) هستیم و کمترین برچسبی که قبل از \(u\) در طول مسیر دیده ایم \(X\) باشد. اگر \(u<X\) باشد (یا به عبارتی \(X\) بعد از این مرحله کم شود) به این معنی است که وارد راسی شدیم که متعلق به یک دور دیگر (از گراف تابعی) بوده است(چرا؟)!

برای اینکه ثابت کنیم تناظر برگشت پذیر است باید از روی یک درخت دو رنگ بتوانیم به صورت یکتا گراف تابعی را بسازیم.

همانطور که گفتیم راس آبی را \(A\) در نظر بگیرید و راس قرمز را \(B\) در نظر بگیرید.

مراحل تناظر را یکی یکی به عقب بر می گردانیم تا به گراف تابعی برسیم. اول از همه درخت را از مسیر \(A\) به \(B\) آویزان کنید. راس \(A\) را در سمت چپ در نظر بگیرید و راس \(B\) را در سمت راست در نظر بگیرید.

• مسیر \(AB\) باید از چپ به راست جهت دهی شده باشد.
• سپس تمام درخت هایی که از رئوس مسیر \(AB\) آویزان شده اند باید از پایین به بالا جهت دهی شده باشند (هر راس به پدرش یال دارد).
• در اینجا از ویژگی جذاب که در بالا گفتیم استفاده می کنیم. با طی کردن مسیر از \(A\) به \(B\) می توانیم مسیر را به بازه هایی افراز کنیم که قبلا (در گراف تابعی) متعلق به یک مولفه بوده اند. حالا می دانیم که هر کدام از بازه ها قبلا یک دور بوده اند که راس های آن به ترتیب \(p_1,...,p_k\) بوده اند و یال \(p_kp_1\) حذف شده است. پس کافیست یک یال از راس آخر بازه (که همان \(p_k\) است) به راس اول بازه (که همان \(p_1\) است) بکشیم.

پس توانستیم با معکوس تابع تناظر از هر درخت دو رنگ به یک گراف تابعی برسیم. پس توانستیم یک به یک بودن تناظر را ثابت کنیم.

راهنمایی¶

سعی می کنیم تعداد انشعاب ها (درخت های ریشه دار که هر راس به جز ریشه به پدرش یال جهت دار دارد) بشماریم همچینین فرض کنید یال های درخت هم دارای ترتیب هستند یعنی جایگشتی \(n-1\) تایی روی یال های درخت نوشته ایم.

در اینصورت اگر تعداد انشعاب هایی که شمردیم (با احتساب ترتیب یال ها) برابر با \(T\) باشد آنگاه تعداد درخت ها برابر با \(\frac {T} {(n-1)! \times n}\) خواهد بود. به عبارتی هر درخت را \((n-1)! \times n\) بار می شماریم. ضریب \(n\) به خاطر حالت بندی روی ریشه درخت است و \((n-1)!\) به خاطر حالت بندی روی جایگشت نوشته شده روی یال های درخت می باشد.

حل¶

سعی می کنیم \(T\) را محاسبه کنیم. یک انشعاب خاص را در نظر بگیرید و فرایند ساختن آن را به شکل زیر در نظر بگیرید‌ :

• ابتدا گرافی \(n\) راسی و بدون یال در نظر بگیرید. یال ها را یکی یکی اضافه می کنیم. پس در هر مرحله تعدادی درخت جهت دار خواهیم داشت.
• در مرحله \(i\) ام یالی که روی آن عدد \(i\) نوشته شده را در نظر بگیرید. فرض کنید \(uv\) باشد.
• در اینصورت لازم و کافی است که در هر مرحله \(u, v\) مربوط به دو مولفه متفاوت باشند و همچنین \(v\) راسی باشد که ریشه یکی از درخت های جهت دار ما است.

برای شمردن تعداد انشعاب های ممکن کافی است بفهمیم فرایند ساختن انشعاب چند حالت مختلف می تواند داشته باشد.

در شروع مرحله \(i\) (با شمارش از 1) دقیقا \(n-i+1\) درخت ریشه دار داریم. اگر روی \(u\) حالت بندی کنید (که \(n\) حالت دارد) برای انتخاب \(v\) دقیقا \(n-i\) حالت داریم زیرا که \(v\) باید ریشه یکی از درخت ها باشد و نباید ریشه درختی باشد که \(u\) در آن است. بنابراین مرحله \(i\) ام فرایند ساختن گراف \(n \times (n-i)\) حالت دارد. پس در نهایت داریم \(T = n^{n-1} * (n-1)!\)

پس همانطور که گفتیم تعداد درخت ها باید برابر با \(\frac {T} {(n-1)! \times n}\) باشد که همان \(n^{n-2}\) است. همانطور که می خواستیم!