|
[[پرونده:Tree graph.svg|left]]
در [[نظریه گراف|نظریهٔ گراف]]، '''درخت''' گرافی همبند و بدون دور است. درخت‌ها به طور گسترده در [[علوم رایانه]] و [[ساختار داده‌ها]] کاربرد دارند. مثل [[درخت‌های جستجوی دودویی]]، [[پشته‌ها]]،<ref>Heaps</ref>، درخت‌های هافمن<ref>Huffman trees</ref> برای [[فشرده‌سازی اطلاعات]] و غیره.
== تعاریف ==
[[پرونده:Tree1.png|بندانگشتی|200px|چپ|نمونه‌ای از یک درخت]]
[[پرونده:Tree2.png|بندانگشتی|200px|چپ|در اینجا بدلیلبه دلیل وجود یک دور گراف درخت نمی‌باشد.]]
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
* G متصل است و دور ندارد.
[[درخت جهت‌دار]]<ref>Directed tree</ref> گراف جهت‌داری است که گراف زمینه آن یک درخت باشد.
یک درخت را ریشه‌دار<ref>Rooted tree</ref> گوییم اگر راسی داشته باشد که به ازای هر راس دیگر درخت، مسیری از آن به راس مذکور وجود داشته باشد. مرتبهٔ درخت<ref>tree-order</ref> یک [[مرتب‌سازی جزئی]]<ref>partial ordering</ref> روی رئوس درخت است که <math>u\le v</math> اگر و فقط اگر یک مسیر یکتا از ریشه به v از u بگذرد. یک درخت که زیر گراف، گراف G است را درخت نرمال<ref>Normal tree</ref> گوییم اگر انتهای هر یال G با این رتبه بندیرتبه‌بندی قابل مقایسه باشد ( Diestel 2005 ,p.15 ).
درخت ریشه‌دار یک [[ساختار داده]] کلیدی در علوم کامپیوتر است. در ضمن با توجه به این که فرض می‌شود درخت‌ها ریشه دارند یک درخت بدون ریشه را درخت آزاد<ref>Free tree</ref> گوییم.
درخت چندگانه<ref>Polytree</ref> درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک [[گراف جهت دار]] بدون مدار است که مدار بدون جهت نیز ندارد.
درخت برچسب دار<ref>Labeled tree</ref> درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به طور نمونه با اعداد 1و2و3و...۱و۲و۳و… وn برچسب گذاری می‌شوند. درخت بازگشتی<ref>Recursive tree</ref> یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین می‌شود.( (اگر <math>u<v</math> و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است. )
درخت ساده نشدنی<ref>irreducible tree</ref> درختی است که رأسی با درجهٔ 2۲ ندارد.
درخت مرتب<ref>Ordered tree</ref> درختی است که برای فرزندان هر رأس مرتبه‌ای تعیین شده باشد.
درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد.
درخت نمایش داده شده در شکل بالا 6۶ رأس، 1 -6۱–۶ = 5۵ یال دارد. مسیر سادهٔ یکتا که رأس 2۲ را به 6۶ وصل می‌کند 6۶-5۵-4۴-2۲ است.
== احکام ==
* هر درخت یک گراف دو بخشی<ref>bipartite graph</ref> و یک گراف میانه<ref>Median graph</ref> است. هر درخت با تعداد شمارا رأس یک [[گراف مسطح]] است.
* هر درخت با <math>n\le 2</math> حداقل 2۲ برگ ( یا رأس با درجه 1۱)دارد. حداقل تعداد برگ مربوط به گراف مسیر<ref>Path graph</ref> و حداکثر تعداد برگ (n-1) مربوط به گراف ستاره‌ای است.
== کاربرد ==
<span style="font-size: large;">''' خیابان هاخیابان‌ها و چهار راه هاراه‌ها :'''</span> ▼
تغییر نام [[ خیابان هاخیابان‌ها]] و چهارراه هاچهارراه‌ها ی عمومی یکی از سرگرمی هایسرگرمی‌های مطلوب انجمن هایانجمن‌های شهری در سراسر جهان است . فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان هایخیابان‌های خود بسیار اصولی باشند . فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه هایچهارراه‌های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشنگتنواشینگتن بایستی در چهار راه واشنگتنواشینگتن باشد. طبیعتاً می خواهیممی‌خواهیم مسئله خود را در زبان گراف هاگراف‌ها در حالتی کلی عنوان کنیم . گراف همبندی داده شده است . تحت چه شرط هایی میشرط‌هایی توانمی‌توان به طور منحصربه‌فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد ؟کرد؟▼▲<span style="font-size: large;">'''خیابان ها و چهار راه ها :'''</span>
در ابتدا خاطر نشان می کنیممی‌کنیم که اگر گرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می کنیممی‌کنیم: ▼
پس از اینکه ریشه ای مانند a0 را در درختی مانند درخت شکل زیر ▼▲تغییر نام [[خیابان ها]] و چهارراه ها ی عمومی یکی از سرگرمی های مطلوب انجمن های شهری در سراسر جهان است . فرض کنید مسئولین شهری بخواهند نسبت به نامگذاری خیابان های خود بسیار اصولی باشند . فرض کنید بخواهند هر خیابان به درازای یک بلوک و هم نام با یکی از چهارراه های دو انتهای خود باشد؛ پس به عنوان مثال، یکی از دو انتهای خیابان واشنگتن بایستی در چهار راه واشنگتن باشد. طبیعتاً می خواهیم مسئله خود را در زبان گراف ها در حالتی کلی عنوان کنیم . گراف همبندی داده شده است . تحت چه شرط هایی می توان به طور منحصربه‌فردی هر یال را با یکی از دو رأس انتهایی آن متناظر کرد ؟
▲در ابتدا خاطر نشان می کنیم که اگر گرافمان درخت باشد، این امر ممکن است. برای این منظور به طریق زیر عمل می کنیم:
▲پس از اینکه ریشه ای مانند a0 را در درختی مانند درخت شکل زیر
[[پرونده:Treef1.JPG]]
به دلخواه انتخاب کردیم، یال a1 a0 را متناظر با رأس a1 می گیریم،می‌گیریم، به همین ترتیب a0 a2 را متناظر با a2 و و a0 a3 را متناظر با a3، سپس 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۳ نگاه کنید)
[[پرونده:Tree3.JPG]]
بنا به قضیه (هر درخت با n رأس دارای n-1 یال است ) تعداد رأس هایرأس‌های یک درخت یکی بیش از تعداد یال هاییال‌های آن است . . تعداد یال هاییال‌های یک مدار یا مداری که درخت هاییدرخت‌هایی از رأس هایرأس‌های آن منشعب شده اندشده‌اند با تعداد رأس هایرأس‌های آن مساوی است.است؛ بنابراین، در این موارد برقراری تناظری میان یال هایال‌ها و رأس هارأس‌ها امکان دارد.
در ختی مانند درخت شکل (1۱) یا گرافی مانند گراف شکل (3۳)، فقط میمی‌توانند توانندنقشهٔ نقشهخیابان‌های ی خیابان های شهر هایشهرهای خیلی کوچک باشند که فاقر بلوک هایبلوک‌های شهری واقعی اند، یا فقط یک بلوک مرکزی دارند که خیابان هاییخیابان‌هایی از حومه به آنها کشیده شده است.
پس از اندکی تأمل درباره یدربارهٔ این موضوع، عضوهای انجمن شهر سرافرازانه متوجه این واقعیت می شوندمی‌شوند که شهر آن هاآن‌ها بزرکتر از آن است که بتوان این روش را در آن به کار گرفت.گرفت؛ بنابراین قرار می گذارندمی‌گذارند که به جای آن از قاعده یقاعدهٔ زیر استفاده کنند : خیابان هاخیابان‌ها و چهارراه هاچهارراه‌ها طوری نامگذاری شوند که در هر چهار راهی یکی از خیابان هاخیابان‌ها به نام همان چهارراه باشد؛ یعنی، به عنوان مثال، بایستی یکی از خیابان هاخیابان‌ها به نام همان چهار راه باشد؛ یعنی به عنوان مثال، بایستی یکی از خیابان هایخیابان‌های منتهی به چهارراه واشنگتنواشینگتن به نام واشنگتنواشینگتن باشد.
به زبان نظریهنظریهٔ ی گراف ها،گراف‌ها، این کار به معنی متناظر کردن هر رأس با فقط یکی از یال هاییال‌های متصل به آن است. .این کار در مواردی عملی نیست؛ به عنوان مثال همانطورهمان‌طور که گفته شد، تعداد رأس هایرأس‌های هر درخت از تعداد یال هاییال‌های آن یکی بیشتر است . گراف شکل (1۱) را در نظر بگیرید . در این گراف می توانمی‌توان هر رأس را با یالی که از آن به سمت رأس a0 خارج می شودمی‌شود متناظر کرد . به این ترتیب، به جز ریشه، هر رأس با یالی متناظر می شودمی‌شود.
== با توجه به حکم کلی زیر درخت هادرخت‌ها از این نظر مستثنی هستند. ==
رأس هایرأس‌های گراف همبند غیر درخت را می توانمی‌توان با یال هاییال‌های متصل به آن هاآن‌ها متناظر کرد. ▼اثبات:هر گرافی که n رأس را به هم متصل می کندمی‌کند دارای حداقل n-1 یال است و با حذف برخی از یال هایال‌ها قابل تبدیل به درخت است . فرض کنید a0b0 = e0 یکی از یال هایییال‌هایی باشد که با حذف آن هاآن‌ها گراف ما به یک درخت، مثلاً T، تبدیل می شود می‌شود. a0 را به عنوان ریشه یریشهٔ T انتخاب کنید. در T هر أس به جز a0 را می توانمی‌توان با یالی متصل به آن متناظر کرد؛ یال اضافی e0 از گراف را نیز می توانمی‌توان با a0 متناظر کرد. به این ترتیب هر رأس گراف با یالی متصل به آن متناظر شده است. ▼
با توجه به بحث پیشین، توجه به این نکته مفید است که همیشه می توانمی‌توان در گراف، ر أس هاأس‌ها را با یال هاییال‌های متصل به آن ها،آنها، یا یال هایال‌ها را با رأس هایرأس‌های متصل به آنها متناظر کرد. می توانیممی‌توانیم هر دو کار را انجام دهیم، اگر و تنها اگر تعداد رأس هارأس‌ها و یال هاییال‌های گراف مساوی باشند . چنین گرافی نمی‌تواند درخت باشد و بنابراین، نتیجه می گیریممی‌گیریم که بایستی مانند گراف شکل ( 3۳) فقط دارای یک مدار c باشد . در واقع تناظری وجود دراد که دو سویی عمل میمی‌کند، کند، یال هایال‌ها را با رأس هارأس‌ها متناظر می کند،می‌کند، و رأس هارأس‌ها را با یالیال‌ها. ها .کافی است یال هاییال‌های c را با رأس هایرأس‌های c، و هر رأس غیر متعلق به c را با نزدیکترین یال متصل به آن نسبت به c متناظر کرد . ▼▲رأس های گراف همبند غیر درخت را می توان با یال های متصل به آن ها متناظر کرد.
▲اثبات:هر گرافی که 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
* . گراف وکاربردهای آن، نویسنده:ایستین ایر
== پانویس ==
{{پانویس|۲}}
| 