موضوع مقاله: ماتریس مجاورت | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماتریس مجاورت | مقدمه: در ریاضی گسسته و دانش رایانه، ماتریس مجاورت یال‌های میان گره‌های گراف را می‌نمایاند. | ## بخش 1: ماتریس مجاورت | به سخنی دیگر، ماتریس مجاورت نشان می‌دهد که آیا جفت‌گره‌ها با یالی همسایه‌ی یکدیگرند. درایهٔ ماتریس مجاورت برای گرافی ساده نشان می‌دهد که آیا یالی میان دو گرهٔ و هست یا نه. در گرافی ناساده، درایهٔ برابر است با شمار یال‌هایی که دو گره و را به هم پیوند میزند.. در گراف ساده، درآیهٔ بودن یالی از گرهٔ به خود این گره و در گراف ناساده شمار یال‌هایی از گرهٔ به خود این گره را نشان می‌دهد. نمایش گراف با ماتریس مجاورت در گراف می‌پنداریم که گره‌ها از یک تا شمار گره‌ها شماره‌گذاری شده‌اند. اگر شمار گره‌های گراف باشد، ماتریس مجاورت درآیه دارد و هر درآیهٔ شمار یال‌های میان گره‌های شماره‌گذاری با و را نشان می‌دهد. ویژگی‌های ماتریس مجاورت ماتریس مجاورت گرافی ساده دارای ویژگی‌های زیر است: ماتریس مجاورت همامون (متقارن) است. | ## بخش 2: ماتریس مجاورت | ماتریس مجاورت گراف دو بخشی برای گرافی دوبخشی که یک بخش دارای گره و بخش دیگر دارای گره است، ماتریس مجاورت چنین است: زیرماتریس دارای درآیه است و ماتریس و به ترتیب ماتریس‌های صفر با اندازه‌های و هستند. ویژگی‌ها ماتریس مجاورت گرافی سادهٔ بی‌سو همامون (متقارن) است و بنابراین مجموعه‌ای کامل از مقدار ویژه‌های حقیقی و یک بردار ویژهٔ متعامد دارد. و هم ریخت (متناظر/isomorphic) اند، اگر و فقط اگر وجود داشته باشد ماتریس جایگشت P به طوری که : و در خصوصیات شبیه یه یکدیگرند، بنابراین، مینیمم، چندجمله‌ای، چند جمله‌ای ویژه، دترمینان و مجموع عناصر قطر داخلی آن‌ها یکسان است. با این حال ممکن است دو گراف مجموعهٔ مقدار ویژه‌های برابر داشته باشند ولی متناظر نباشند. اگر Aماتریس مجاورت گراف باسو یا با سو G باشد، ماتریس تفسیر جالبی دارد: درایهٔ ردیف i ام و ستون j ام، تعداد مسیرهای به طول n بین دو گره و را نشان می‌دهد. برای گراف (d)-منتظم (که d همچنین یک مقدار ویژهٔ A هم هست)، برای بردار ، گراف G همبند است اگر و تنها اگر تعدد dها بیش از ۱ نباشد. این جمله غلط است که: ماتریس I-A (که I ماتریس همانی n×n است) وارون پذیر هستند اگر و فقط اگر هیچ دور مستقیمی در گراف G نباشد. | ## بخش 3: ماتریس مجاورت | در این مورد، وارون این گراف یعنی چنین تفسیری دارد: درایهٔ ردیف i ام و ستون j ام، تعداد مسیرهای مستقیم از گره i به گره j را نشان می‌دهد (که اگر دور مستقیمی وجود نداشته باشد، همیشه این تعداد متناهی است.). این را می‌توان با استفاده از سری هندسی برای ماتریس‌ها فهمید : که این متناظر است با اینکه تعداد مسیرها بین i و j برابر است با تعداد مسیرها به طول ۱ بعلاوهٔ تعداد مسیرها به طول ۲، بعلاوهٔ تعداد مسیرها به طول ۳ الی آخر. چون گراف بی‌سو است، ماتریس مجاورت همامون (متقارن) است.پیوند= گراف کیلیپیوند= هم‌آرایی‌ها ۰ تا ۲۳ هستند. ساختمان داده در زمینهٔ ساختمان داده، اصلی‌ترین چیزی که با ماتریس مجاورت رقابت می‌کند، لیست مجاورت است. چون هر درایه در ماتریس مجاورت تنها ۱ بیت نیاز دارد، پس می‌توانند به صورت فشرده‌ای تنها با اشغال کردنn۲/۸ فضای پیوسته، نشان داده شوند (که n تعداد گره هاست.). علاوه بر جلوگیری از هدر رفتن فضا، این فشردگی باعث بهبود و نزدیک تر شدن مکانی ارجاع‌ها می‌شود. از طرف دیگر، در گراف‌های کم یال، لیست مجاورت برنده‌است، زیرا آن‌ها برای نشان دادن یال‌هایی که اصلاً نبوده‌اند فضایی استفاده نمی‌کنند. | ## جمع‌بندی | با استفاده از یک پیاده‌سازی ساده با آرایه بر روی یک کامپیوتر ۳۲ بیتی، یک لیست مجاورت برای یک گراف با سو حدود ۸e بایت حافظه نیاز دارد که e تعداد یال هاست.