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

مرتب سازی
بدون خلاصۀ ویرایش
(مرتب سازی)
 
* G متصل است و n-1 یال دارد.
* G مدار ساده ندارد و n-1 یال دارد.
گراف سادهٔ بدون جهت 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>Free tree</ref> گوییم.
درخت چندگانه<ref>Polytree</ref> درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک [[گراف جهت دار]] بدون مدار است که مدار بدون جهت نیز ندارد.
 
* درخت '''چندگانه'''<ref>Polytree</ref> درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک [[گراف جهت دار]] بدون مدار است که مدار بدون جهت نیز ندارد.
درخت برچسب دار<ref>Labeled tree</ref> درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به‌طور نمونه با اعداد ۱و۲و۳و… وn برچسب گذاری می‌شوند. درخت بازگشتی<ref>Recursive tree</ref> یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین می‌شود. (اگر <math>u<v</math> و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است)
 
* درخت '''برچسب دار'''<ref>Labeled tree</ref> درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به‌طور نمونه با اعداد ۱و۲و۳و… وn برچسب گذاری می‌شوند. درخت '''بازگشتی'''<ref>Recursive tree</ref> یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین می‌شود. (اگر <math>u<v</math> و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است)
درخت ساده نشدنی<ref>irreducible tree</ref> درختی است که رأسی با درجهٔ ۲ ندارد.
 
* درخت مرتب'''ساده نشدنی'''<ref>Orderedirreducible tree</ref> درختی است که برای فرزندان هر رأسرأسی مرتبه‌ایبا تعییندرجهٔ شده۲ باشدندارد.
 
* درخت n-تایی'''مرتب'''<ref>Ordered tree</ref> درختی است که هربرای رأسفرزندان کههر برگ نیسترأس حداکثرمرتبه‌ای nتعیین فرزندشده داردباشد.
 
* درخت '''n-تایی''' درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد.
 
درخت نمایش داده شده در شکل بالا ۶ رأس، ۱–۶ = ۵ یال دارد. مسیر سادهٔ یکتا که رأس ۲ را به ۶ وصل می‌کند ۶-۵-۴-۲ است.
۱۰۳

ویرایش