المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:گراف:سوال ۵

سوال ۵

گراف ساده‌ی ‎$G$‎ را در نظر بگیرید. با دو جهت‌دهی متفاوت یال‌های ‎$G$‎، به دو گراف جهت‌دار بدون دور ‎$D_1‎, ‎D_2$‎ رسیده‌ایم. در یک عمل «محاکمه‌ی وزیر»‎ روی یک گراف جهت‌دار، می‌توان جهت یک یال را برعکس کرد. ثابت کنید با تعدادی متناهی عمل محاکمه‌ی وزیر، می‌توان از گراف ‎$D_1$‎ به گراف ‎$D_2$‎ رسید؛ طوری که در حین انجام مراحل، هیچ یک از گراف‌های جهت‌داری که می‌سازیم، دور نداشته باشند.


ابزار صفحه