المپدیا

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

ابزار کاربر

ابزار سایت


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

افراز به ‎$K_{1,3}$‎

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

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


ابزار صفحه