تاریخچه ی:
گرافهای چندبخشی
||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__||
^@#16:
!گراف چند بخشی
فرض کنید مجموعه ی راس های یک گراف{TEX()} {G} {TEX} به {TEX()} {n} {TEX} زیر مجموعه {TEX()} {G_n,\cdots ,G_2,G_1} {TEX} افراز گردد. {TEX()} {G} {TEX}گراف چند بخشی است در صورتی که در {TEX()} {G} {TEX}دو راس وقتی می توانند به هم به وسیله یال وصل شوند که دو راس عضو دو مجموعه ی {TEX()} {G_j,G_i} {TEX} باشند به قسمی که {TEX()} {G_i \neq G_j} {TEX}.
مثلاً گراف زیر گراف های 3بخشی و 4 بخشی را نشان می دهند :
::{picture=img/daneshnameh_up/1/1d/mco0068a.jpg}::
::{picture=img/daneshnameh_up/8/89/mco0068b.jpg}::
گراف {TEX()} {n} {TEX} بخشی را کامل گویند هر گاه همه ی یالهای ممکن بین راس های آن کشیده شده باشد. اگر {TEX()} {G} {TEX} یک گراف {TEX()} {n} {TEX} بخشی کامل باشد.
به قسمی که {TEX()} {G} {TEX} به{TEX()} {n} {TEX} مجموعه ی{TEX()} {(1\le i \le n) G_i} {TEX} افراز شده باشد که به ازای هر {TEX()} {i} {TEX}، هیچ دو راسی از {TEX()} {G_i} {TEX} به هم متصل نباشند، و نیز {TEX()} {|G_i|={\alpha}_i} {TEX}
آنگاه گراف {TEX()} {G} {TEX} را با نماد روبرو نمایش می دهیم: {TEX()} {K_{\alpha}_1,{\alpha}_2,\cdots , {\alpha}_n}} {TEX}
---
!!مثال
گراف های زیر نمونه هایی از ((گراف)) های چند بخشی کامل هستند.
::{picture=img/daneshnameh_up/d/d6/mco0068c.jpg}::
::{picture=img/daneshnameh_up/2/26/mco0068d.jpg}::
::{picture=img/daneshnameh_up/4/49/mco0068e.jpg}::
تعداد یالهای یک گراف{TEX()} {K_{a_1,a_2,\cdots ,a_n}} {TEX}برابر است با {TEX()} {a_1\times a_2\times \cdots a_n} {TEX}
برخلاف گراف های در بخشی کامل، گرافهای چند بخشی کامل همیشه منتظم نیستند. مگر گرافهای کامل دو بخشی به صورت{TEX()} {K_{a_1,a_2,\cdots ,a_n}} {TEX} به قسمی که {TEX()} {-a_1=a_2=\cdots =a_n} {TEX} در این صورت درجه هر راس از این گراف برابر است با{TEX()} {-a_1 \times (n-1)} {TEX} چرا که مجموعه ی راس های{picture=img/daneshnameh_up/c/c5/mco0068f.jpg} ، به {TEX()} {n} {TEX} زیر مجموعه ی مساوی هر کدام با {TEX()} {a} {TEX} عضو افراز می شود و از هر راس از یکی از این زیر مجموعه ها به سایر زیر مجموعه ها یال رسم می شود. از آنجا که هر ((زیر مجموعه)) شامل {TEX()} {a} {TEX} راس است، از هر راس{TEX()} {a\times (n-1)} {TEX} یال خارج می گردد.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0077.pdf]
---
!همچنین ببینید
*(( گرافهای k - مکعب ))
*(( گرافهای پترسن ))
#@^