موضوع مقاله: درخت (نظریه گراف) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت (نظریه گراف) | مقدمه: درخت یک گراف ساده بدون جهت است که در یکی از شروط معادل زیر صدق کند: G متصل است و دور ندارد. | ## بخش 1: درخت (نظریه گراف) | G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن به وجود می‌آید. اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند: G متصل است و n-1 یال دارد. یک درخت را ریشه‌دارRooted tree گوییم اگر راسی داشته باشد که به ازای هر راس دیگر درخت، مسیری از آن به راس مذکور وجود داشته باشد. در ضمن با توجه به این که فرض می‌شود درخت‌ها ریشه دارند یک درخت بدون ریشه را درخت آزادFree tree گوییم. درخت چندگانهPolytree درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد؛ یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد. کاربرد خیابان‌ها و چهار راه‌ها: تغییر نام خیابان‌ها و چهارراه‌ها ی عمومی یکی از سرگرمی‌های مطلوب انجمن‌های شهری در سراسر جهان است. فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان‌های خود بسیار اصولی باشند. فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه‌های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشینگتن بایستی در چهار راه واشینگتن باشد. تحت چه شرط‌هایی می‌توان به‌طور منحصربه‌فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد؟ | ## بخش 2: درخت (نظریه گراف) | اکنون فرض کنید که گراف دارای مداری مثلاً c، باشد (شکل ۲) هر یال c باید متناظر با یکی از دو رأس انتهایی خود باشد، یعنی متناظر با رأسی از c. اگر به عنوان مثال یال a1 a2 متناظر با a2 باشد آنگاه یال a2 a3 بایستی متناظ با a3 باشد، و الی آخر؛ بنابراین هیچ یال نا متعلق به c نمی‌تواند با رأسی از c متناظر باشد. در نتیجه یالی مانند a1 b1 که در a1 مدار c را قطع می‌کند، بایستی با b1 متناظر باشد و یالی مانند b1 b2 با b2 و الی آخر. تعداد یال‌های یک مدار یا مداری که درخت‌هایی از رأس‌های آن منشعب شده‌اند با تعداد رأس‌های آن مساوی است؛ بنابراین، در این موارد برقراری تناظری میان یال‌ها و رأس‌ها امکان دارد. در ختی مانند درخت شکل (۱) یا گرافی مانند گراف شکل (۳)، فقط می‌توانند نقشهٔ خیابان‌های شهرهای خیلی کوچک باشند که فاقد بلوک‌های شهری واقعی اند، یا فقط یک بلوک مرکزی دارند که خیابان‌هایی از حومه به آن‌ها کشیده شده است. پس از اندکی تأمل دربارهٔ این موضوع، عضوهای انجمن شهر سرافرازانه متوجه این واقعیت می‌شوند که شهر آن‌ها بزرکتر از آن است که بتوان این روش را در آن به کار گرفت؛ بنابراین قرار می‌گذارند که به جای آن از قاعدهٔ زیر استفاده کنند: خیابان‌ها و چهارراه‌ها طوری نامگذاری شوند که در هر چهار راهی یکی از خیابان‌ها به نام همان چهارراه باشد؛ یعنی، به عنوان مثال، بایستی یکی از خیابان‌ها به نام همان چهار راه باشد؛ یعنی به عنوان مثال، بایستی یکی از خیابان‌های منتهی به چهارراه واشینگتن به نام واشینگتن باشد. به زبان نظریهٔ گراف‌ها، این کار به معنی متناظر کردن هر رأس با فقط یکی از یال‌های متصل به آن است. این کار در مواردی عملی نیست؛ به عنوان مثال همان‌طور که گفته شد، تعداد رأس‌های هر درخت از تعداد یال‌های آن یکی بیشتر است. در این گراف می‌توان هر رأس را با یالی که از آن به سمت رأس a0 خارج می‌شود متناظر کرد. | ## بخش 3: درخت (نظریه گراف) | با توجه به حکم کلی زیر درخت‌ها از این نظر مستثنی هستند رأس‌های گراف همبند غیر درخت را می‌توان با یال‌های متصل به آن‌ها متناظر کرد. اثبات:هر گرافی که n رأس را به هم متصل می‌کند دارای حداقل n-1 یال است و با حذف برخی از یال‌ها قابل تبدیل به درخت است. فرض کنید a0b0 = e0 یکی از یال‌هایی باشد که با حذف آن‌ها گراف ما به یک درخت، مثلاً T، تبدیل می‌شود. در T هر أس به جز a0 را می‌توان با یالی متصل به آن متناظر کرد؛ یال اضافی e0 از گراف را نیز می‌توان با a0 متناظر کرد. با توجه به بحث پیشین، توجه به این نکته مفید است که همیشه می‌توان در گراف، ر أس‌ها را با یال‌های متصل به آن‌ها، یا یال‌ها را با رأس‌های متصل به آن‌ها متناظر کرد. می‌توانیم هر دو کار را انجام دهیم، اگر و تنها اگر تعداد رأس‌ها و یال‌های گراف مساوی باشند. چنین گرافی نمی‌تواند درخت باشد و بنابراین، نتیجه می‌گیریم که بایستی مانند گراف شکل (۳) فقط دارای یک مدار c باشد. در واقع تناظری وجود دراد که دو سویی عمل می‌کند، یال‌ها را با رأس‌ها متناظر می‌کند، و رأس‌ها را با یال‌ها. | ## جمع‌بندی | کافی است یال‌های c را با رأس‌های c، و هر رأس غیر متعلق به c را با نزدیکترین یال متصل به آن نسبت به c متناظر کرد.