تاریخچه ی:
گرافهای یکریخت
||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__||
^@#16:
!گراف های یکریخت
هرگراف {TEX()} {G} {TEX} به طور یکتا با {TEX()} {E(G),V(G)} {TEX} آن مشخص می شود یعنی اگر دو گراف {TEX()} {G_2,G_1} {TEX} مجموعه رئوس و یالهای یکسانی داشته باشند،نمودار یکسان نیز خواهند داشت و اساساً {TEX()} {G_1=G_2} {TEX} خواهد بود.
اما فراتر از این، گراف هایی هستند که همانند نیستند ولیکن نمودارهای یکسان دارند مانند:
::{picture=img/daneshnameh_up/8/8e/mco0049a.jpg}::
چنین گراف هایی را یکریخت می نامیم.
از آنجا که در مقدمه شهود این مفهوم داده شده است مستقیماً به سراغ تعریف و کاربرد می رویم:
دو گراف{TEX()} {G} {TEX} و {TEX()} {H} {TEX} را یکریخت گوییم اگر توابع دو طرفه
@@{TEX()} {\varphi : E(G) \rightarrow E(H) } {TEX}@@
@@{TEX()} {\theta : V(G) \rightarrow V(H)} {TEX}@@
موجود باشند به طوری که در {TEX()} {G} {TEX} ، {TEX()} {u} {TEX} به{TEX()} {v} {TEX} متصل باشد اگر و تنها اگر{TEX()} {\theta (u)} {TEX} تحت تبدیل بالا به {TEX()} {\theta (v)} {TEX} متصل باشد.
به عبارت دیگر تبدیلی دو طرفه برای رئوس{TEX()} {G} {TEX}و یالهای متناظر آنها موجود باشد که {TEX()} {G} {TEX} را به{TEX()} {H} {TEX} تبدیل کند که در مثال قبل تبدیل زیر{TEX()} {G} {TEX} را به {TEX()} {H} {TEX} تبدیل می کند:
@@{TEX()} {\theta (v)=v_1 \ , \ \theta (w)=v_2 \ , \ \theta (u)=v_3} {TEX}@@
@@{TEX()} {\varphi (e_1)=a \ , \ \varphi (e_2)=b \ , \ \varphi (e_3)=c} {TEX}@@
توصیه می گردد حتماً شهود یکریختی را که در " مقدمه " بحث شده بود را مطالعه کرده باشید.
بدین ترتیب مجموعه کل گراف های موجود در دنیا! به دسته های یکریختی افراز می گردد یعنی برای هر گراف دلخواه دسته هم ارزی ای وجود دارد که تمام گراف های آن با گراف دلخواه هم ارزند!
از این به بعد ما غالباً یکریختی را به مفهوم برابری و یکسانی می گیریم زیرا دو گراف یکریخت تنها در نام و نحوه رسم متفاوت می باشند و خصوصیات یکسان خواهند داشت.
---
!!تمرین
آیا ممکن است {TEX()} {H,G} {TEX} متعلق به یک دسته یک ریختی باشند ولی دنباله درجه های آنها متفاوت باشد؟
__جواب__
به وضوح خیر. زیرا در این صورت هیچ تبدیلی نمی تواند آنها را به هم تبدیل کند.
---
!!نتیجه
پس اولین شرط لازم و نه کافی برای یکریخت بودن، داشتن درجه های رئوس یکسان می باشد.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0066.pdf]
#@^