ماتریس مجاورت گراف

[nafise sadeghi]

تعریف

ماتریس مجاورت گراف، ماتریس است که خصوصیات و ویژگی های یک گراف را به طور خلاصه نمایش می دهد.
ماتریس مجاورت گراف، ماتریسی است که ویژگی های زیر را دارد:
1) ماتریس مربعی است که تعداد سطر و ستون آن برابر با اندازه (تعداد راس) گراف می باشد.
2) این ماتریس فقط از اعداد یک و صفر تشکیل شده است.
3)رایه های واقع بر قطر اصلی آن فقط و فقط از صفر تشکیل شده باشد.
4)مهمتر از همه این است که این ماتریس باید متقارن باشد.
به کمک این ماتریس می توانیم به آسانی، یک گراف را رسم کنیم. هر سطر نشان می دهد که آن راس مربوط به آن سطر به چه روسی متصل است به ازای هر یالی که آن راس به راس دیگری متصل می شود، عدد یک را می گذاریم و اگر دو راس به هم متصل نباشند، عدد صفر را می گذاریم. پس تعدا یک های یک سطر درجه آن سطر می باشد.

قضایای مربوط به ماتریس مجاورت گراف:

1)اگر M ماتریس مجاورت یک گراف باشد، آنگاه درایه های واقع بر سطر iام ستون iام ماتریس M به توان دو برابر با درجه راس iام است

[nafise sadeghi]

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

تعریف ها:

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

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

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