درخت (نظریه گراف): تفاوت میان نسخه‌ها

هیچ تغییری در اندازه به وجود نیامده‌ است. ،  ۱۰ سال پیش
جز (ویرایش 66.201.54.122 (بحث) به آخرین تغییری که MerlIwBot انجام داده بود واگردانده شد)
 
تغییر نام خیابان ها و چهارراه ها ی عمومی یکی از سرگرمی های مطلوب انجمن های شهری در سراسر جهان است . فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان های خود بسیار اصولی باشند . فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشنگتن بایستی در چهار راه واشنگتن باشد. طبیعتاً می خواهیم مسئله خود را در زبان گراف ها در حالتی کلی عنوان کنیم . گراف همبندی داده شده است . تحت چه شرط هایی می توان به طور منحصر به فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد ؟
در ابتدا خاطر نشان می کنیم که اگر گرلفمانگرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می کنیم:
پس از اینکه ریشه ای مانند a0 را در درختی مانند درخت شکل زیر
[[پرونده:Treef1.JPG]]
کاربر ناشناس