Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

افراز به ‎K1,3

گراف مسطح ‎G‎ که همه‌ی نواحی آن (حتی ناحیه‌ی خارجی) به شکل مثلث‎ (دقیقاً‎ مفهوم هندسی مثلث مد نظر است) می‌باشند را در نظر بگیرید. از این گراف ‎۳‎ یال ناحیه‌ی بیرونی را حذف کنید و گراف حاصله را ‎H‎ بنامید.

ثابت کنید که یال‌های ‎H‎ را می‌توان به تعدادی ‎K1,3‎ افراز کرد به طوری که همه‌ی رئوس گراف به جز ‎۳‎ رأس ناحیه‌ی بیرونی ‎G‎، دقیقاً در یکی از K1,3‎ها نقش رأس مرکزی (رأ‎س مرکزی یک ‎K1,3‎، رأس درجه‌ی ‎۳‎ ی آن است) را داشته باشد. به این افراز، افراز متعادل می‌گوییم.


ابزار صفحه