۲۰ امتحان نهایی / نمونه سؤال گسسته / نمایش گراف
رأس، یال، جدول

نمونه سؤال ماتریس مجاورت؛
ترتیب رأس‌ها را در سطر و ستون یکسان نگه دار

هر خانهٔ ماتریس می‌گوید رأس سطر با رأس ستون مجاور است یا نه. پیش از پرکردن جدول، نوع گراف و ترتیب رأس‌ها را مشخص کن؛ تغییر ترتیب، ماتریس را تغییر می‌دهد اما ممکن است ساختار گراف همان باشد.

[A]

گراف پایه

گراف ساده و بدون جهت G

ترتیب رأس‌ها: 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 نوشته است. خطا چیست؟

پاسخ تشریحی

تفسیر خانه‌ها مبهم و کنترل تقارن مختل می‌شود. باید ترتیب رأس‌ها برای سطر و ستون یکسان و آشکار باشد؛ سپس هر خانه یک زوج مشخص را نشان می‌دهد.

کارت کنترل ماتریس

  1. نوع گراف و ترتیب رأس‌ها را نوشتم.
  2. برای هر یال، خانه یا خانه‌های درست را پر کردم.
  3. قطر اصلی را با وجود حلقه کنترل کردم.
  4. در گراف بدون جهت، تقارن و مجموع سطرها را سنجیدم.
  5. مجموع همهٔ درایه‌ها را با دو برابر تعداد یال‌ها مقایسه کردم.

برای کاربرد این نمایش در ساختارهای بی‌دور، نمونه سؤال درخت گراف را حل کن.