منو
 کاربر Online
857 کاربر online

درخت «گراف»

چاپ



img/daneshnameh_up/d/d1/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 راس برابر است. این قضیه به قضیه کایلی معروف است.
تعداد درخت هایی که با n راس با درجات می توان ساخت برابر مقدار زیر است:



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

نظریه گراف
فهرست انواع درخت
درخت و هیدروکربنها
تاریخچه پیدایش درخت «گراف»



تعداد بازدید ها: 55987


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..