$n$ شهر مهم در کشوری با جاده هایی دو به دو به هم متصل شده اند. اگر بخواهیم همهٔ این جاده ها را یک طرفه کنیم، به ازای چه $n$هایی این کار ممکن است؟

Question

می‌دانیم $n$ شهر مهم در کشوری با جاده‌هایی دو به دو به هم متصل شده‌اند. اگر بخواهیم همهٔ این جاده‌ها را یک‌طرفه کنیم به‌طوری که از هر شهر به شهر دیگری بتوان با یک یا دو جاده رفت، به‌ازای چه $n$هایی این کار ممکن است؟

Comments

به نظرم برای همه nهایی طبیعی به غیر از 2 چنین حالتی می توان انجام داد. چون برای هر سه شهری این کار ممکنه کافی در یک جهت مثلا ساعت گرد جاده ها را جهت دار کنیم

---

@Thepythn از این به بعد، در انتهای متن پرسش‌تان به تلاش خود و اینکه چه فکرهایی تا به حال روی پرسش‌تان کرده‌اید اشاره کنید.

Answer 1

برای $n=1$ چیزی برای اثبات نمی‌ماند چون یک شهر دارید و هیچ «دو تایی» از یک چیز نمی‌توان انتخاب کرد پس از همان ابتدا چیزی برای اثبات نیست. برای $n=2$ چون پرسش گفته‌است بین هر دو شهر تنها یک یالِ یک‌طرفه باید داشته‌باشیم، پس یک یال یا از سمت گرهٔ ۱ به ۲ یا برعکس داریم. بدون کاستن از کلیت (دستِ‌بالا با یک تغییر نامگذاری، تغییر اندیس ۱ و ۲) می‌توانید فرض کنید که یال‌تان از ۱ به ۲ است. در این صورت نمی‌توان از شهرِ ۲ به شهرِ ۱ رفت. پس برای $n=2$ چنین چیزی ممکن نیست که با فقط یک یالِ یک‌طرفه بین هر دو شهر بتوان از هر شهرِ دلخواهی به شهرِ دلخواه دیگری مسیری یافت (یک مسیر، دنباله‌ای از یال‌ها است).

اکنون $n$ را بزرگتر یا مساویِ ۳ بگیرید. گرافِ سادهٔ دوریِ $C_n$ را در نظر بگیرید. این گراف $n$ گره دارد و اگر آنها را شماره‌گذاری کنید یعنی گرهٔ ۱، گرهٔ ۲، تا گرهٔ $n$ آنگاه این گراف $n$ یال دارد که $n-1$ تای آنها به شکلِ وصل‌کنندهٔ گرهٔ $i$ به گرهٔ $i+1$ هستند (برای $i=1,\dots,n-1$) و آخرین یال، گرهٔ $n$ را به گرهٔ ۱ وصل می‌کند. اکنون به این یال‌ها جهت بیفزائید به گونه‌ای که یک دورِ ساعتگرد یا پادساعتگرد داشته باشید. برای نمونه جهتِ $n-1$ یالِ نخست را از $i$ به $i+1$ بگیرید و جهتِ یالِ آخر را از $n$ به ۱. با همین تعداد یال شما می‌توانید بین هر دو شهرِ دلخواهی یک مسیر بیابید، یا به اصطلاح، گرافت‌تان همبندِ قوی است. اکنون چون پرسش گفته‌است بین هر دو شهر یک یال نگه می‌داریم پس اگر $n$ عددی غیر از ۳ یعنی بزرگتر یا مساوی ۴ باشد، هنوز گره‌هایی هستند که باید یال‌های بین‌شان را تعیین کنیم برای نمونه جهتِ یالِ بین گرهٔ ۲ و گرهٔ ۴. اما هر جهتی که برای یال‌های باقی‌مانده بردارید چون همان $n$ تا یالِ دورِ اولیه همبندیِ قوی را فراهم کرده‌است، برایتان فرقی ندارد. چون دست‌کم یک مسیر بین هر دو شهر توسط دورِ اولیه وجود دارد، حالا جهت‌های یال‌های اضافه‌تر می‌تواند یک مسیرِ کوتاه‌تر ایجاد کند یا نکند که کاری به خواستهٔ پرسش ندارد. خواستهٔ پرسش توانستن به رفتن از هر شهری به هر شهر دیگر است.

پس یک اثباتِ کامل برای اینکه خواستهٔ پرسش برای هر $n\neq 2$ ممکن است و برای $n=2$ ناممکن، ارائه دادیم.

Answer 2

برای n مساوی 1 واضح است اما برای n مساوی 2 امکان ندارد چون فقط یک جاده بین آنها وجود دارد بنابراین فقط از یک شهر به شهر دیگر می توان رفت برای n مساوی 3 کافی است سه جاده را در یک جهت مثلا ساعت گرد جهت دار کنیم با توجه به این حالت می توان به استقرا ثابت کرد که برای بقیه موارد درست است زیرا در صورتی که برای n تا درست باشه در این صورت برای n+1 ام کافی آن شهر را با دو شهر دلخواه قبلی در نظر گرفته با توجه به جهت آن دو شهر انتخاب وشهر مورد نظر بنابه حالت n مساوی 3 دو جاده را در آن جهت یک طرفه کنیم.