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

در [[نظریه گراف|نظریهٔ گراف]]، '''درخت''' گرافی همبند و بدون دور است. درخت‌ها به طوربه‌طور گسترده در [[علوم رایانه]] و [[ساختار داده‌ها]] کاربرد دارند. مثل [[درخت‌های جستجوی دودویی]]، [[پشته‌ها]]،<ref>Heaps</ref> درخت‌های هافمن<ref>Huffman trees</ref> برای [[فشرده‌سازی اطلاعات]] و غیره.

درخت برچسب دار<ref>Labeled tree</ref> درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به طوربه‌طور نمونه با اعداد ۱و۲و۳و… وn برچسب گذاری می‌شوند. درخت بازگشتی<ref>Recursive tree</ref> یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین می‌شود. (اگر <math>u<v</math> و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است)

تغییر نام [[خیابان‌ها]] و چهارراه‌ها ی عمومی یکی از سرگرمی‌های مطلوب انجمن‌های شهری در سراسر جهان است. فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان‌های خود بسیار اصولی باشند. فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه‌های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشینگتن بایستی در چهار راه واشینگتن باشد. طبیعتاً می‌خواهیم مسئله خود را در زبان گراف‌ها در حالتی کلی عنوان کنیم. گراف همبندی داده شده استشده‌است. تحت چه شرط‌هایی می‌توان به طوربه‌طور منحصربه‌فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد؟

به دلخواه انتخاب کردیم، یال a1 a0 را متناظر با رأس a1 می‌گیریم، به همین ترتیب a0 a2 را متناظر با a2 و و a0 a3 را متناظر با a3، سپس a1 a11 را متناظر با a11 قرار می‌دهیم، و الی آخر؛ به طوربه‌طور کلی، هر یال را به انتهایی از آن که از a0 دور تر است، متناظر می‌کنیم.

هر یال یک [[گراف همبند]] را می‌توان به طوربه‌طور منحصربه‌فردی با یکی از دو رأس آن یال متناظر کرد اگر و تنها اگر گراف نامبرده یک درخت باشد یا متشکل از مدار منحصربه‌فردی همراه با درخت‌هایی منشعب از رأس‌های آن مدار باشد (به شکل ۳ نگاه کنید)

در ختی مانند درخت شکل (۱) یا گرافی مانند گراف شکل (۳)، فقط می‌توانند نقشهٔ خیابان‌های شهرهای خیلی کوچک باشند که فاقر بلوک‌های شهری واقعی اند، یا فقط یک بلوک مرکزی دارند که خیابان‌هایی از حومه به آنهاآن‌ها کشیده شده استشده‌است.

اثبات:هر گرافی که n رأس را به هم متصل می‌کند دارای حداقل n-1 یال است و با حذف برخی از یال‌ها قابل تبدیل به درخت است. فرض کنید a0b0 = e0 یکی از یال‌هایی باشد که با حذف آن‌ها گراف ما به یک درخت، مثلاً T، تبدیل می‌شود. a0 را به عنوان ریشهٔ T انتخاب کنید. در T هر أس به جز a0 را می‌توان با یالی متصل به آن متناظر کرد؛ یال اضافی e0 از گراف را نیز می‌توان با a0 متناظر کرد. به این ترتیب هر رأس گراف با یالی متصل به آن متناظر شده استشده‌است.

با توجه به بحث پیشین، توجه به این نکته مفید است که همیشه می‌توان در گراف، ر أس‌ها را با یال‌های متصل به آن‌ها، یا یال‌ها را با رأس‌های متصل به آنهاآن‌ها متناظر کرد. می‌توانیم هر دو کار را انجام دهیم، اگر و تنها اگر تعداد رأس‌ها و یال‌های گراف مساوی باشند. چنین گرافی نمی‌تواند درخت باشد و بنابراین، نتیجه می‌گیریم که بایستی مانند گراف شکل (۳) فقط دارای یک مدار c باشد. در واقع تناظری وجود دراد که دو سویی عمل می‌کند، یال‌ها را با رأس‌ها متناظر می‌کند، و رأس‌ها را با یال‌ها. کافی است یال‌های c را با رأس‌های c، و هر رأس غیر متعلق به c را با نزدیکترین یال متصل به آن نسبت به c متناظر کرد.