درخت (نظریه گراف): تفاوت میان نسخهها
جز حذف رده «درختها (نظریه گراف)» (با استفاده از ردهساز) |
←تعاریف: +pic |
||
خط ۶: | خط ۶: | ||
== تعاریف == |
== تعاریف == |
||
[[تصویر:Tree1.png|thumb|200px|left|نمونهای از یک درخت]] |
|||
[[تصویر:Tree2.png|thumb|200px|left|در اینجا بدلیل وجود یک دور گراف درخت نمیباشد.]] |
|||
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند: |
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند: |
||
*G متصل است و دور ندارد. |
*G متصل است و دور ندارد. |
||
*G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود |
*G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود میآید. |
||
*G متصل است و اگر یک یال آن خذف شود دیگر متصل نیست. |
*G متصل است و اگر یک یال آن خذف شود دیگر متصل نیست. |
||
*G متصل است و گراف کامل 3 رأسی <math>K_3</math> جزِئی از آن نیست. |
*G متصل است و گراف کامل 3 رأسی <math>K_3</math> جزِئی از آن نیست. |
||
*هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل |
*هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل میشوند. |
||
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند: |
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند: |
||
خط ۱۹: | خط ۲۱: | ||
گراف سادهٔ بدون جهت G را جنگل<ref>forest</ref> گوئیم اگر مسیر ساده نداشته باشد. |
گراف سادهٔ بدون جهت G را جنگل<ref>forest</ref> گوئیم اگر مسیر ساده نداشته باشد. |
||
[[درخت جهتدار]]<ref>Directed tree</ref> گراف جهتداری است که اگر جهت روی |
[[درخت جهتدار]]<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>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>Polytree</ref> درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد. |
||
درخت برچسب دار<ref>Labeled tree</ref> درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به طور نمونه با اعداد 1و2و3و...وn برچسب گذاری |
درخت برچسب دار<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>irreducible tree</ref> درختی است که رأسی با درجه ی 2 ندارد. |
||
درخت مرتب<ref>Ordered tree</ref> درختی است که برای فرزندان هر رأس |
درخت مرتب<ref>Ordered tree</ref> درختی است که برای فرزندان هر رأس مرتبهای تعیین شده باشد. |
||
درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد. |
درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد. |
||
درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر ساده ی یکتا که رأس 2 را به 6 وصل |
درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر ساده ی یکتا که رأس 2 را به 6 وصل میکند 6-5-4-2 است. |
||
==احکام== |
==احکام== |
نسخهٔ ۱۸ مهٔ ۲۰۰۹، ساعت ۰۷:۰۷
برای دیگر معانی درخت به درخت (ابهامزدایی) نگاه کنید.
در نظریهٔ گراف، درخت گرافی است که هر دو رأس آن با دقیقا یک مسیر به هم متصل شده است. همچنین، هر گراف متصل که مدار نداشته باشد یک درخت است. جنگل، اجتماع چندین درخت است. درخت ها به طور گسترده در علوم کامپیوتر و ساختار دادهها کاربرد دارند مثل درختهای جستجوی دودویی، پشتهها[۱]، درختهای هافمن[۲] برای فشردهسازی اطلاعات و غیره.
تعاریف
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
- G متصل است و دور ندارد.
- G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود میآید.
- G متصل است و اگر یک یال آن خذف شود دیگر متصل نیست.
- G متصل است و گراف کامل 3 رأسی جزِئی از آن نیست.
- هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل میشوند.
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:
- G متصل است و n-1 یال دارد.
- G مدار ساده ندارد و n-1 یال دارد.
گراف سادهٔ بدون جهت G را جنگل[۳] گوئیم اگر مسیر ساده نداشته باشد.
درخت جهتدار[۴] گراف جهتداری است که اگر جهت روی یالهای آن را نادیده بگیریم به یک درخت تبدیل میشود.
یک درخت را ریشهدار[۵] گوییم اگر یک رأس در آن ریشه باشد. مرتبه ی درخت[۶] یک مرتبسازی جزئی[۷] روی رئوس درخت است که اگر و فقط اگر یک مسیر یکتا از ریشه به v از u بگذرد. یک درخت که زیر گراف، گراف G است را درخت نرمال[۸] گوییم اگر انتهای هر یال G با این رتبه بندی قابل مقایسه باشد ( Diestel 2005 ,p.15 ).
درخت ریشهدار یک ساختار داده کلیدی در علوم کامپیوتر است. در ضمن با توجه به این که فرض میشود درختها ریشه دارند یک درخت بدون ریشه را درخت آزاد[۹] گوییم.
درخت چندگانه[۱۰] درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد.
درخت برچسب دار[۱۱] درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به طور نمونه با اعداد 1و2و3و...وn برچسب گذاری میشوند. درخت بازگشتی[۱۲] یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبه ی درخت تعیین میشود.( اگر و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است. )
درخت ساده نشدنی[۱۳] درختی است که رأسی با درجه ی 2 ندارد.
درخت مرتب[۱۴] درختی است که برای فرزندان هر رأس مرتبهای تعیین شده باشد.
درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد.
درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر ساده ی یکتا که رأس 2 را به 6 وصل میکند 6-5-4-2 است.
احکام
- هر درخت یک گراف دو بخشی[۱۵] و یک گراف میانه[۱۶] است. هر درخت با تعداد شمارا رأس یک گراف مسطح است.
- هر درخت با حداقل 2 برگ ( یا رأس با درجه 1)دارد. حداقل تعداد برگ مربوط به گراف مسیر[۱۷] و حداکثر تعداد برگ (n-1) مربوط به گراف ستاره ای است.
- بین هر سه رأس در یک درخت سه مسیر وجود دارد که این سه مسیر حداقل در یک رأس مشترک اند.
منابع
- .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