روش حل تست گراف و مدل‌سازی گسسته؛ از متن سؤال تا مسیر و درجه

اولین نقطه توقف را پیدا کن؛ گراف یک فصل مستقل است

صفحه رسمی شبکه رشد، «گراف و مدل‌سازی» را فصل دوم کتاب ریاضیات گسسته پایه دوازدهم معرفی می‌کند. برای تعیین دامنه دقیق مطالعه، نسخه رسمی کتاب پایه و رشته خودت را ملاک بگیر؛ عنوان فصل، فهرست‌های غیررسمی یا سؤال‌های سال‌های قبل به‌تنهایی جای منبع درسی همان دوره را نمی‌گیرند.

پیش از شروع تمرین، چهار سؤال کوتاه با صورت‌های متفاوت بردار و بدون زمان حل کن. کنار هرکدام نخستین توقف را ثبت کن: انتخاب رأس، تعریف یال، رسم بدون جاافتادگی، شمارش درجه، تشخیص مسیر و دور یا استخراج نتیجه از مدل. عبارت «گراف بلد نیستم» واحد تمرین نمی‌سازد؛ اما «در متن، یال را با مسیر اشتباه می‌گیرم» دقیق و قابل ترمیم است.

اگر هنوز در کل درس گسسته مسیر مطالعه روشنی نداری، ابتدا راهنمای عمومی این درس را ببین و بعد برای تمرین تخصصی گراف به همین صفحه برگرد. موضوع‌های این خوشه نیز در صفحه روش مطالعه و یادگیری کنار هم قرار گرفته‌اند.

• نسخه رسمی کتاب را مبنای دامنه قرار بده
• چهار صورت سؤال متفاوت انتخاب کن
• نخستین تصمیم شکسته را نام ببر
• فقط همان مهارت را با سؤال تازه بسنج

مطالعه مرتبط: راهنمای مطالعه گسسته، آمار و احتمال، صفحه موضوعی روش مطالعه و یادگیری

متن سؤال را به فرهنگ مدل تبدیل کن

قبل از رسم، یک فرهنگ دوخطی بنویس: «هر رأس نماینده چیست؟» و «وجود هر یال دقیقاً چه معنایی دارد؟». اگر شهرها رأس و جاده مستقیم میان دو شهر یال باشند، رسیدن با چند جاده یک مسیر است، نه یک یال تازه. همین جداسازی جلوی اضافه‌کردن ارتباط‌هایی را می‌گیرد که متن نگفته است.

واژه‌های طبیعی همیشه معنای ریاضی ثابتی ندارند. «ارتباط»، «همسایگی» یا «دسترسی» را از تعریف همان سؤال بخوان. ممکن است رابطه دوطرفه باشد، ممکن است جهت اهمیت داشته باشد یا برای هر ارتباط عددی مانند هزینه نوشته شده باشد. فقط ویژگی‌ای را وارد شکل کن که متن یا تعریف مسئله آن را پشتیبانی می‌کند.

شرط‌ها را نیز کنار فرهنگ مدل بنویس: تکرار ارتباط مجاز است یا نه، یک شیء می‌تواند به خودش وصل شود یا نه و آیا همه رأس‌ها باید در یک بخش متصل باشند؟ اگر سؤال در چارچوب گراف ساده است، آن شرط را پیش از استفاده از رابطه‌های شمارشی ثبت کن؛ فرمول درست روی مدل نامتناسب جواب معتبر نمی‌سازد.

• رأس = شیء یا وضعیت
• یال = رابطه مستقیم تعریف‌شده
• مسیر = زنجیره‌ای از یال‌ها
• عدد کنار یال = فقط در صورت تعریف سؤال
• قیدهای مدل = پیش از رسم

شکل را منظم بساز، نه لزوماً شبیه واقعیت

رأس‌ها را ابتدا با نام‌های کوتاه فهرست کن و برای هر داده یک‌بار تصمیم بگیر کدام دو رأس را وصل می‌کند. در مسئله‌های متنی، ساخت یک جدول کوچک از زوج‌های متصل پیش از رسم، احتمال حذف یا دوباره‌کشیدن یال را کم می‌کند. بعد شکل را طوری بچین که تقاطع خط‌ها کمتر شود؛ محل رأس روی کاغذ معمولاً بخشی از تعریف گراف نیست مگر اینکه سؤال ویژگی هندسی خاصی داده باشد.

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

