المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

یال‌های گراف سه منتظم $G$ را سه رنگ ۱، ۲ و ۳ رنگ کرده‌ایم به طوری‌که در هر راس، هر سه رنگ ظاهر شده است. یک مجموعه‌ی دلخواه $V'$ از رئوس $G$ رادر نظر می‌گیریم. فرض کنید تعداد یال‌های با رنگ ۱ که از $V'$ خارج می‌شوند $a$، تعداد یال‌های با رنگ ۲ از $V'$ خارج می‌شوند $b$ و تعداد یال‌های با رنگ ۳ که از $V'$ خارج می‌شوند $c$ باشد. ثابت کنید $a$ و $b$ و $c$ از نظر زوجیت یکسان هستند.


ابزار صفحه