گراف پایه
ترتیب رأسها: A,B,C,D | یالها: AB, AC, BC, CD
آموزش کامل در راهنمای ماتریس مجاورت آمده است.
بخش اول؛ ساخت ماتریس
سؤال ۱
سطر مربوط به A در ترتیب A,B,C,D چیست؟
پاسخ تشریحی
A به B و C وصل و به خودش و D وصل نیست؛ پس سطر A برابر [۰،۱،۱،۰] است.
سؤال ۲
ماتریس کامل G را بنویس.
پاسخ تشریحی
با ترتیب A,B,C,D:
[۰ ۱ ۱ ۰]
[۱ ۰ ۱ ۰]
[۱ ۱ ۰ ۱]
[۰ ۰ ۱ ۰]
سؤال ۳
چرا ماتریس بالا متقارن است؟
پاسخ تشریحی
گراف بدون جهت است؛ اگر A با B مجاور باشد، B نیز با A مجاور است. بنابراین خانهٔ (i,j) با خانهٔ (j,i) برابر میشود.
سؤال ۴
چرا قطر اصلی همه صفر است؟
پاسخ تشریحی
گراف ساده و بدون حلقه است؛ هیچ رأس به خودش یال ندارد. هر خانهٔ قطری مجاورت رأس با خودش را نشان میدهد.
بخش دوم؛ درجه و تعداد یال
سؤال ۵
درجهٔ هر رأس را از مجموع سطرها پیدا کن.
پاسخ تشریحی
درجهها: d(A)=۲، d(B)=۲، d(C)=۳ و d(D)=۱. در گراف سادهٔ بدون جهت، مجموع سطر هر رأس برابر درجهٔ آن است.
سؤال ۶
تعداد یالها را از مجموع همهٔ درایهها به دست آور.
پاسخ تشریحی
مجموع درایهها ۲+۲+۳+۱=۸ است. هر یال دو بار دیده میشود، پس تعداد یالها ۸÷۲=۴.
سؤال ۷
کدام رأس برگمانند با درجهٔ یک است و چگونه از ماتریس دیده میشود؟
پاسخ تشریحی
رأس D؛ سطر آن فقط یک درایهٔ ۱ دارد و تنها به C متصل است.
بخش سوم؛ بازسازی و تغییر ترتیب
سؤال ۸
چگونه بدون دوبارهشماری، فهرست یالها را از ماتریس متقارن استخراج میکنی؟
پاسخ تشریحی
فقط خانههای ۱ بالای قطر اصلی را میخوانیم: AB، AC، BC و CD. نیمهٔ پایین همان یالها را تکرار میکند.
سؤال ۹
اگر ترتیب رأسها D,C,B,A شود، سطر نخست چیست؟
پاسخ تشریحی
رأس D فقط به C وصل است. در ترتیب D,C,B,A، سطر نخست [۰،۱،۰،۰] است.
سؤال ۱۰
آیا متفاوتشدن ماتریس پس از تغییر ترتیب رأسها یعنی گراف عوض شده است؟
پاسخ تشریحی
نه لزوماً. اگر همان رأسها و یالها با ترتیب دیگری نوشته شوند، جای سطرها و ستونهای متناظر همزمان تغییر میکند؛ نمایش عددی فرق میکند اما ساختار ثابت میماند.
بخش چهارم؛ نوع گراف و نقد پاسخ
سؤال ۱۱
در یک گراف جهتدار، وجود یال A→B بدون B→A چه اثری بر تقارن ماتریس دارد؟
پاسخ تشریحی
خانهٔ سطر A و ستون B برابر ۱، اما خانهٔ سطر B و ستون A برابر ۰ میشود؛ بنابراین ماتریس الزاماً متقارن نیست.
سؤال ۱۲
دانشآموز سطرها را با ترتیب A,B,C,D و ستونها را با ترتیب D,C,B,A نوشته است. خطا چیست؟
پاسخ تشریحی
تفسیر خانهها مبهم و کنترل تقارن مختل میشود. باید ترتیب رأسها برای سطر و ستون یکسان و آشکار باشد؛ سپس هر خانه یک زوج مشخص را نشان میدهد.
کارت کنترل ماتریس
- نوع گراف و ترتیب رأسها را نوشتم.
- برای هر یال، خانه یا خانههای درست را پر کردم.
- قطر اصلی را با وجود حلقه کنترل کردم.
- در گراف بدون جهت، تقارن و مجموع سطرها را سنجیدم.
- مجموع همهٔ درایهها را با دو برابر تعداد یالها مقایسه کردم.
برای کاربرد این نمایش در ساختارهای بیدور، نمونه سؤال درخت گراف را حل کن.