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