ماتریس مجاورت گراف؛ درجه، یال و شمارش پیمایشها
آموزش ساخت ماتریس مجاورت، تشخیص درجه رأسها، تعداد یالها و مفهوم توانهای ماتریس در تست گراف.
پاسخ کوتاه
ماتریس مجاورت نمایش جبری یک گراف است. با شمارهگذاری رأسها، وجود هر یال را در یک درایه ثبت میکنیم و سپس از مجموع سطرها، تقارن ماتریس و توانهای آن اطلاعات ساختاری گراف را به دست میآوریم.
ساخت ماتریس
برای رأسهای v1 تا vn، درایه a_ij برابر یک است اگر vi و vj مجاور باشند و در غیر این صورت صفر است. در گراف ساده بدون حلقه، درایههای قطر اصلی صفرند. ترتیب رأسها شکل ماتریس را عوض میکند اما خود گراف ثابت میماند.
تقارن در گراف بدون جهت
اگر گراف بدون جهت باشد، مجاورت vi با vj دوطرفه است؛ پس a_ij=a_ji و ماتریس نسبت به قطر اصلی متقارن میشود. در گراف جهتدار این تقارن الزاماً وجود ندارد و مجموع سطر و ستون نقش خروجی و ورودی را دارند.
درجه و تعداد یال
در گراف ساده بدون جهت، مجموع درایههای سطر i درجه رأس vi است. مجموع همه درایهها دو برابر تعداد یالهاست، چون هر یال در دو خانه متقارن ثبت میشود. بنابراین تعداد یالها نصف مجموع کل ماتریس است.
توانهای ماتریس
درایه (i,j) از A^k تعداد پیمایشهای طول k از vi به vj را میشمارد. برای k=2، درایه خارج قطر تعداد همسایههای مشترک دو رأس و درایه قطری درجه همان رأس در گراف ساده بدون جهت است.
مثال و تست کوتاه
اگر ماتریس مجاورت سه رأس سطرهای [0,1,1]، [1,0,0] و [1,0,0] داشته باشد، درجات 2، 1 و 1 هستند. مجموع درایهها 4 است، پس گراف 2 یال دارد و رأس اول به هر دو رأس دیگر وصل است.
چکلیست حل تست
- قطر اصلی گراف ساده بدون حلقه صفر است.
- مجموع هر سطر درجه همان رأس است.
- نصف مجموع کل درایهها تعداد یالهاست.