المپدیا

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

ابزار کاربر

ابزار سایت


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

گراف یالی متناوب

از روی گراف $G$، گراف $L(G)$ را به این صورت می‌سازیم که به ازای هر یال $G$‌یک راس در $L(G)$ در نظر می‌گیریم، دو راس $L(G)$ مجاورند اگر و تنها اگر یال‌های متناظر آن‌ها در $G$‌ مجاور باشند. کلیه‌ی گراف‌های $G$ را بیابید که $L^{(k)}(G)$ به ازای یک عدد طبیعی $k$، برابر $G$ باشد. (منظور از $L^{(2)}(G)$، $L(L(G))$ می‌باشد!)


ابزار صفحه