ریاضیات گسسته، فصل ۲، درس ۱

شمردن مسیرها و دورها

نهایی: در ۳ امتحان از ۲۶، روی‌هم ۲/۵ نمره

ایده

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

نمونهٔ نهایی

نهایی دی ۱۳۹۹، سؤال ۸، بخش ب۱/۵ نمره

گراف به صورت مقابل را در نظر بگیرید.

گراف با رأس‌های a، b، c، d و e و یال‌های ab، ac، bc، bd، be و cd
ب)

تمام دورهای موجود در گراف را بنویسید.

  1. رأس فقط یک همسایه دارد و روی هیچ دوری نیست؛ پس دورها فقط روی هستند.

  2. دورهای به طول را از سه رأس دو به دو مجاور بساز؛ اولین مثلث از و و است.۰/۵ نمره

  3. مثلث دیگر را با و و بساز.۰/۵ نمره

  4. دور به طول را پیدا کن: چهار رأس را طوری پشت‌سرهم بگذار که هر دو رأس متوالی مجاور باشند.۰/۵ نمره

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

همهٔ سؤال‌های این تیپ