ماتریس مجاورت
From Wikipedia, the free encyclopedia
در ریاضی گسسته و دانش رایانه، ماتریس مجاورت یالهای میان گرههای گراف را مینمایاند. به سخنی دیگر، ماتریس مجاورت نشان میدهد که آیا جفتگرهها با یالی همسایهی یکدیگرند. در گرافهای ناساده، این ماتریس شمار یالهای میان جفتگرهها را نمایش میدهد. برای گراف با
گره، اندازهٔ ماتریس مجاورت
×
است. درایهٔ
ماتریس مجاورت برای گرافی ساده نشان میدهد که آیا یالی میان دو گرهٔ
و
هست یا نه. در گرافی ناساده، درایهٔ
برابر است با شمار یالهایی که دو گره
و
را به هم پیوند میزند.[1] در گراف ساده، درآیهٔ
بودن یالی از گرهٔ
به خود این گره و در گراف ناساده شمار یالهایی از گرهٔ
به خود این گره را نشان میدهد. برای هر گراف، ماتریس مجاورت یکتایی هست.