ماتریس مجاورت کیست؟ توضیح بده.
در ریاضی گسسته و دانش رایانه، ماتریس مجاورت یال‌های میان گره‌های گراف را می‌نمایاند. به سخنی دیگر، ماتریس مجاورت نشان می‌دهد که آیا جفت‌گره‌ها با یالی "همسایه‌ی" یکدیگرند. در گراف‌های ناساده، این ماتریس شمار یال‌های میان جفت‌گره‌ها را نمایش می‌دهد. برای گراف formula_1 با formula_2 گره، اندازهٔ ماتریس مجاورت formula_2×formula_2 است. درایهٔ formula_5 ماتریس مجاورت برای گرافی ساده نشان می‌دهد که آیا یالی میان دو گرهٔ formula_6 و formula_7 هست یا نه. در گرافی ناساده، درایهٔ formula_5 برابر است با شمار یال‌هایی که دو گره formula_6 و formula_7 را به هم پیوند میزند. در گراف ساده، درآیهٔ formula_11 بودن یالی از گرهٔ formula_6 به خود این گره و در گراف ناساده شمار یال‌هایی از گرهٔ formula_6 به خود این گره را نشان می‌دهد. برای هر گراف، ماتریس مجاورت یکتایی هست.نمایش گراف با ماتریس مجاورت.در گراف formula_14 می‌پنداریم که گره‌ها از یک تا شمار گره‌ها (formula_15) شماره‌گذاری شده‌اند. اگر شمار گره‌های گراف formula_2 باشد، ماتریس مجاورت formula_17 درآیه دارد و هر درآیهٔ formula_5 شمار یال‌های میان گره‌های شماره‌گذاری با formula_19 و formula_20 را نشان می‌دهد. اگر گراف ساده باشد، درآیهٔ formula_5 تنها می‌تواند صفر یا یک باشد. ارزش صفر نشان دهندهٔ نبود یال است و ارزش یک نشان‌دهندهٔ بودن یال.ویژگی‌های ماتریس مجاورت.ماتریس مجاورت گرافی ساده دارای ویژگی‌های زیر است:ماتریس مجاورت گراف دو بخشی.برای گرافی دوبخشی که یک بخش دارای formula_22 گره و بخش دیگر دارای formula_23 گره است، ماتریس مجاورت formula_24 چنین است:formula_25زیرماتریس formula_26 دارای formula_27 درآیه است و ماتریس formula_28 و formula_29 به ترتیب ماتریس‌های صفر با اندازه‌های formula_30 و formula_31 هستند. گاه این ماتریس، ماتریس مجاورت دوبخشی نیز خوانده می‌شود.ویژگی‌ها.ماتریس مجاورت گرافی سادهٔ بی‌سو همامون (متقارن) است و بنابراین مجموعه‌ای کامل از مقدار ویژه‌های حقیقی و یک بردار ویژهٔ متعامد دارد. (basis) مجموعهٔ مقدار ویژه‌های یک گراف، طیف آن گراف را تشکیل می‌دهند.فرض کنید ۲ گراف (باسو یا با سو) formula_32 و formula_33 با ماتریس مجاورت‌های formula_34 و formula_35 داده شده‌اند. formula_32 و formula_33 هم ریخت (متناظر/isomorphic) اند، اگر و فقط اگر وجود داشته باشد ماتریس جایگشت P به طوری که :formula_38formula_34 و formula_35 در خصوصیات شبیه یه یکدیگرند، بنابراین، مینیمم، چندجمله‌ای، چند جمله‌ای ویژه، دترمینان و مجموع عناصر قطر داخلی آن‌ها یکسان است. در نتیجه به عنوان گراف‌های متناظر یکدیگر در نظر گرفته می‌شوند.با این حال ممکن است دو گراف مجموعهٔ مقدار ویژه‌های برابر داشته باشند ولی متناظر نباشند. اگر Aماتریس مجاورت گراف باسو یا با سو G باشد، ماتریس formula_41 تفسیر جالبی دارد: درایهٔ ردیف i ام و ستون j ام، تعداد مسیرهای به طول n بین دو گره formula_6 و formula_7 را نشان می‌دهد.قطر اصلیِ ماتریس مجاورتِ هر گرافِ بدون طوقه‌ای، تماماً صفر است.برای گراف (d)-منتظم (که d همچنین یک مقدار ویژهٔ A هم هست)، برای بردار formula_44، گراف G همبند است اگر و تنها اگر تعدد dها بیش از ۱ نباشد. می‌توان نشان داد که اگر G گراف همبند دوبخشی باشد،–d نیز یک مقدار ویژهٔ آن است. تمام اینها نتایج نظریهٔ پرُن-فربنیوس (Perron–Frobenius theorem) است.این جمله غلط است که: ماتریس I-A (که I ماتریس همانی n×n است) وارون پذیر هستند اگر و فقط اگر هیچ دور مستقیمی در گراف G نباشد. در این مورد، وارون این گراف یعنی formula_45 چنین تفسیری دارد:درایهٔ ردیف i ام و ستون j ام، تعداد مسیرهای مستقیم از گره i به گره j را نشان می‌دهد (که اگر دور مستقیمی وجود نداشته باشد، همیشه این تعداد متناهی است.). این را می‌توان با استفاده از سری هندسی برای ماتریس‌ها فهمید : formula_46که این متناظر است با اینکه تعداد مسیرها بین i و j برابر است با تعداد مسیرها به طول ۱ بعلاوهٔ تعداد مسیرها به طول ۲، بعلاوهٔ تعداد مسیرها به طول ۳ الی آخر.ساختمان داده.در زمینهٔ ساختمان داده، اصلی‌ترین چیزی که با ماتریس مجاورت رقابت می‌کند، لیست مجاورت است. چون هر درایه در ماتریس مجاورت تنها ۱ بیت نیاز دارد، پس می‌توانند به صورت فشرده‌ای تنها با اشغال کردنn۲/۸ فضای پیوسته، نشان داده شوند (که n تعداد گره هاست.). علاوه بر جلوگیری از هدر رفتن فضا، این فشردگی باعث بهبود و نزدیک تر شدن مکانی ارجاع‌ها می‌شود.از طرف دیگر، در گراف‌های کم یال، لیست مجاورت برنده‌است، زیرا آن‌ها برای نشان دادن یال‌هایی که اصلاً نبوده‌اند فضایی استفاده نمی‌کنند. با استفاده از یک پیاده‌سازی ساده با آرایه بر روی یک کامپیوتر ۳۲ بیتی، یک لیست مجاورت برای یک گراف با سو حدود ۸e بایت حافظه نیاز دارد که e تعداد یال هاست.