نوشتن دور

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

ایده

دور به طول $n$ دنبالهٔ $v_{۱} v_{۲} \dots v_{n} v_{۱}$ است: $n$ رأس دو به دو متمایز که هر رأس با رأس بعدی مجاور است و رأس آخر دوباره به رأس اول برمی‌گردد. پس رأس اول را در انتها یک بار دیگر می‌نویسی، و طول دور همان تعداد رأس‌ها (و یال‌ها) است. رأسی که فقط یک همسایه دارد یا تنهاست روی هیچ دوری نیست.

نمونهٔ نهایی

نهایی شهریور ۱۴۰۲، سؤال ۸، بخش د۰/۵ نمره

گراف $G$ به‌صورت زیر رسم شده است. باتوجه به این گراف به سؤالات زیر پاسخ دهید.

گراف G با رأس‌های a، b، c، d، e، f و g؛ رأس g تنهاست و بقیه با یال‌ها به هم وصل‌اند

د)

دوری به طول $۴$ در این گراف بنویسید.

رأس‌هایی را که درجه‌شان $۱$ یا $۰$ است کنار بگذار، چون روی هیچ دوری نیستند.
$de g b = ۱, de g d = ۱, de g g = ۰ \Rightarrow a می‌ماند, c, e, f$
چهار رأس مانده را پشت‌سرهم بگذار، طوری که هر دو رأس متوالی مجاور باشند و آخر به $a$ برگردد.۰/۵ نمره
$a, c, e, f, a (a c, ce, e f, f a)$

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

امتحان نهایی ۱۹

۱۳ سؤال دیگر