: قضیه اویلر

||V{maketoc}||

^@#16:

!قضیه اویلر

گراف{TEX()} {K_3} {TEX} را در نظر می گیریم – در واقع یک ((مثلث)) است که صفحه را به دو قسمت تقسیم کرده است- اگر بخواهیم اجزای صفحه را با توجه به {TEX()} {K_3} {TEX} تقسیم کنیم آنچه خواهیم داشت عبارتند از : 3 راس، 3 یال و 3 وجه که در شکل با رنگهای متفاوت مشخص شده اند.

تعداد رئوس را با {TEX()} {v} {TEX}،‌ تعداد یالها را با{TEX()} {e} {TEX} و تعداد

سطوح را با{TEX()} {f} {TEX} نشان می دهیم. یعنی در {TEX()} {K_3} {TEX}

::{picture=img/daneshnameh_up/4/4c/mco0069a.jpg}::

@@ {TEX()} {f=2} {TEX} و {TEX()} {e=3} {TEX} و {TEX()} {v=3} {TEX}@@

اگر فکر می کنید در مورد تعداد وجه ها گیج می شوید می توانید از این به بعد گرافتان را روی یک ((کره)) فرض کنید. در این صورت شاید از لحاظ شهودی بهتر باشد:

::{picture=img/daneshnameh_up/8/8c/mco0069b.jpg}::

حال یک گراف دلخواه بکشید. مثلاً من گراف زیر را انتخاب می کنم.

حالا {TEX()} {e,v} {TEX} را برای گرافی که رسم کرده اید حساب کنید. مثلاً من گراف زیر{TEX()} {(R)} {TEX} را انتخاب می کنم: مثلاً من خواهم داشت

@@{TEX()} {v=17} {TEX} و {TEX()} {e=18} {TEX} و {TEX()} {f=3} {TEX}@@

یک چیز عجیب!

::{picture=img/daneshnameh_up/5/55/mco0069c.jpg}::

عدد زیر {TEX()} {(C)} {TEX} را برای این گراف و {TEX()} {K_3} {TEX} حساب می کنیم.

@@{TEX()} {C=v-e+f} {TEX}@@

@@برای گراف {TEX()} {K_3} {TEX} : {TEX()} {C=3-3+2=2} {TEX}@@

@@برای گراف{TEX()} {R} {TEX} : {TEX()} {C=17-18+3=2} {TEX} @@

می بینیم که برای هر دو گراف عدد {TEX()} {C} {TEX}برابر 2 به دست می آید- اگر شما به عدد 2 نرسیده اید دوباره بشمارید و نیز دقت کنید هیچ دو یالی همدیگر را قطع نکرده باشند- این موضوع در نظر اول عجیب می رسد ولی با اثبات قضیه زیر در خواهیم یافت که عدد{TEX()} {C} {TEX} برای هر گراف مسطح 2 می باشد.

این قضیه به قضیه ی چند وجهی اولر معروف است که اویلر آن را در سال 1750 کشف کرده است.

البته ریاضیدانان قبل از ((اویلر)) مانند ((دکارت)) و ((فرما)) نیز از این موضوع بی اطلاع نبوده اند ولی آنها قضیه را به صورت کلی و در همه ی حالات و با اثبات کامل نمی دانسته اند. شبیه این فرمول در مواقع تعمیم آن در توپولوژی جبری ( یکی از شاخه های مهم ریاضی محض ) با عنوان قضیه اویلر-پوانکاره معروف است.

---

!قضیه. ( فرمول چند وجهی اویلر )

اگر گراف مسطح {TEX()} {G} {TEX} روی صفحه ( کره ) رسم شده باشد به طوری که دارای{TEX()} {V} {TEX} راس، {TEX()} {e} {TEX} یال و {TEX()} {f} {TEX} وجه باشد آنگاه داریم:

@@{TEX()} { C(G)= v- e + f= 2 } {TEX}@@

