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

بدون خلاصۀ ویرایش
بدون خلاصۀ ویرایش
 
== کاربرد ==
<span style="font-size: large;">'''خیابان‌ها و چهار راه‌ها :'''</span>
 
تغییر نام [[خیابان‌ها]] و چهارراه‌ها ی عمومی یکی از سرگرمی‌های مطلوب انجمن‌های شهری در سراسر جهان است. فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان‌های خود بسیار اصولی باشند. فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه‌های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشینگتن بایستی در چهار راه واشینگتن باشد. طبیعتاً می‌خواهیم مسئله خود را در زبان گراف‌ها در حالتی کلی عنوان کنیم. گراف همبندی داده شده‌است. تحت چه شرط‌هایی می‌توان به‌طور منحصربه‌فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد؟ در ابتدا خاطر نشان می‌کنیم که اگر گرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می‌کنیم:
در ابتدا خاطر نشان می‌کنیم که اگر گرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می‌کنیم:
پس از اینکه ریشه ای مانند a0 را در درختی مانند درخت شکل زیر
[[پرونده:Treef1.JPG]]
[[پرونده:Tree2.JPG]]
 
چنان‌که ملاحظه می‌کنیم، قسمتی از گراف که به این ترتیب با عزیمت از a1 و حرکت در طول یال‌هایی مانند a1 b1 که با c در a1 مشترکند، پیموده می‌شود، بایستی درختی مانند T1 می‌توان هر یال را با انتهایی از آن که از a1 متناظرند، بنابراین از این تجزیه و تحلیل نتیجهٔ زیر به دست می‌آید: هر یال یک [[گراف همبند]] را می‌توان به‌طور منحصربه‌فردی با یکی از دو رأس آن یال متناظر کرد اگر و تنها اگر گراف نامبرده یک درخت باشد یا متشکل از مدار منحصربه‌فردی همراه با درخت‌هایی منشعب از رأس‌های آن مدار باشد (به شکل ۳ نگاه کنید)
هر یال یک [[گراف همبند]] را می‌توان به‌طور منحصربه‌فردی با یکی از دو رأس آن یال متناظر کرد اگر و تنها اگر گراف نامبرده یک درخت باشد یا متشکل از مدار منحصربه‌فردی همراه با درخت‌هایی منشعب از رأس‌های آن مدار باشد (به شکل ۳ نگاه کنید)
 
[[پرونده:Tree3.JPG]]
بنا به قضیه (هر درخت با n رأس دارای n-1 یال است) تعداد رأس‌های یک درخت یکی بیش از تعداد یال‌های آن است . . تعداد یال‌های یک مدار یا مداری که درخت‌هایی از رأس‌های آن منشعب شده‌اند با تعداد رأس‌های آن مساوی است؛ بنابراین، در این موارد برقراری تناظری میان یال‌ها و رأس‌ها امکان دارد.
 
در ختی مانند درخت شکل (۱) یا گرافی مانند گراف شکل (۳)، فقط می‌توانند نقشهٔ خیابان‌های شهرهای خیلی کوچک باشند که فاقرفاقد بلوک‌های شهری واقعی اند، یا فقط یک بلوک مرکزی دارند که خیابان‌هایی از حومه به آن‌ها کشیده شده‌است.
پس از اندکی تأمل دربارهٔ این موضوع، عضوهای انجمن شهر سرافرازانه متوجه این واقعیت می‌شوند که شهر آن‌ها بزرکتر از آن است که بتوان این روش را در آن به کار گرفت؛ بنابراین قرار می‌گذارند که به جای آن از قاعدهٔ زیر استفاده کنند: خیابان‌ها و چهارراه‌ها طوری نامگذاری شوند که در هر چهار راهی یکی از خیابان‌ها به نام همان چهارراه باشد؛ یعنی، به عنوان مثال، بایستی یکی از خیابان‌ها به نام همان چهار راه باشد؛ یعنی به عنوان مثال، بایستی یکی از خیابان‌های منتهی به چهارراه واشینگتن به نام واشینگتن باشد.
به زبان نظریهٔ گراف‌ها، این کار به معنی متناظر کردن هر رأس با فقط یکی از یال‌های متصل به آن است. این کار در مواردی عملی نیست؛ به عنوان مثال همان‌طور که گفته شد، تعداد رأس‌های هر درخت از تعداد یال‌های آن یکی بیشتر است. گراف شکل (۱) را در نظر بگیرید. در این گراف می‌توان هر رأس را با یالی که از آن به سمت رأس a0 خارج می‌شود متناظر کرد. به این ترتیب، به جز ریشه، هر رأس با یالی متناظر می‌شود.
۳۸۱

ویرایش