: درخت «گراف»

V{maketoc}




-	{picture file=img/daneshnameh_up/Tree1.gif}	+	{picture=Tree1.gif}

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

!تعریف ها:

یک درخت از شرایط زیر پیروی می کند.

*در آن هیچ ((مدار)) یا حلقه ای موجود نیست.

*درخت یک ((گراف همبند)) است.

*با حذف یک یال از درخت، دیگر آن گراف یک درخت نخواهد بود.

*هر دو راس در یک درحت بوسیله مسیر منحصر به فرد به هم متصل می شوند.

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

*T یک درخت است.

*T مداری ندارد و n-1 یال دارد.

*T همبند است و n-1 یال دارد.

*هر دو راس T با ((مسیر)) منحصر به فرد به هم متصل می شوند.

*T مداری ندارد و با افزودن یگ یال جدید دقیقاً یک مدار بوجود می آید.

!مثال:

در شکل درختی با 6 راس و 5 یال وجود دارد مقدار یالها برابر 5 = 1- 6 است. و بین دو راس 2 و 6 دقیقاً یک مسیر وجود دارد که عبارت است از 6-5-4-2

!بیشتر بدانیم:

((درخت مولد گراف)) مانند G بزرگترین گراف درختی مانند T در G است که با افزودن یک یال از درخت بودن خارج می شود و واضح است اگر یک گراف n راس و m یال داشته باشد آن گاه درخت مولد n-1 یال داشته و باید __m >= n-1__ باشد.

تعداد درخت های مولد متمایز برای گراف کامل با n راس برابر {TEX()} {n^{n-2}} {TEX}است. این قضیه به ((قضیه کایلی)) معروف است.

تعداد درخت هایی که با n راس با درجات {TEX()} {d_1, d_2, \ldots, d_n} {TEX} می توان ساخت برابر مقدار زیر است:

::{TEX()} {{n-2 \choose d_1-1, d_2-1, \ldots, d_n-1}} {TEX}::

!همچنین ببینید:

((نظریه گراف))

((فهرست انواع درخت «گراف»|فهرست انواع درخت))

((درخت و هیدروکربنها))