__اثبات__

حکم را با استقرا بر روی تعداد دورهای ((گراف)) اثبات می کنیم. ابتدا فرض می کنیم که {TEX()} {G} {TEX} دارای هیچ دوری نباشد، یعنی {TEX()} {G} {TEX} یک درخت است. به راحتی دیده می شود که {TEX()} {f=1} {TEX} و {TEX()} {v = e + 1} {TEX} در نتیجه

@@{TEX()} { C ( G ) = v - e + f = e + 1 - e + 1 = 2 } {TEX}@@

حال فرض می کنیم فرمول اویلر برای گرافهای همبند ترسیم شده روی صفحه با کمتر از {TEX()} {n} {TEX} دور صحیح باشد. گراف همبند{TEX()} {G} {TEX} شامل {TEX()} {n} {TEX} دور را در نظر می گیریم که در آن{TEX()} {f,e,v} {TEX} را مانند قبل، به ترتیب تعداد راس ها، یالها و وجه ها فرض می کنیم.یک وجه گراف مانند {TEX()} {C} {TEX} را در نظر می گیریم که در واقع یک دور نیز می باشد. یکی از اضلاع وجه {TEX()} {C} {TEX} را که {TEX()} {E,P} {TEX}نام گذاری می کنیم نیز فرض می گیریم. یال {TEX()} {P} {TEX} در واقع مرز بین وجه {TEX()} {C} {TEX} با وجه دیگری مانند{TEX()} {C^\prime} {TEX} است. پس اگر یال{TEX()} {P} {TEX} را فرض کنیم گراف حاصل یعنی {TEX()} {G - P} {TEX} دارای{TEX()} {v} {TEX} راس،‌ {TEX()} {e - 1} {TEX} یال و {TEX()} {f - 1} {TEX} وجه خواهد شد ( وجوه {TEX()} {C} {TEX} و {TEX()} {C^\prime} {TEX} یکی شده اند‌). پس از تعداد دورها نیز یکی کم می شود چرا که از تعداد وجه ها یکی کم شده – پس فرمول اویلر طبق فرض استقرا برای {TEX()} {G - P} {TEX} صدق خواهد کرد.

یعنی داریم:

@@{TEX()} { v - (e - 1) + (f - 1) = 2 } {TEX}@@

پس خواهیم داشت:

@@{TEX()} { v - e + f = 2 } {TEX}@@

پس طبق استقرا حکم نتیجه می شود.

---

!تعریف

گراف مسطح {TEX()} {G} {TEX} را یک ((ماکسیمال)) مسطح نامیم هر گاه با اضافه کردن یک یال بین هر کدام از دو راس غیر مجاور، گراف {TEX()} {G} {TEX} به گرافی نامسطح تبدیل شود. گراف مکعبی زیر یک گراف مسطح نیست چرا که با اضافه کردن یالی که به عنوان {TEX()} {e} {TEX} مشخص شده است،‌ گراف مسطح باقی می ماند،‌ گراف 8 وجهی یک گراف ماکسیمال مسطح است، هم چنین {TEX()} {K_5-e} {TEX} نیز یک گراف ماکسیمال مسطح است ({TEX()} {e} {TEX} هر یک از یالهای {TEX()} {K_5} {TEX} می تواند باشد. ). گراف {TEX()} {K_4} {TEX} نیز یک گراف ماکسیمال مسطح است. با توجه به مثالهای فوق مشاهده شکل های آنها ویژگی مشترکی مابین این گرافهای ماکسیمال مسطح می بینیم که آن مثلثی بودن هر یک از وجوه این گرافهاست- در واقع به سادگی می بینیم که این ویژگی در میان همه ی گرافهای نامسطح وجود دارد- چرا که اگر وجهی غیر مثلثی وجود داشته باشد،‌ می توان هر یک از قطرهای این وجه در صورت رسم شدن مسطح بودن گراف به هم نمی خورد. مساله را در شکل زیر بهتر می توانید ببینید:

