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

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

ماتریس مجاورت ماتریسی است n × n که برای نمایش گراف های ساده استفاده می شود. در این ماتریس \(a_{ij}\) نشان دهنده تعداد یال های موجود بین راس i و راس j در گراف است. اگر توجه کنید می فهمید که این ماتریس متقارن است. درایه های این ماتریس صفر و یک است.

در گراف هایی با یال چندگانه و طوقه

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

در گراف های جهت دار

در گراف های جهت دار ماتریس مجاورت به این صورت تعریف می شود که \(a_{ij}\) به معنای تعداد یال هایی است که از راس i به j می رود.

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

Adjacency Matrix