X
تبلیغات
رایتل

علم ریاضی

این وبلاگ جهت استفاده علاقمندان به ریاضی ایجاد شده است.
جمعه 29 دی‌ماه سال 1391

گراف

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

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

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

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

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

نظرات (0)
نام :
ایمیل : [پنهان می ماند]
وب/وبلاگ :
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)