:: {picture=img/daneshnameh_up/9/98/mco0069d.jpg}::

---

!قضیه

اگر{TEX()} {G} {TEX} یک گراف ماکسیمال مسطح با {TEX()} {v} {TEX} راس و {TEX()} {e} {TEX} یال باشد و{TEX()} {V \ge 3} {TEX} آنگاه{TEX()} {e=3V-6} {TEX}.

__اثبات__

گراف ماکسیمال مسطح {TEX()} {G} {TEX} با{TEX()} {f} {TEX} وجه را در نظر گیرید. هر وجه آن بزرگتر یا مساوی6 می باشد و {TEX()} {G} {TEX} دارای {TEX()} {V} {TEX} راس و {TEX()} {e} {TEX} یال است. پس داریم:

@@{TEX()} {2q= \sum_{P\in V} deg(P) \ge 6V} {TEX}@@

بنابراین:

#@

@#16:

@@{TEX()} {e \ge 3V} {TEX}@@

که تناقض با ین قضیه است که در گراف های مسطح{TEX()} {e \le 3V-6} {TEX}.

---

!قضیه

{TEX()} {G} {TEX} را گرافی ماکسیمال مسطح با{TEX()} {V} {TEX} راس و{TEX()} {e} {TEX} یال در نظر می گیریم که{TEX()} {V \ge 4} {TEX} .

{TEX()} {V_i} {TEX}را راسهای از درجه ی{TEX()} {i} {TEX} نام گذاری می کنیم. خواهیم داشت:

@@{TEX()} {3V_3+2V_4+V_5=12+V_7+2V_8+3V_9+4V_{10}+\cdots } {TEX}@@

__اثبات__

داریم

@@{TEX()} {V=V_3+V_4+V_5+\cdots } {TEX}@@

@@{TEX()} {2e=3V_3+4V_4+5V_5+\cdots } {TEX}@@

از آنجا که {TEX()} {G} {TEX} ماکسیمال مسطح است خواهیم داشت{TEX()} {e=3V-6} {TEX}، حال معادله ی اول را در 6 ضرب کرده و معادله ی دوم را از آن کم می کنیم. در نتیجه :

@@{TEX()} {6V-2e=3V_3+2V_4+V_5-V_7-2V_8-3V_9-4V_{10} +\cdots} {TEX}@@

@@{TEX()} {\Rightarrow 3V_3+2V_4+V_5=12+V_7+2V_8+3V_9+4V_{10} +\cdots} {TEX}@@

حال این مساله را می خواهیم برای گراف های دو بخشی بررسی کنیم. در اولین نگاه می بینیم که گراف های دو بخشی هیچ مثلثی را شامل نمی شوند. پس هیچ گراف دو بخشی ماکسیمال مسطح وجود ندارد. گراف مکعبی مثالی از یک گراف دو بخشی مسطح است که دیدیم ماکسیمال مسطح نیست. در واقع با اضافه کردن هر یال به این گراف،‌ گراف از حالت دو بخشی بودن یا مسطح بودن خارج می شود. حال قضیه ی زیر را اثبات می کنیم:

---

!قضیه

هر گاه {TEX()} {G} {TEX} گرافی مسطح و دو بخشی با {TEX()} {v} {TEX} راس و {TEX()} {e} {TEX} یال باشد و {TEX()} {V\ge 3} {TEX} خواهیم داشت{TEX()} {e \le 2V-4} {TEX}.

__اثبات__

اثبات مانند معادل همین قضیه برای گراف های مسطح است که کمی قبل اثبات کردیم.

با این تفاوت که در اینجا در حالت ماکسیمال همه ی وجه ها مربعی شکل هستند. پس خواهیم داشت:

@@{TEX()} {2e \ge 4f \ \Rightarrow \ e \ge 2f} {TEX}@@

