درخت
تعریف
همبند(متصل) است و دور ندارد (تعریف اصلی). هیج دوری ندارد و با اضافه کردن هر یال جدید دقیقا یک دور خواهیم داشت.- بین هر دور رأس
دقیقا یک مسیر وجود دارد.
اگر
همبند است و - یال دارد. دور ساده ندارد و - یال دارد.
جنگل
گراف سادهٔ بدون جهت
درخت جهت دار
درخت جهتدار (Directed tree) گراف جهتداری است که گراف زمینه آن یک درخت باشد.
درخت ریشه دار
درخت ریشهدار (Rooted tree) درختیست کهیک راس آن به عنوان ریشه انتخاب شده که نسل صفر هم نامیده میشود راسهایی که به آن متصلند را فرزندان ریشه و نصل یک مینامیم و همین ترتیب را ادامه میدهیم، برای مثال در شکل روبرو راس
نسل صفر:
نسل یک:
نسل دو:
نسل سه:
یک درخت ریشهدار با ریشهاش و خود درخت یکتا تعیین میشود درختی که ریشه دار نباشد، درخت آزاد نام دارد.
اگر راسی که بالاتر است(نسل زودتری دارد) به راس پایین تر مسیری رو به پایین داشته باشد(مسیری که در آن نسل افزایش پیدا میکند)، جد راس پایین خواهد بود. برای نمونه
درخت چندگانه
درخت چندگانه (Polytree) درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانهیک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد.
درخت ساده نشدنی
درخت ساده نشدنی (irreducible tree) درختی است که رأسی با درجهٔ 2 ندارد.
درخت -تایی
درخت
مرتبه درخت
مرتبهٔ درخت (tree-order) یک مرتبسازی جزئی (partial ordering) روی رئوس درخت است که
درخت مرتب
درخت مرتب (Ordered tree) درختی است که برای فرزندان هر رأس مرتبهای تعیین شده باشد.
درخت برچسب دار
درخت برچسب دار (Labeled tree) درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با
درخت بازگشتی
درخت بازگشتی(Recursive tree) یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین میشود.( اگر