شبكه‌ي رشد > المپياد كامپيوتر > مسابقه - فرمول اويلر (مسابقه‌ي شماره‌‌ي 49)

مسابقه‌ی تصادفی

فرمول اويلر (مسابقه‌ي شماره‌‌ي 49)

فرمول اويلر (مسابقه‌ي شماره‌‌ي 49)مسابقه كامپيوتر

رابطه‌ي بين تعداد رؤوس، يال‌ها و وجوه در يك گراف مسطح

فرمول اويلر

سؤال

ثابت كنيد در يك «گراف مسطح» (صفحه‌اي) اگر

تعداد رأس‌ها،

تعداد يال‌ها،

تعداد وجوه و

تعداد گراف‌ها باشد رابطه‌ي ذيل صادق خواهد بود:

(رابطه‌ي 1)

راهنمايي

منظور از «گراف مسطح» (صفحه‌اي) گرافي است كه در يك صفحه بدون تقاطع يال‌ها رسم شود و «گراف غيرمسطح» (غيرصفحه‌اي) گرافي است كه رسم آن در يك صفحه بدون تقاطع يال‌هايش ممكن نيست.

1386/10/21

لينک مستقيم

پاسخ دهيد (1)

فرستنده :

علیرضا شفائی

1386/10/23

مـتـن :

من مسئله را قبل از حل یک خورده دستکاریش کردم. چون برام مفهومی نداشت.
وجوه را گرفتم ناحیه و تعداد گراف را هم گرفتم تعداد مولفه ها.

برای k=1 روی n استقرا میزنم.میگم چی؟
برای N=1 . اگر گرافمون یال نداشته باشه . e=0 n=1 پس f=1 خواهد بود که درسته. اگر یال داشته باشه که طوقه است با اضافه کردن هر یال به تعداد ناحیه ها هم اضافه میشه (دقیقا در ازای هر یک طوقه یک ناحیه اضافه میشه). پس همچنان فرمول n-e+f=2 برقرار میمونه.
برای N های بزرگتر از 1. فرض میکنیم برای N درست باشه میریم سر N+1
از اونجایی که در اول مسئله تعداد مولفه هارا گرفتم 1 . پس گرافمون باید همبند باشه. پس حتما یالی داریم که طوقه نیست(چرا؟ چون اگر همش طوقه باشه یعنی بین مثلا دو راس uوV هیچ یالی نیست پس همبند نیست.)
میاییم روی اون یال عملیات Contraction را انجام میدیم!
Contraction چیست؟
Contraction را اینطوری تعریف میکنیم. این عمل روی یک یال اینطوریه که میاد یالی که به U و V وصله را پاک میکنه. سپس Uرا روی V یا V را روی U مینشاند!. فایده اش اینه که از مجموعه روس و یالها یکی کم میشه ولی گراف خاصیتهایی مثله تعداد ناحیه را حفظ میکنه.(ببخشید نمیدونم ترجمه به کار رفته در کتب گراف فارسی چیه)
اون یاله که طوقه نیست را انتخاب میکنم وقتی روی گراف N+1 راسی این کار را میکنم یک گراف جدید با N راس میده که طبق فرض مسئله برای گراف ها با N راس معادله صدق میکنه. پس با اضافه کردن یک راس و یک یال معادله هیچ فرقی نمیکنه چون داریم n-e
و از طرفی تعداد ناحیه ها هم ثابته.(یک جور تناظر بین این دوتا گراف در نظر گرفتم) به این ترتیب اثبات شد که این معادله برای گراف هایی با 1 مولفه درسته.

برای K>1 میاییم گرافها را با اضافه کردن K-1 یال به گرافهایی با 1 مولفه تبدیل میکنیم. تعداد ناحیه ها ثابت میمونه(چرا؟ میتونید هر مولفه را یک راس در نظر بگیرید. حالا میخواییم یک درخت درست کنیم. به n-1 یال نیاز داریم. همونطور که در درختها یک ناحیه بیشتر نیست. همانند حالت اولیه بدون n-1 یال باز هم تعداد ناحیه ها ثابت میمونه. چیزه خیلی تابلوییه فکر نکنم بیشتر از این توضیح بخواد)
معادله ما میشه:
n-(e+k-1)+f=2
n-e-k+1+f=2
n-e+f=k+1
که به این ترتیب گزاره اصلی ما ثابت میشه.

خیلی مسئله ی قشنگی بود . فردا امتحان ترم ادبیات داریم. هنوز شعر حفط نکردم D:
همه ی ذهنم مشغول این بود. نمیشد چیزی حفظ کرد!
بهرام که گور میگرفتی همه عمر. دیدی که چگونه گور بهرام گرفت؟

اگر امکانش هست همین روال را طی کنید و هر هفته مسئله را سخت تر کنید. اینطوری خیلی خیلی بهتر میشه!

باتشکر
ع.ش

پاسـخ :

ايميل فرستنده: a.shafaei@gmail.com
تاريخ ارسال: 1386/10/23

عليرضا جان!
از اين‌كه به ما در تعريف اصطلاح‌هاي «گراف» چنين با رعايت اخلاق كمك مي‌كني تشكر مي‌كنيم.
از اين‌كه به سؤال‌ها با دقت جواب مي‌دي تشكر مي‌كنيم. موفقيت روزافزون تو رو خواستاريم!

	نظر شما پس از تاييد در سايت قرار داده خواهد شد

نام :
پست الکترونيکي :
صفحه شخصي :
نظر:





تایید انصراف

بازديدها

	كاربران غيرعضو آنلاين: 2
	كاربران عضو آنلاين: 0
	کل كاربران آنلاين: 2

سرویس‌های رشد:

فهرست: