ماتریس همسایگی

در ریاضی گسسته و دانش رایانه، ماتریس همسایگی یال های میان گره های گراف را می نمایاند. به سخنی دیگر، ماتریس همسایگی نشان می دهد که آیا جفت گره ها با یالی همسایه ی یکدیگرند. در گراف های ناساده، این ماتریس شمار یال های میان جفت گره ها را نمایش می دهد. برای گراف G {\displaystyle G} با n {\displaystyle n} گره، اندازۀ ماتریس همسایگی n {\displaystyle n} × n {\displaystyle n} است. درایهٔ a i j {\displaystyle a_{ij}} ماتریس همسایگی برای گرافی ساده نشان می دهد که آیا یالی میان دو گرۀ v i {\displaystyle v_{i}} و v j {\displaystyle v_{j}} هست یا نه. در گرافی ناساده، درایهٔ a i j {\displaystyle a_{ij}} برابر است با شمار یال هایی که دو گره v i {\displaystyle v_{i}} و v j {\displaystyle v_{j}} را به هم پیوند میزند. در گراف ساده، درآیۀ a i i {\displaystyle a_{ii}} بودن یالی از گرۀ v i {\displaystyle v_{i}} به خود این گره و در گراف ناساده شمار یال هایی از گرۀ v i {\displaystyle v_{i}} به خود این گره را نشان می دهد. برای هر گراف، ماتریس همسایگی یکتایی هست.
ماتریس همسایگی همامون (متقارن) است.
در گراف کامل، همۀ درایه های ماتریس همسایگی جز درایه های قطر یک اند.
همۀ درایه های ماتریس همسایگی گرافی تهی صفر اند.
در گراف G = ( V , E ) {\displaystyle G=(V,E)}   می پنداریم که گره ها از یک تا شمار گره ها ( | V | {\displaystyle |V|}  ) شماره گذاری شده اند. اگر شمار گره های گراف n {\displaystyle n}   باشد، ماتریس همسایگی n × n {\displaystyle n\times n}   درآیه دارد و هر درآیۀ a i j {\displaystyle a_{ij}}   شمار یال های میان گره های شماره گذاری با i {\displaystyle i}   و j {\displaystyle j}   را نشان می دهد. اگر گراف ساده باشد، درآیۀ a i j {\displaystyle a_{ij}}   تنها می تواند صفر یا یک باشد. ارزش صفر نشان دهندۀ نبود یال است و ارزش یک نشان دهندۀ بودن یال.
ماتریس همسایگی گرافی ساده دارای ویژگی های زیر است:
برای گرافی دوبخشی که یک بخش دارای r {\displaystyle r}   گره و بخش دیگر دارای s {\displaystyle s}   گره است، ماتریس همسایگی A {\displaystyle A}   چنین است: