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