المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:گراف:سوال ۶

تبدیل افراز

یک جهت‌دهی ستاره‌ای در سؤال قبل برای گراف ‎$H$‎ از روی یک افراز متعادل به این شکل به دست می‌آید که کافیست یال‌های هر ‎$K_{1,3}$‎ را طوری جهت‌دهی کنیم که از رأس مرکزی آن خارج شوند. حال دو جهت‌دهی ‎$D_1$‎ و ‎$D_2$‎ را در نظر بگیرید.

ثابت کنید ‎$D_1$‎ و ‎$D_2$‎ با عمل چرخش به هم قابل تبدیل‌اند.

عمل چرخش در یک گراف جهت‌دار به این صورت است که یک دور جهت‌دار در آن انتخاب می‌کنیم و جهت همه‌ی یال‌های آن دور را برعکس می‌کنیم.


ابزار صفحه