برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: در گراف می‌پنداریم که گره‌ها از یک تا شمار گره‌ها () شماره‌گذاری شده‌اند. اگر شمار گره‌های گراف باشد، ماتریس همسایگی درآیه دارد و هر درآیۀ شمار یال‌های میان گره‌های شماره‌گذاری با و را نشان می‌دهد. اگر گراف ساده باشد، درآیۀ تنها می‌تواند صفر یا یک باشد. ارزش صفر نشان دهندۀ نبود یال است و ارزش یک نشان‌دهندۀ بودن یال. ماتریس همسایگی گرافی ساده دارای ویژگی‌های زیر است: ماتریس همسایگی همامون (متقارن) است. در گراف کامل، همۀ درایه‌های ماتریس همسایگی جز درایه‌های قطر یک‌اند. همۀ درایه‌های ماتریس همسایگی گرافی تهی صفر اند. برای گرافی دوبخشی که یک بخش دارای گره و بخش دیگر دارای گره است، ماتریس همسایگی چنین است: زیرماتریس دارای درآیه است و ماتریس و به ترتیب ماتریس‌های صفر با اندازه‌های و هستند. گاه این ماتریس، ماتریس همسایگی دوبخشی نیز خوانده می‌شود. ماتریس همسایگی گرافی ساده بی‌سو همامون (متقارن) است و بنابراین مجموعه‌ای کامل از مقدار ویژه‌های حقیقی و یک بردار ویژه متعامد دارد. (basis) مجموعه مقدار ویژه‌های یک گراف، طیف آن گراف را تشکیل می‌دهند. فرض کنید ۲ گراف (باسو یا با سو) و با ماتریس همسایگی‌های و داده شده‌اند. و هم ریخت (متناظر / isomorphic) اند، اگر و فقط اگر وجود داشته باشد ماتریس جایگشت p به طوری که: و در خصوصیات شبیه یه یکدیگرند، بنابراین، مینیمم، چندجمله‌ای، چند جمله‌ای ویژه، دترمینان و مجموع عناصر قطر داخلی آن‌ها یکسان است. در نتیجه به عنوان گراف‌های متناظر یکدیگر در نظر گرفته می‌شوند. با این حال ممکن است دو گراف مجموعه مقدار ویژه‌های برابر داشته باشند ولی متناظر نباشند. اگر aماتریس همسایگی گراف باسو یا با سو g باشد، ماتریس تفسیر جالبی دارد: درایه ردیف i ام و ستون j ام، تعداد مسیرهای به طول n بین دو گره و را نشان می‌دهد. قطر اصلی ماتریس همسایگی هر گراف بدون طوقه‌ای، تماما صفر است. برای گراف (d) -منتظم (که d همچنین یک مقدار ویژه a هم هست)، برای بردار، گراف g همبند است اگر و تنها اگر تعدد dها بیش از ۱ نباشد. می‌توان نشان داد که اگر g گراف همبند دوبخشی باشد، –d نیز یک مقدار ویژه آن است. تمام اینها نتایج نظریه پرن-فربنیوس (perron–frobenius theorem) است. این جمله غلط است که: ماتریس i-a (که i ماتریس همانی n×n است) وارون‌پذیر هستند اگر و فقط اگر هیچ دور مستقیمی در …
برداشت:
در ریاضی گسسته و دانش رایانه ، ماتریس همسایگی یال‌های میان گره‌های گراف را می‌نمایاند . به سخنی دیگر ، ماتریس همسایگی نشان می‌دهد که آیا جفت‌گره‌ها با یالی همسایه‌ی یکدیگرند . در گراف‌های ناساده ، این ماتریس شمار یال‌های میان جفت‌گره‌ها را نمایش می‌دهد . برای گراف با گره ، اندازۀ ماتریس همسایگی × است . درایهٔ ماتریس همسایگی برای گرافی ساده نشان می‌دهد که آیا یالی میان دو گرۀ و هست یا نه.در گرافی ناساده ، درایهٔ برابر است با شمار یال‌هایی که دو گره و را به هم پیوند میزند . در گراف ساده ، درآیۀ بودن یالی از گرۀ به خود این گره و در گراف ناساده شمار یال‌هایی از گرۀ به خود این گره را نشان می‌دهد .