منو
 کاربر Online
578 کاربر online
تاریخچه ی: گونای گراف

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!گونای گراف
فرض کنید کره و مکعبی که در شکل زیر کشیده شده اند، هر دو توخالی بوده و از جنس لاستیک بسیار نرمی ساخته شده باشند.
::{picture=img/daneshnameh_up/8/8e/mco0075a.jpg}::
می توان کره را بدون پاره شدن و با فشردن یا کشیدن آن به مکعب تبدیل کرد. ولی‌آیا می توان کره را بدون پاره کردن به چنبره ی زیر تبدیل کرد؟
::{picture=img/daneshnameh_up/6/69/mco0075b.jpg}::
مطمئن باشید این کار نشدنی است- اثبات آن ساده است و در واقع از طریق تعمیم قضیه ی چند گونای اویلر بدست می آید. چنبره را می توان طوری تغییر شکل داد که تبدیل به یک کره ی دسته دار شود یعنی چیزی شبیه به یک قوری بدون لوله و در!
::{picture=img/daneshnameh_up/2/2e/mco0075c.jpg}::
آنچه که از قضیه ی مشخصه های اویلر برای رویه های دو بعدی بدست می آید این است که هیچ دو رویه ای که از چسباندن {TEX()} {n} {TEX} دسته به کره و دیگری از چسباندن {TEX()} {m} {TEX} دسته به کره حاصل می شوند،‌در صورت مساوی نبودن {TEX()} {m,n} {TEX} ، قابل تبدیل به هم نیستند. به تعداد دسته های یک روی،‌ گونای {TEX()} {(genus)} {TEX} رویه گویند. گونای رویه ی {TEX()} {F} {TEX} را با {TEX()} {g(F)} {TEX} نشان می دهند.
::{picture=img/daneshnameh_up/3/3f/mco0075d.jpg}::
رویه هایی که در شکل فوق مشاهده می کنید،‌ در واقع هر 3 خاصیت زیر را دارا هستند:
1.همه آنها کراندارند – یعنی داخل یک کره ی به اندازه کافی بزرگ جا می شوند.
2.همه آنها از دو طرف تشکیل شده اند – یکی درون و یکی بیرون مثلاً‌یک مورچه بدون پاره کردن کره و یا هر یک از رویه های فوق،‌ نمی تواند از ان خارج شود.
3.همه آنها سالم هستند. یعنی پارگی و یا سوراخی که موجب پنچر شدن آنها شود ندارند! رویه‌ای که دارای 3 شرط فوق باشد را یک رویه ی فشرده ی جهت پذیر می نامیم.
هرگاه بتوان دو رویه را طوری با کشیدن یا فشردن به هم تبدیل کرد که سوراخ یا پاره نشوند. گویند این دو رویه با هم،‌ همسان ریخت اند. ( برای درک بهتر می توانید فرض کنید که رویه ها از جنیس لاستیک نرم،‌نازک و بسیار مرغوب تهیه شده اند! ). در واقع آنچه که قضیه ی اویلر به ما می گوید عبارت است از :
•دو رویه ی فشرده ی جهت پذیر همسان ریخت اند، اگر و تنها اگر گونای آن دو با هم مساوی باشد.
تعریف. گراف {TEX()} {G} {TEX} را در نظر بگیرید. اگر{TEX()} {G} {TEX} را بتوان روی سطحی با گونای {TEX()} {n} {TEX} رسم کرد به گونه ای که هیچ دو یالی همدیگر را قطع نکنند،‌{TEX()} {G} {TEX} را از گونای {TEX()} {n} {TEX} می نامیم در صورتی که گراف{TEX()} {G} {TEX} را نتوان روی سطحی با گونای {TEX()} {n-1} {TEX} رسم کرد به طوری هیچ دو یالی هم دیگر را قطع نکنند.
اگر گراف {TEX()} {G} {TEX} از گونای{TEX()} {n} {TEX} باشد،‌ آنگاه می نویسیم: {TEX()} {g(G)=n} {TEX}.
به طور مثال گراف های مسطح همگی از گونای صفر هستند.
---
!قضیه
@@ {TEX()} {g(G) \le C_r(G)} {TEX}@@
برای اثبات کافی است ثابت کنیم که اگر گراف{TEX()} {G} {TEX} روی کره رسم شده باشد، می توان به ازای هر تقاطع، با اضافه کردن یک دسته به کره،‌ گراف را دوباره طوری رسم کرد که تقاطع از بین برود. این امر در شکل زیر مشخص شده است:
::{picture=img/daneshnameh_up/5/52/mco0075e.jpg}::
در واقع با اضافه کردن دسته،‌ می توان یک یال مرتبط،‌ تقاطع را از زیر دسته و دیگری را از روی دسته عبور داد . دقت کنید که دسته ی اضافه شده در اینجا حکم پل را برای ما دارد.
از قضیه ی قبل به راحتی می توان دید که
@@{TEX()} {g(K_{3,3})=g(K_5)=1} {TEX}@@
---
!قضیه
{TEX()} {G} {TEX} را گرافی همبند و از گونای {TEX()} {n} {TEX} در نظر گیرید. اگر {TEX()} {G} {TEX} دارای {TEX()} {v} {TEX} راس،‌ {TEX()} {E} {TEX}یال و{TEX()} {F} {TEX} وجه باشد آنگاه:
@@{TEX()} {V-E+F=2-2n} {TEX}@@
این قضیه همانا تعمیم قضیه ی چند وجهی اویلر است چرا که اگر گراف مسطح باشد در نتیجه گراف از گونای صفر خواهد بود و تساوی برقرار است:
@@{TEX()} {V-E+F=2-2(0)=2} {TEX}@@
__اثبات__
فرض کنید {TEX()} {G} {TEX} را روی سطحی با گونای {TEX()} {n} {TEX} رسم کرده اید. انتهای هر دسته مثلاً‌ به شکل زیر می باشد:
::{picture=img/daneshnameh_up/3/36/mco0075f.jpg}::
یک طرف دسته ی مذکور را آنقدر می کشیم که محل برخورد دسته با کره مدار{TEX()} {M} {TEX} شود:
::{picture=img/daneshnameh_up/8/8c/mco0075g.jpg}::
دسته ی فوق را از روی{TEX()} {M} {TEX} برش می دهیم.
می دانیم برای کره، قضیه برقرار است. حال باید ببینیم با اضافه کردن دسته به کره چه اتفاقی می افتد. اگر دسته را به صورتی که محل تقاطع آن با کره یک وجه را کاملاً‌ بپوشاند، یعنی روی یک مدار منطبق شود،‌ می بینیم که تفاوت وجه های گراف از گرافی که روی کره است دو تا کمتر است که آن در همان محل برخورد دسته به کره است – پس به ازای اضافه کردن یک گونا به سطح، از تعداد وجه ها 2 تا کم می شود ولی تعداد یالها و راسها ثابت می ماند. پس برای سطحی که {TEX()} {n} {TEX} دسته دارد داریم:
@@{TEX()} {V-E+F+2n=2} {TEX}@@
@@{TEX()} {V-E+F=2-2n} {TEX}@@
و اثبات کامل می شود.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0121.pdf]

#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:39 ]   2   زینب معزی      جاری 
 چهارشنبه 22 شهریور 1385 [11:53 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..