گرافهای سکه ای




این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


گراف های سکه ای

به شکل زیر توجه کنید:
img/daneshnameh_up/d/dd/mco0073a.jpg

می بینیم که راس های گراف را می توان بدون تغییر مکان به عنوان مرکز تعدادی دایره ی مماس روی صفحه در نظر گرفت- و همچنین بین دو راس گراف یک یال می گذرد اگر و تنها اگر دایره هایی که آن دو راس مذکور مرکز آنها هستند با هم مماس باشند به این نوع گراف ها،‌ گراف سکه ای، گویند- حال آیا فکر می کنید این مساله برای هر گراف مسطحی صدق می کند؟ یعنی هر گراف مسطحی یک گراف سکه ای است؟ جواب مشکل ولی زیباست.
سال 1935،‌ کب قضیه ی زیر را بوسیله ی آنالیز مختلط حل کرد:

قضیه

هر گراف مسطح یک گراف سکه ای است.
حال هر گاه گرافی را بتوان به صورت گراف سکه ای نشان داد به قسمی که دایره هایی که راس های گراف مرکز آنهایند با هم مساوی باشند،‌ یعنی شعاع دایره ها همگی یکسان باشند،‌ به این نوع گراف ها،‌ گراف های پنی گویند – در تمرینات با برخی از گراف های پنی آشنا می شوید-

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0119.pdf




تعداد بازدید ها: 8013