درخت

$G$ را یک گراف ساده بدون جهت است که آنرا درخت می‌نامیم اگر و تنها اگر یکی از شرایط معادل زیر را داشته باشد:

1. $G$ همبند(متصل) است و دور ندارد (تعریف اصلی).
2. $G$ هیج دوری ندارد و با اضافه کردن هر یال جدید دقیقا یک دور خواهیم داشت.
3. بین هر دور رأس $G$ دقیقا یک مسیر وجود دارد.

اگر $G$ تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند: -

1. $G$ همبند است و $1$ - $n$ یال دارد.
2. $G$ دور ساده ندارد و $1$ - $n$ یال دارد.

گراف سادهٔ بدون جهت $G$ را جنگل (forest) گوئیم اگر دور ساده نداشته باشد.

درخت جهت‌دار (Directed tree) گراف جهت‌داری است که گراف زمینه آن یک درخت باشد.

درخت ریشه‌دار (Rooted tree) درختیست که یک راس آن به عنوان ریشه انتخاب شده که نسل صفر هم نامیده می‌شود راس‌هایی که به آن متصلند را فرزندان ریشه و نصل یک می‌نامیم و همین ترتیب را ادامه می‌دهیم، برای مثال در شکل روبرو راس $F$ را ریشه گرفتیم، در نتیجه $C$ و $J$ و $B$ فرزند $F$ می‌شوند. $A$ فرزند $C$ می‌شود. $K$ و $H$ فرزند $J$ می‌شوند. $D$ فرزند $B$ می‌شود. $I$ فرزند $H$ می‌شود.

نسل صفر: $F$

نسل یک: $ C و J و B $

نسل دو: $ A و H و K و D $

نسل سه: $ I $

یک درخت ریشه‌دار با ریشه‌اش و خود درخت یک‌تا تعیین می‌شود درختی که ریشه دار نباشد، درخت آزاد نام دارد.

اگر راسی که بالاتر است(نسل زودتری دارد) به راس پایین تر مسیری رو به پایین داشته باشد(مسیری که در آن نسل افزایش پیدا می‌کند)، جد راس پایین خواهد بود. برای نمونه $F$ جد بقیه رئوس است و $J$ جد $K$ و $H$ و $I$ است ولی جد $A$ نیست.

درخت چندگانه (Polytree) درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد. یعنی درخت چندگانه یک گراف جهت دار بدون مدار است که مدار بدون جهت نیز ندارد.

درخت ساده نشدنی (irreducible tree) درختی است که رأسی با درجهٔ 2 ندارد.

درخت $m$-تایی درختی است که هر رأس داخلی آن حداکثر $m$ فرزند دارد.

مرتبهٔ درخت (tree-order) یک مرتب‌سازی جزئی (partial ordering) روی رئوس درخت است که $u$ ≤ $v$ اگر و فقط اگر یک مسیر یکتا از ریشه به $v$ از $u$ بگذرد.

درخت مرتب (Ordered tree) درختی است که برای فرزندان هر رأس مرتبه‌ای تعیین شده باشد.

درخت برچسب دار (Labeled tree) درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با $n$ رأس به طور نمونه با اعداد $1$و$2$و$3$و…و$n$ برچسب گذاری می‌شوند.

درخت بازگشتی(Recursive tree) یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین می‌شود.( اگر $u$ < $v$ و $u$,$v$ دو رأس درخت باشند برچسب $u$ کوچکتر از برچسب $v$ است. )