تعریفها و نتایج اولیه
درخت یک گراف همبند بدون دور است.
جنگل یک گراف بدون دور است. پس هر مولفه همبندی جنگل، درخت است.
هر راس درجه 1 در درخت را یک برگ مینامیم.
تعریفها و نتایج اولیه
یک درخت فراگیر از گراف G یک زیردرخت فراگیر از آن است که درخت باشد.
درخت با یک راس را درخت بدیهی مینامیم.
تعریفها و نتایج اولیه
قضیه: درخت T دارای n راس و n-1 یال است.
قضیه: بین هر دو راس از درخت دقیقا یک مسیر وجود دارد.
نتیجه: هر یال درخت یک پل است.
قضیه: هر درخت غیر بدیهی دارای حداقل 2 برگ است.
قضیه: اگر بزرگترین درجه راسی درخت T برابر با باشد، آنگاه T دارای حداقل برگ است.
درخت ریشه‌دار
درخت جهتدار T گراف جهتداری است که گراف زمینه آن درخت باشد.
درخت
ریشه‌دار T درخت جهتداری است که راسی مانند r به نام ریشه داشته باشد به
طوری که از ریشه به هر راس دیگر مسیر جهتداری وجود داشته باشد.
درخت ریشه‌دار
اگر
T یک درخت ریشه دار باشد، معمول است T طوری رسم شود که ریشه در بالاترین
سطح (سطح صفر)، راس‌های مجاور آن در سطح یک و به همین صورت راس‌های مجاور
راس‌های هر سطح i در سطح i+1 قرار گیرند. در این صورت جهت کمان ها در نمایش
حذف می‌شود.
بزرگترین سطح در درخت را ارتفاع درخت مینامیم.
درخت ریشه‌دار
قضیه:
درخت جهتدار T ریشه دار است اگر و تنها اگر T شامل راسی مانند r باشد به
طوری که id(r) = 0 و برای هر راس دیگر u داشته باشیم id(u) = 1
ایده اثبات: اگر T درخت ریشه دار باشد، حکم به وضوح برقرار است.
فرض
کنید T درخت جهتدار با شرط داده شده باشد. یک راس دلخواه u انتخاب کنید.
id(u) = 1، پس کمان ورودی (v,u) وجود دارد. اگر v = r مساله حل شده است. در
غیر این صورت v هم یک کمان ورودی دارد. با ادامه این روند مسیری جهتدار از
r به u تعیین می‌شود.
درخت ریشه‌دار
در درخت ریشه دار T،
اگر کمان (w,v) وجود داشته باشد، v فرزند w و w پدر v است.
اگر مسیر جهتداری از u به v وجود داشته باشد، u جد v و
V نوه u است.
زیردرخت ریشهداری که از راس u و همه نوادگان
آن تشکیل می‌شود، زیردرخت ماکسیمال T با ریشه
u نام دارد و با نماد T( u ) نشان داده می‌شود.
درخت ریشه‌دار
درخت ریشه دار T را m-تایی مینامیم هرگاه هر راس آن حداکثر m فرزند داشته باشد.
درخت m-تایی را تام مینامیم هرگاه هر راس m یا صفر فرزند داشته باشد.
درخت m-تایی را متعادل مینامیم هرگاه همه برگهای آن در سطح h یا h-1 قرار داشته باشند.
اگر m=2 باشد درخت را دودویی مینامیم.