پس از رسم، متن را یک دور از ابتدا بخوان و هر داده را روی مدل نشان بده. سپس جهت معکوس را کنترل کن: هر یال رسم‌شده باید یک شاهد در متن یا تعریف داشته باشد. این ممیزی رفت‌وبرگشتی هم جاافتادگی را پیدا می‌کند و هم یال‌های ساخته‌شده از حدس را.

درجه‌ها را بشمار و با مجموع درجه‌ها کنترل کن

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

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

زوج‌بودن مجموع درجه‌ها شرط لازم است، اما هر فهرست عددیِ با مجموع زوج الزاماً دنباله درجه یک گراف ساده نیست. هر درجه باید با تعداد رأس‌ها و محدودیت‌های اتصال سازگار باشد و یال‌های لازم واقعاً قابل ساختن باشند. در سؤال «آیا چنین گرافی وجود دارد؟» فقط یک کنترل عددی را به‌جای ساخت یا استدلال کامل نگذار.

• درجه هر رأس را جدا ثبت کن
• مجموع درجه‌ها را حساب کن
• آن را با دو برابر تعداد یال‌ها بسنج
• حد بالای درجه را با مدل کنترل کن
• شرط لازم را با شرط کافی اشتباه نگیر

گراف کامل و متمم را از زوج‌های ممکن بساز

در گراف ساده با n رأس، هر رأس می‌تواند به n−1 رأس دیگر وصل شود. چون هر یال از دو سر شمرده می‌شود، گراف کامل n(n−1)/2 یال دارد. این رابطه را از شمارش زوج‌های متمایز رأس‌ها بازسازی کن تا در سؤال‌هایی که یک محدودیت اضافه دارند، صرفاً به فرمول حفظی وابسته نباشی.

در متمم یک گراف ساده، همان مجموعه رأس‌ها حفظ می‌شود و هر زوجِ نامتصل در گراف اصلی، در متمم به هم وصل است. بنابراین برای هر رأس، درجه آن در گراف و متممش روی‌هم n−1 می‌شود. تعداد یال‌های دو گراف نیز باید در مجموع به تعداد یال‌های گراف کامل برسد.

برای جلوگیری از جابه‌جایی، دو ستون «هست» و «نیست» بساز و زوج‌های رأس را فقط یک‌بار بررسی کن. متمم به معنای پاک‌کردن رأس‌های جداافتاده یا رسم یک گراف دلخواه با تعداد یال مکمل نیست؛ هویت همه رأس‌ها و وضعیت تک‌تک زوج‌ها باید حفظ شود.

مطالعه مرتبط: حل زنجیره‌های طولانی در تست‌های چندمرحله‌ای

راه، مسیر، دور و همبندی را با تعریف بررسی کن

وقتی سؤال درباره حرکت روی گراف است، ابتدا بنویس چه چیزی اجازه تکرار دارد: رأس، یال یا هیچ‌کدام. نام‌گذاری‌ها را از تعریف کتاب همان درس بردار و روی یک نمونه کوچک اجرا کن؛ شباهت واژه‌های «راه» و «مسیر» نباید باعث شود شرط تکرار در میانه حل عوض شود.

برای تشخیص همبندی، کافی نیست شکل یکپارچه به نظر برسد. از یک رأس شروع کن و رأس‌های قابل دسترس را مرحله‌به‌مرحله علامت بزن. اگر رأسی بیرون ماند، مؤلفه دیگری داری. در مسئله‌های حذف یال یا رأس نیز همین فرایند دسترسی را پس از تغییر دوباره اجرا کن؛ نتیجه شکل قبلی را ذهنی ادامه نده.

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

• واحد پیمایش را مشخص کن
• قانون تکرار را بنویس
• دسترسی رأس‌ها را علامت بزن
• یال‌محوربودن اویلر را از رأس‌محوربودن همیلتون جدا کن
• نتیجه را با یک مسیر واقعی کنترل کن

درخت را با همبندی و نبود دور کنترل کن

درخت یک گراف همبند و بدون دور است. برای گراف متناهی ساده با n رأس، داشتن n−1 یال همراه با همبندی، ساختار درخت را نتیجه می‌دهد؛ اما شمارش n−1 یال به‌تنهایی کافی نیست، چون ممکن است بخشی دور داشته باشد و رأس دیگری جدا مانده باشد.

