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

جز
ربات: تصحیح جایگذاری کاما، شمارگان هزارگان
بدون خلاصۀ ویرایش
جز (ربات: تصحیح جایگذاری کاما، شمارگان هزارگان)
<big>'''خیابان ها و چهار راه ها :'''</big>
 
تغییر نام خیابان ها و چهارراه ها ی عمومی یکی از سرگرمی های مطلوب انجمن های شهری در سراسر جهان است . فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان های خود بسیار اصولی باشند . فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه های دو انتهای خود باشد؛ پس به عنوان مثال ،مثال، یکی از دو انتهای خیابان واشنگتن بایستی در چهار راه واشنگتن باشد. طبیعتاً می خواهیم مسئله خود را در زبان گراف ها در حالتی کلی عنوان کنیم . گراف همبندی داده شده است . تحت چه شرط هایی می توان به طور منحصر به فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد ؟
در ابتدا خاطر نشان می کنیم که اگر گرلفمان درخت باشد ،باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می کنیم:
پس از اینکه ریشه ای مانند a0 را در درختی مانند درخت شکل زیر
[[پرونده:Treef1.JPG]]
 
به دلخواه انتخاب کردیم ،کردیم، یال a1 a0 را متناظر با رأس a1 می گیریم ،گیریم، به همین ترتیب a0 a2 را متناظر با a2 و و a0 a3 را متناظر با a3a3، ،سپسسپس a1 a11 را متناظر با a11 قرار می دهیم ،دهیم، و الی آخر ؛آخر؛ به طور کلی ،کلی، هر یال را به انتهایی از آن که از a0 دور تر است ،است، متناظر می کنیم.
اکنون فرض کنید که گراف دارای مداری مثلاً c، باشد ( شکل 2 ) هر یال c باید متناظر با یکی از دو رأس انتهایی خود باشد ،باشد، یعنی متناظر با رأسی از c. اگر به عنوان مثال یال a1 a2 متناظر با a2 باشد آنگاه یال a2 a3 بایستی متناظ با a3 باشد ،باشد، و الی آخر . بنابراین هیچ یال نا متعلق به c نمی تواند با رأسی از c متناظر باشد. در نتیجه یالی مانند a1 b1 که در a1 مدار c را قطع می کند ،کند، بایستی با b1 متناظر باشد و یالی مانند b1 b2 با b2 و الی آخر .
 
[[پرونده:Tree2.JPG]]
 
چنانکه ملاحظه می کنیم ،کنیم، قسمتی از گراف که به این ترتیب با عزیمت از a1 و حرکت در طول یال هایی مانند a1 b1 که با c در a1 مشترکند ،مشترکند، پیموده می شود ،شود، بایستی درختی مانند T1 می توان هر یال را با انتهایی از آن که از a1 متناظرند ،متناظرند، بنابراین از این تجزیه و تحلیل نتیجه ی زیر به دست می آید:
هر یال یک گراف همبند را می توان به طور منحصر به فردی با یکی از دو رأس آن یال متناظر کرد اگر و تنها اگر گراف نامبرده یک درخت باشد یا متشکل از مدار منحصر به فردی همراه با درخت هایی منشعب از رأس های آن مدار باشد ( به شکل 3 نگاه کنید)
 
 
 
بنا به قضیه (هر درخت با n رأس دارای n-1 یال است ) تعداد رأس های یک درخت یکی بیش از تعداد یال های آن است . .تعداد یال های یک مدار یا مداری که درخت هایی از رأس های آن منشعب شده اند با تعداد رأس های آن مساوی است. بنابراین ،بنابراین، در این موارد برقراری تناظری میان یال ها و رأس ها امکان دارد.
 
در ختی مانند درخت شکل (1) یا گرافی مانند گراف شکل (3) ، فقط می توانند نقشه ی خیابان های شهر های خیلی کوچک باشند که فاقر بلوک های شهری واقعی اند ،اند، یا فقط یک بلوک مرکزی دارند که خیابان هایی از حومه به آنها کشیده شده است.
پس از اندکی تأمل درباره ی این موضوع ،موضوع، عضوهای انجمن شهر سرافرازانه متوجه این واقعیت می شوند که شهر آن ها بزرکتر از آن است که بتوان این روش را در آن به کار گرفت. بنابراین قرار می گذارند که به جای آن از قاعده ی زیر استفاده کنند : خیابان ها و چهارراه ها طوری نامگذاری شوند که در هر چهار راهی یکی از خیابان ها به نام همان چهارراه باشد؛ یعنی ،یعنی، به عنوان مثال ،مثال، بایستی یکی از خیابان ها به نام همان چهار راه باشد ؛باشد؛ یعنی به عنوان مثال ،مثال، بایستی یکی از خیابان های منتهی به چهارراه واشنگتن به نام واشنگتن باشد.
به زبان نظریه ی گراف ها ،ها، این کار به معنی متناظر کردن هر رأس با فقط یکی از یال های متصل به آن است .این کار در مواردی عملی نیست ؛نیست؛ به عنوان مثال همانطور که گفته شد ،شد، تعداد رأس های هر درخت از تعداد یال های آن یکی بیشتر است . گراف شکل (1) را در نظر بگیرید . در این گراف می توان هر رأس را با یالی که از آن به سمت رأس a0 خارج می شود متناظر کرد . به این ترتیب ،ترتیب، به جز ریشه ،ریشه، هر رأس با یالی متناظر می شود.
 
''' <big>با توجه به حکم کلی زیر درخت ها از این نظر مستثنی هستند.</big>'''
 
رأس های گراف همبند غیر درخت را می توان با یال های متصل به آن ها متناظر کرد.
اثبات:هر گرافی که n رأس را به هم متصل می کند دارای حداقل n-1 یال است و با حذف برخی از یال ها قابل تبدیل به درخت است . فرض کنید a0b0 = e0 یکی از یال هایی باشد که با حذف آن ها گراف ما به یک درخت، مثلاً T، تبدیل می شود . a0 را به عنوان ریشه ی T انتخاب کنید. در T هر أس به جز a0 را می توان با یالی متصل به آن متناظر کرد ؛کرد؛ یال اضافی e0 از گراف را نیز می توان با a0 متناظر کرد. به این ترتیب هر رأس گراف با یالی متصل به آن متناظر شده است.
 
با توجه به بحث پیشین ،پیشین، توجه به این نکته مفید است که همیشه می توان در گراف ،گراف، ر أس ها را با یال های متصل به آن ها ،ها، یا یال ها را با رأس های متصل به آنها متناظر کرد. می توانیم هر دو کار را انجام دهیم ،دهیم، اگر و تنها اگر تعداد رأس ها و یال های گراف مساوی باشند . چنین گرافی نمی تواند درخت باشد و بنابراین ،بنابراین، نتیجه می گیریم که بایستی مانند گراف شکل (3) فقط دارای یک مدار c باشد . در واقع تناظری وجود دراد که دو سویی عمل می کند ،کند، یال ها را با رأس ها متناظر می کند ،کند، و رأس ها را با یال ها .کافی است یال های c را با رأس های c ، و هر رأس غیر متعلق به c را با نزدیکترین یال متصل به آن نسبت به c متناظر کرد .
 
== منابع ==
* .Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
* Otter, Richard (1948), “The Number of Trees”, Annals of Mathematics, Second Series 49 (3): 583–599
* .گراف وکاربردهای آن, نویسنده:ایستین ایر
== پاورقی ==
{{پانویس}}
۵۹۲٬۸۸۴

ویرایش