گراف

در نظریه گراف، یک درخت گرافی است که هر دو راس آن بوسیله دقیقاً یک یال به هم متصل شده اند، یک جنگل گرافی است که دو راس آن با بیشتر از یک راس به هم متصل اند. یک جنگل در واقع از اتصال، مجموعه ای از درخت ها به وجود می آید.

تعریف ها:
یک درخت از شرایط زیر پیروی می کند.

در آن هیچ مدار یا حلقه ای موجود نیست.
درخت یک گراف همبند است.
با حذف یک یال از درخت، دیگر آن گراف یک درخت نخواهد بود.
هر دو راس در یک درحت بوسیله مسیر منحصر به فرد به هم متصل می شوند.

اگر یک جنگل با n راس باشد آن گاه از شرایط زیر پیروی می کند:

T یک درخت است.
T مداری ندارد و n-1 یال دارد.
T همبند است و n-1 یال دارد.
هر دو راس T با مسیر منحصر به فرد به هم متصل می شوند.
T مداری ندارد و با افزودن یگ یال جدید دقیقاً یک مدار بوجود می آید.