میان هر دو رأس یک درخت دقیقاً یک مسیر وجود دارد. اگر یالی به درخت اضافه کنی، یک دور ساخته می‌شود؛ اگر یکی از یال‌هایش را حذف کنی، اتصال می‌شکند. این ویژگی‌ها را به‌صورت تصویر ذهنی حفظ نکن: روی یک درخت کوچک تغییر را انجام بده و مسیرها را دوباره دنبال کن.

در مسئله مدل‌سازی، «کمترین تعداد ارتباط برای متصل‌ماندن همه نقاط» می‌تواند نشانه فکرکردن به درخت باشد، اما باید محدودیت‌های واقعی سؤال را هم رعایت کنی. هزینه، ممنوعیت بعضی اتصال‌ها یا الزام به عبور از نقاط خاص ممکن است انتخاب یال‌ها را عوض کند؛ n−1 فقط تعداد لازم در یک درخت با n رأس را می‌گوید، نه اینکه هر انتخابی از این تعداد یال پاسخ مسئله است.

سؤال ترکیبی را به مدل، ناوردا و خواسته بشکن

اگر سؤال چند تغییر پیاپی دارد، همه را روی یک شکل شلوغ اجرا نکن. زنجیره را بنویس: «تعریف رأس و یال ← مدل اولیه ← تغییر داده‌شده ← ویژگی ثابت یا متغیر ← خواسته». پس از هر تغییر فقط رأس‌ها، یال‌ها و درجه‌های اثرگرفته را ثبت کن. این کار معلوم می‌کند کدام نتیجه هنوز معتبر است.

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

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

مطالعه مرتبط: روش انتخاب و تحلیل پاسخ‌نامه تست، حل تست احتمال و ترکیبیات به‌عنوان نیت جداگانه

برنامه هفت‌روزه برای انتقال روش به سؤال تازه

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

روز ششم چند مسئله درخت و یک سؤال چندمرحله‌ای را بدون فشار زمان حل کن. روز هفتم یک بسته تازه و مخلوط بردار و سه شاهد ثبت کن: چند مدل بدون اصلاح ساخته شد، چند کنترل ناسازگاری را پیدا کرد و چند پاسخ بدون دیدن راه‌حل کامل شد. درصد به‌تنهایی نشان نمی‌دهد ترجمه متن بهتر شده یا فقط شکل سؤال‌ها آشنا بوده است.

وقتی در چند سؤال تازه می‌توانی فرهنگ مدل را مستقل بنویسی، شکل را ممیزی و پاسخ را با یک رابطه یا مسیر واقعی کنترل کنی، بسته کوتاه زمان‌دار اضافه کن. اگر زمان‌گیری باعث حذف تعریف یال یا کنترل نهایی شد، تعداد سؤال‌ها را کم کن و همان زنجیره را حفظ کن.

• روز ۱: فرهنگ رأس و یال
• روز ۲: رفت‌وبرگشت فهرست و شکل
• روز ۳: درجه و شمارش یال
• روز ۴: کامل و متمم
• روز ۵: مسیر، دور و همبندی
• روز ۶: درخت و سؤال چندمرحله‌ای
• روز ۷: بسته تازه و سنجش انتقال

جمع‌بندی: اول رابطه را تعریف کن، بعد شکل بکش

حل تست گراف با تشخیص چند شکل آماده کامل نمی‌شود. ابتدا معنای رأس و یال و قیدهای مدل را بنویس، اتصال‌ها را بدون جاافتادگی رسم کن و سپس از درجه، شمارش زوج‌ها، همبندی یا ویژگی درخت برای استدلال استفاده کن. هر رابطه باید به همان مدلی تعلق داشته باشد که صورت سؤال تعریف کرده است.

بعد از خطا، به‌جای حفظ پاسخ، نخستین حلقه شکسته را ترمیم کن: ترجمه، رسم، تعریف، شمارش یا کنترل. یک سؤال تازه با ظاهر متفاوت نشان می‌دهد روش منتقل شده است. این روال گراف را از مجموعه‌ای از شکل‌ها به مدلی قابل ممیزی برای حل مسئله تبدیل می‌کند.