درخت (نظریه گراف)

left
در نظریه گراف، درخت گرافی همبند و بدون دور است. درخت‌ها به طور گسترده در علوم رایانه و ساختار داده‌ها کاربرد دارند. مثل درخت‌های جستجوی دودویی، پشته‌ها، درخت‌های هافمن برای فشرده‌سازی اطلاعات و غیره.
تعاریف
نمونه‌ای از یک درخت
در اینجا به دلیل وجود یک دور گراف درخت نمی‌باشد.
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
G متصل است و دور ندارد.
G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود می‌آید.
G متصل است و اگر یک یال آن حذف شود دیگر متصل نیست.
هر دو راس در G با یک مسیر ساده یکتا به هم وصل می‌شوند.
اگر G تعداد متناهی راس داشته باشد احکام بالا با شروط زیر نیز معادل اند:
G متصل است و n-1 یال دارد.
G مدار ساده ندارد و n-1 یال دارد.
گراف ساده بدون جهت G را جنگل گوئیم اگر مسیر ساده نداشته باشد.
درخت جهت‌دار گراف جهت‌داری است که گراف زمینه آن یک درخت باشد.
یک درخت را ریشه‌دار گوییم اگر راسی داشته باشد که به ازای هر راس دیگر درخت، مسیری از آن به راس مذکور وجود داشته باشد. مرتبه درخت یک مرتب‌سازی جزئی روی رئوس درخت است که اگر و فقط اگر یک مسیر یکتا از ریشه به v از u بگذرد. یک درخت که زیر گراف، گراف G است را درخت نرمال گوییم اگر انتهای هر یال G با این رتبه‌بندی قابل مقایسه باشد (Diestel 2005 ,p.15).
درخت ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است. در ضمن با توجه به این که فرض می‌شود درخت‌ها ریشه دارند یک درخت بدون ریشه را درخت آزاد گوییم.
درخت چندگانه درختی است که حداکثر یک مسیر بدون جهت بین هر دو راسش دارد. یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد.
درخت برچسب دار درختی است که در آن هر راس برچسب یکتایی دارد. رئوس درختی با n راس به طور نمونه با اعداد ۱و۲و۳و… وn برچسب گذاری می‌شوند. درخت بازگشتی یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبه درخت تعیین می‌شود. (اگر و u,v دو راس درخت باشند برچسب u کوچکتر از برچسب v است)
درخت ساده نشدنی درختی است که راسی با درجه ۲ ندارد.
درخت مرتب درختی است که برای فرزندان هر راس مرتبه‌ای تعیین شده باشد.
درخت n-تایی درختی است که هر راس که برگ نیست حداکثر n فرزند دارد.
درخت نمایش داده شده در شکل بالا ۶ راس، ۱–۶ = ۵ یال دارد. مسیر ساده یکتا که راس ۲ را به ۶ وصل می‌کند ۶-۵-۴-۲ است.
احکام
هر درخت یک گراف دو بخشی و یک گراف میانه است. هر درخت با تعداد شمارا راس یک گراف مسطح است.
هر درخت با حداقل ۲ برگ (یا راس با درجه ۱)دارد. حداقل تعداد برگ مربوط به گراف مسیر و حداکثر تعداد برگ (n-1) مربوط به گراف ستاره‌ای است.
کاربرد
خیابان‌ها و چهار راه‌ها :
تغییر نام خیابان‌ها و چهارراه‌ها ی عمومی یکی از سرگرمی‌های مطلوب انجمن‌های شهری در سراسر جهان است. فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان‌های خود بسیار اصولی باشند. فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه‌های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشینگتن بایستی در چهار راه واشینگتن باشد. طبیعتا می‌خواهیم مسئله خود را در زبان گراف‌ها در حالتی کلی عنوان کنیم. گراف همبندی داده شده است. تحت چه شرط‌هایی می‌توان به طور منحصربه‌فردی هر یال را با یکی از دو راس انتهایی آن متناظر کرد؟
در ابتدا خاطر نشان می‌کنیم که اگر گرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می‌کنیم:
پس از اینکه ریشه‌ای مانند a0 را در درختی مانند درخت شکل زیر
پرونده:Treef1.JPG
به دلخواه انتخاب کردیم، یال a1 a0 را متناظر با راس a1 می‌گیریم، به همین ترتیب a0 a2 را متناظر با a2 و و a0 a3 را متناظر با a3، سپس a1 a11 را متناظر با a11 قرار می‌دهیم، و الی آخر؛ به طور کلی، هر یال را به انتهایی از آن که از a0 دور‌تر است، متناظر می‌کنیم.
اکنون فرض کنید که گراف دارای مداری مثلا c، باشد (شکل ۲) هر یال 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 متناظرند، بنابراین از این تجزیه و تحلیل نتیجه زیر به دست می‌آید:
هر یال یک گراف همبند را می‌توان به طور منحصربه‌فردی با یکی از دو راس آن یال متناظر کرد اگر و تنها اگر گراف نامبرده یک درخت باشد یا متشکل از مدار منحصربه‌فردی همراه با درخت‌هایی منشعب از راس‌های آن مدار باشد (به شکل ۳ نگاه کنید)
پرونده:Tree3.JPG
بنا به قضیه (هر درخت با n راس دارای n-1 یال است) تعداد راس‌های یک درخت یکی بیش از تعداد یال‌های آن است . . تعداد یال‌های یک مدار یا مداری که درخت‌هایی از راس‌های آن منشعب شده‌اند با تعداد راس‌های آن مساوی است؛ بنابراین، در این موارد برقراری تناظری میان یال‌ها و راس‌ها امکان دارد.
در ختی مانند درخت شکل (۱) یا گرافی مانند گراف شکل (۳)، فقط می‌توانند نقشه خیابان‌های شهرهای خیلی کوچک باشند که فاقر بلوک‌های شهری واقعی‌اند، یا فقط یک بلوک مرکزی دارند که خیابان‌هایی از حومه به آنها کشیده شده است.
پس از اندکی تامل درباره این موضوع، عضوهای انجمن شهر سرافرازانه متوجه این واقعیت می‌شوند که شهر آن‌ها بزرکتر از آن است که بتوان این روش را در آن به کار گرفت؛ بنابراین قرار می‌گذارند که به جای آن از قاعده زیر استفاده کنند: خیابان‌ها و چهارراه‌ها طوری نامگذاری شوند که در هر چهار راهی یکی از خیابان‌ها به نام همان چهارراه باشد؛ یعنی، به عنوان مثال، بایستی یکی از خیابان‌ها به نام همان چهار راه باشد؛ یعنی به عنوان مثال، بایستی یکی از خیابان‌های منتهی به چهارراه واشینگتن به نام واشینگتن باشد.
به زبان نظریه گراف‌ها، این کار به معنی متناظر کردن هر راس با فقط یکی از یال‌های متصل به آن است. این کار در مواردی عملی نیست؛ به عنوان مثال همان‌طور که گفته شد، تعداد راس‌های هر درخت از تعداد یال‌های آن یکی بیشتر است. گراف شکل (۱) را در نظر بگیرید. در این گراف می‌توان هر راس را با یالی که از آن به سمت راس a0 خارج می‌شود متناظر کرد. به این ترتیب، به جز ریشه، هر راس با یالی متناظر می‌شود.
با توجه به حکم کلی زیر درخت‌ها از این نظر مستثنی هستند.
راس‌های گراف همبند غیر درخت را می‌توان با یال‌های متصل به آن‌ها متناظر کرد.
اثبات:هر گرافی که n راس را به هم متصل می‌کند دارای حداقل n-1 یال است و با حذف برخی از یال‌ها قابل تبدیل به درخت است. فرض کنید a0b0 = e0 یکی از یال‌هایی باشد که با حذف آن‌ها گراف ما به یک درخت، مثلا T، تبدیل می‌شود. a0 را به عنوان ریشه T انتخاب کنید. در T هر اس به جز a0 را می‌توان با یالی متصل به آن متناظر کرد؛ یال اضافی e0 از گراف را نیز می‌توان با a0 متناظر کرد. به این ترتیب هر راس گراف با یالی متصل به آن متناظر شده است.
با توجه به بحث پیشین، توجه به این نکته مفید است که همیشه می‌توان در گراف، ر اس‌ها را با یال‌های متصل به آن‌ها، یا یال‌ها را با راس‌های متصل به آنها متناظر کرد. می‌توانیم هر دو کار را انجام دهیم، اگر و تنها اگر تعداد راس‌ها و یال‌های گراف مساوی باشند. چنین گرافی نمی‌تواند درخت باشد و بنابراین، نتیجه می‌گیریم که بایستی مانند گراف شکل (۳) فقط دارای یک مدار c باشد. در واقع تناظری وجود دراد که دو سویی عمل می‌کند، یال‌ها را با راس‌ها متناظر می‌کند، و راس‌ها را با یال‌ها. کافی است یال‌های c را با راس‌های c، و هر راس غیر متعلق به c را با نزدیکترین یال متصل به آن نسبت به c متناظر کرد.