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

در ریاضی گسسته و دانش رایانه، ماتریس مجاورت یال های میان گره های گراف را می نمایاند. به سخنی دیگر، ماتریس مجاورت نشان می دهد که آیا جفت گره ها با یالی همسایه ی یکدیگرند. در گراف های ناساده، این ماتریس شمار یال های میان جفت گره ها را نمایش می دهد. برای گراف G با n گره، اندازهٔ ماتریس مجاورت n × n است. درایهٔ a i j ماتریس مجاورت برای گرافی ساده نشان می دهد که آیا یالی میان دو گرهٔ v i و v j هست یا نه. در گرافی ناساده، درایهٔ a i j برابر است با شمار یال هایی که دو گره v i و v j را به هم پیوند میزند. [ ۱] در گراف ساده، درآیهٔ a i i بودن یالی از گرهٔ v i به خود این گره و در گراف ناساده شمار یال هایی از گرهٔ v i به خود این گره را نشان می دهد. برای هر گراف، ماتریس مجاورت یکتایی هست.
در گراف G = ( V , E ) می پنداریم که گره ها از یک تا شمار گره ها ( | V | ) شماره گذاری شده اند. اگر شمار گره های گراف n باشد، ماتریس مجاورت n × n درآیه دارد و هر درآیهٔ a i j شمار یال های میان گره های شماره گذاری با i و j را نشان می دهد. اگر گراف ساده باشد، درآیهٔ a i j تنها می تواند صفر یا یک باشد. ارزش صفر نشان دهندهٔ نبود یال است و ارزش یک نشان دهندهٔ بودن یال.
ماتریس مجاورت گرافی ساده دارای ویژگی های زیر است:
• ماتریس مجاورت همامون ( متقارن ) است.
• در گراف کامل، همهٔ درایه های ماتریس مجاورت جز درایه های قطر یک اند.
• همهٔ درایه های ماتریس مجاورت گرافی تهی صفر اند.
برای گرافی دوبخشی که یک بخش دارای r گره و بخش دیگر دارای s گره است، ماتریس مجاورت A چنین است:
A = ( 0 r , r B B T 0 s , s )
زیرماتریس B دارای r × s درآیه است و ماتریس 0 r , r و 0 s , s به ترتیب ماتریس های صفر با اندازه های r × r و s × s هستند. گاه این ماتریس، ماتریس مجاورت دوبخشی نیز خوانده می شود.
ماتریس مجاورت گرافی سادهٔ بی سو همامون ( متقارن ) است و بنابراین مجموعه ای کامل از مقدار ویژه های حقیقی و یک بردار ویژهٔ متعامد دارد. ( basis ) مجموعهٔ مقدار ویژه های یک گراف، طیف آن گراف را تشکیل می دهند. فرض کنید ۲ گراف ( باسو یا با سو ) G 1 و G 2 با ماتریس مجاورت های A 1 و A 2 داده شده اند. G 1 و G 2 هم ریخت ( متناظر/isomorphic ) اند، اگر و فقط اگر وجود داشته باشد ماتریس جایگشت P به طوری که  :