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

||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 - مکعب ))
*(( گرافهای پترسن ))
#@^



تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:28 ]   2   زینب معزی      جاری 
 سه شنبه 21 شهریور 1385 [13:05 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..