جلسهی 23: مسیر، دور و کشیدن با یک خط Paths, Cycles and One Stroke
مسیر و دور در گراف، و معمای معروفِ «بدون برداشتنِ قلم بکش»: کی ممکن است و از کجا باید شروع کرد؟ بعد شمردنِ مسیرها در گرافِ جهتدار.
در این جلسه یاد میگیری
- با شمردنِ رأسهای درجهفرد میفهمی یک شکل با یک خط کشیده میشود یا نه.
- میدانی از کجا شروع کنی و کجا تمام میشود.
- مسیرها را در یک گرافِ جهتدار با جمع زدن روی رأسها میشماری.
درس
«خانهی نیکلاس»: این شکل را بدون برداشتنِ قلم و بدون دو بار کشیدنِ یک خط بکش. از هر نقطهای که شروع کنی میشود؟
قانون اویلر: وقتی از یک نقطه رد میشوی، یک خط وارد و یک خط خارج میشود؛ یعنی خطها جفتجفت مصرف میشوند. پس هر نقطهای که شروع یا پایان نیست، درجهی زوج دارد. نتیجه: یک گرافِ همبند را میشود با یک خط کشید اگر و فقط اگر ۰ یا ۲ رأسِ درجهفرد داشته باشد. با ۲ رأسِ فرد، از یکی شروع کن و در دیگری تمام میشود؛ با ۰ رأسِ فرد، از هر جا شروع کنی به همانجا برمیگردی.
در خانهی نیکلاس فقط دو گوشهی پایین درجهی ۳ (فرد) دارند؛ پس از یکیشان شروع کن!
این یکی را امتحان کن: یک مربع با هر دو قطرش. هر چهار گوشه درجهی ۳ دارند: چهار رأسِ فرد. هرگز نمیشود؛ شمردن کافی بود!
شمردنِ مسیرها در گرافِ جهتدار (یالها فلشاند): درست مثل جدول، روی هر رأس بنویس از A به چند راه به آن میرسیم = جمعِ عددهای رأسهایی که فلشی از آنها به این رأس میآید. از A (عدد ۱) شروع کن و به ترتیب جلو برو.
اشتباه رایج: قاطی کردنِ «مسیر» (هر رأس حداکثر یک بار) با «گذر اویلری» (هر یال دقیقاً یک بار).
چالشها
- Where to Start (آسان)
- The Bow Tie (آسان)
- Bridges of a River Town (متوسط)
- Fixing the Prism (متوسط)
- Paths Along the Arrows (سخت)
- Round the Grid (سخت)