ماتریس مجاورت
دانشنامه عمومی
در گراف 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 به طوری که :
