راه‌ها و چهارراه‌ها

نقشه را می‌شود با نقطه و خط کشید. نقطه‌ها چهارراه‌اند و خط‌ها راه. چهار چهارراه با نام‌های A و B و C و D بردار و پنج راه بکش: A به B، B به C، C به D، D به A، و A به C.

نقشه به صورت گراف: چهارراه‌ها $V=\{A,B,C,D\}$ و راه‌ها $E=\{AB,BC,CD,DA,AC\}$، پس $|V|=\mathrm{۴}$ و $|E|=\mathrm{۵}$.

$G=(V,E)$ با $V=\{A,B,C,D\}$ و $E=\{AB,BC,CD,DA,AC\}$.

در هر چهارراه راه‌ها را بشمار. A سه‌تا دارد، B دوتا، C سه‌تا، D دوتا. جمعشان ده است، دو برابر شمار راه‌ها، چون هر راه دو سر دارد و در هر دو سر شمرده می‌شود.

راه‌های هر چهارراه: $\mathrm{deg}A=\mathrm{۳},\mathrm{deg}B=\mathrm{۲},\mathrm{deg}C=\mathrm{۳},\mathrm{deg}D=\mathrm{۲}$. جمعشان $\mathrm{۳}+\mathrm{۲}+\mathrm{۳}+\mathrm{۲}=\mathrm{۱۰}=۲|E|$ است، چون هر راه دو سر دارد.

$\mathrm{deg}A=\mathrm{۳},\mathrm{deg}B=\mathrm{۲},\mathrm{deg}C=\mathrm{۳},\mathrm{deg}D=\mathrm{۲}$ و $\sum \mathrm{deg}=\mathrm{۱۰}=۲|E|$.

آیا می‌شود از هر راه دقیقاً یک بار گذشت؟ بله، اگر و فقط اگر صفر یا دو چهارراه شمار فردی راه داشته باشند، و در حالت دو باید از یکی از آنها شروع کرد و به دیگری رسید. اینجا A و C فرد هستند. پس از A شروع کن: A، B، C، D، A، C. هر راه یک بار، و در C تمام می‌شود.

گشتی که از هر راه یک بار بگذرد را $W$ و تعداد چهارراه‌های فرد را $k$ بنامیم، آنگاه $W\iff k\in \{\mathrm{۰},\mathrm{۲}\}$. اینجا $k=\mathrm{۲}$ در $A$ و $C$ است، پس $A\to B\to C\to D\to A\to C$ جواب است: $\mathrm{۵}$ راه، هر کدام یک بار.

گشت $W$ و تعداد فردها $k$، آنگاه $W\iff k\in \{\mathrm{۰},\mathrm{۲}\}$. اینجا $k=\mathrm{۲}$ در $A$ و $C$ است و $A\to B\to C\to D\to A\to C$ ✓.

اگر از B شروع کنی هرگز نمی‌شود. بدون چهارراه فرد دوری داریم که به همان‌جا برمی‌گردد؛ دو چهارراه فرد گشتی از یکی به دیگری می‌دهند؛ چهار چهارراه فرد هیچ گشتی نمی‌دهند.

از $B$ نمی‌شود شروع کرد، چون $\mathrm{deg}B=\mathrm{۲}$ زوج است و برای $k=\mathrm{۲}$ باید از $A$ یا $C$ شروع کرد. $k=\mathrm{۰}$ دوری می‌دهد که به خانه برمی‌گردد و $k=\mathrm{۴}$ هیچ گشتی نمی‌دهد.

چون $\mathrm{deg}B=\mathrm{۲}$ پس شروع از $B$ ✗. $k=\mathrm{۰}$ دور و $k=\mathrm{۴}$ ✗.