یعنی :

@@{TEX()} {v-e+\frac{e}{2} \ge 2 \ \Rightarrow \ 2v-e \ge 4 \ \Rightarrow \ e \le 2v-4} {TEX}@@

---

!قضیه

گراف دو بخشی کامل {TEX()} {K_{3,3}} {TEX} نامسطح است.

__اثبات__

در {TEX()} {K_{3,3}} {TEX} داریم: {TEX()} {\Leftarrow e=9,v=6} {TEX}

@@{TEX()} {9 \ge 2\times 6-4} {TEX}@@

---

!قضیه

هر گراف مسطحی شامل حداقل یک راس از درجه ی کوچکتر یا مساوی 5 می باشد.

__اثبات__

فرض کنیم این چنین نباشد - یعنی گراف مسطح {TEX()} {G} {TEX} موجود است که درجه هر راس آن طبق آنچه که در بالا گفته شد یک مثلث بوده و دقیقاً‌ بوسیله 3 یال احاطه گشته است.

از آنجا که هر یال متعلق به دو وجه است خواهیم داشت{TEX()} {2e=3f} {TEX}. برای آگاهی از درستی این تساوی وجه ها و یال ها را از دو راه می شمریم. فرض کنیم {TEX()} {h} {TEX} تعداد دوتایی های{TEX()} {(t,p)} {TEX} باشد که در آن {TEX()} {t} {TEX} یک مثلث و {TEX()} {p} {TEX} یالی از {TEX()} {t} {TEX} است. از آنجا که هر مثلث شامل 3 یال و در کل {TEX()} {f} {TEX} مثلث وجود دارد خواهیم داشت{TEX()} {h= 3 f} {TEX}. همچنین هر یال گراف در بین دو وجه مشترک می باشد. پس اگر بخواهیم {TEX()} {h} {TEX} را با شمردن یالها حساب کنیم کافیست هر یال را دو بار بشماریم،‌ یعنی{TEX()} {h= 2 e} {TEX} :

پس داریم:

@@{TEX()} {3 f = 2 e \ \Rightarrow \ f=\frac{2}{3}e} {TEX}@@

از طرفی داریم گراف {TEX()} {G} {TEX} مسطح است یعنی طبق قضیه قبل:

@@{TEX()} {V - e + f = 2} {TEX}@@

خواهیم داشت:

@@{TEX()} {V - e+\frac{2}{3} e = 2 \ \Rightarrow \ 3V - e = 6 \ \Rightarrow \ e = 3V - 6} {TEX}@@

قضیه بعد نتیجه ی فوری این قضیه است:

---

!قضیه

هیچ گراف مسطحی با{TEX()} {V\ge 3} {TEX} راس،‌ بیش از {TEX()} {3V - 6} {TEX} یال ندارد.

---

!قضیه

گراف {TEX()} {K_5} {TEX} مسطح نیست.

__اثبات__

در گراف {TEX()} {K_5} {TEX} داریم{TEX()} {V=5,e=10} {TEX} یعنی {TEX()} {e>3\times 5-6=9} {TEX} پس طبق قضیه ی قبل{TEX()} {K_5} {TEX} نامسطح است.

بدیهی و مشهود است که هر گرافی که شامل زیر گرافی غیر مسطح باشد،‌ خود غیر مسطح است.

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

!قضیه ( کوراتووسکی{TEX()} {Kuratowski} {TEX} )

گراف {TEX()} {G} {TEX}مسطح است اگر و تنها اگر شامل هیچ زیر گراف یک ریخت با{TEX()} {K_5} {TEX} یا {TEX()} {K_{3,3}} {TEX} نباشد.

---

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

[http://Olympiad.roshd.ir/computer/content/pdf/0117.pdf]

---

!همچنین ببینید

*(( نمایش گراف مسطح با خطوط راست ))

*((گرافهای سکه ای ))

#@^