المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

قضیه‌ی چهار رنگ بیان می‌کند که رئوس هر گراف مسطح با ۴ رنگ قابل رنگ‌آمیزی است. با استفاده از این قضیه، ثابت کنید که هرگاه $G$ یک گراف مسطح همبند و بدون یال برشی باشد، می‌توان یال‌های $G$ را به گونه‌ای جهت داد و روی هر یک از یال‌ها یکی از عددهای ۱، ۲، ۳ یا ۴ را نوشت، به طوری که هر راس $v$ از $G$ که در نظر بگیریم، مجموع عددهای یال‌های خروجی $v$ (در گراف جهت‌دار شده) برابر با مجموع عددهای یال‌های ورودی $v$ باشد.


ابزار صفحه