Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

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


ابزار صفحه