بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 23: مسیر، دور و کشیدن با یک خط Paths, Cycles and One Stroke

مسیر و دور در گراف، و معمای معروفِ «بدون برداشتنِ قلم بکش»: کی ممکن است و از کجا باید شروع کرد؟ بعد شمردنِ مسیرها در گرافِ جهت‌دار.

در این جلسه یاد می‌گیری

درس

«خانه‌ی نیکلاس»: این شکل را بدون برداشتنِ قلم و بدون دو بار کشیدنِ یک خط بکش. از هر نقطه‌ای که شروع کنی می‌شود؟

قانون اویلر: وقتی از یک نقطه رد می‌شوی، یک خط وارد و یک خط خارج می‌شود؛ یعنی خط‌ها جفت‌جفت مصرف می‌شوند. پس هر نقطه‌ای که شروع یا پایان نیست، درجه‌ی زوج دارد. نتیجه: یک گرافِ همبند را می‌شود با یک خط کشید اگر و فقط اگر ۰ یا ۲ رأسِ درجه‌فرد داشته باشد. با ۲ رأسِ فرد، از یکی شروع کن و در دیگری تمام می‌شود؛ با ۰ رأسِ فرد، از هر جا شروع کنی به همان‌جا برمی‌گردی.
در خانه‌ی نیکلاس فقط دو گوشه‌ی پایین درجه‌ی ۳ (فرد) دارند؛ پس از یکی‌شان شروع کن!

این یکی را امتحان کن: یک مربع با هر دو قطرش. هر چهار گوشه درجه‌ی ۳ دارند: چهار رأسِ فرد. هرگز نمی‌شود؛ شمردن کافی بود!

شمردنِ مسیرها در گرافِ جهت‌دار (یال‌ها فلش‌اند): درست مثل جدول، روی هر رأس بنویس از A به چند راه به آن می‌رسیم = جمعِ عددهای رأس‌هایی که فلشی از آن‌ها به این رأس می‌آید. از A (عدد ۱) شروع کن و به ترتیب جلو برو.
اشتباه رایج: قاطی کردنِ «مسیر» (هر رأس حداکثر یک بار) با «گذر اویلری» (هر یال دقیقاً یک بار).

چالش‌ها

  1. Where to Start (آسان)
  2. The Bow Tie (آسان)
  3. Bridges of a River Town (متوسط)
  4. Fixing the Prism (متوسط)
  5. Paths Along the Arrows (سخت)
  6. Round the Grid (سخت)

← جلسه‌ی 22: گراف: نقطه‌ها و خط‌ها جلسه‌ی 24: درخت →