تبلیغات
علوم و تکنولوژی و اطلاعات عمومی - اصل درخت(گراف)
 
درباره وبلاگ



مدیر وبلاگ : حامد ژرفی
مطالب اخیر
نویسندگان
نظرسنجی
نظر شما در مورد این وبلاگ چیست؟








جستجو

آمار وبلاگ
  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :
علوم و تکنولوژی و اطلاعات عمومی




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

تعریف ها:

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

اگر یک جنگل با 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 راس با درجات می توان ساخت برابر مقدار زیر است:





نوع مطلب :
برچسب ها :
لینک های مرتبط :


شنبه 13 آذر 1389 :: نویسنده : حامد ژرفی
نظرات ()
سه شنبه 10 مرداد 1396 10:49 ق.ظ
Greetings! I know this is somewhat off topic but I was wondering which
blog platform are you using for this website? I'm getting fed up of Wordpress because I've had
issues with hackers and I'm looking at options for another platform.
I would be great if you could point me in the direction of a good platform.
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر