منو
 کاربر Online
803 کاربر online

گرافهای چندبخشی

چاپ
علوم ریاضی > علو م رایانه



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


گراف چند بخشی

فرض کنید مجموعه ی راس های یک گراف به زیر مجموعه افراز گردد. گراف چند بخشی است در صورتی که در دو راس وقتی می توانند به هم به وسیله یال وصل شوند که دو راس عضو دو مجموعه ی باشند به قسمی که .
مثلاً‌ گراف زیر گراف های 3بخشی و 4 بخشی را نشان می دهند :
img/daneshnameh_up/1/1d/mco0068a.jpg

img/daneshnameh_up/8/89/mco0068b.jpg

گراف بخشی را کامل گویند هر گاه همه ی یالهای ممکن بین راس های آن کشیده شده باشد. اگر یک گراف بخشی کامل باشد.
به قسمی که به مجموعه ی افراز شده باشد که به ازای هر ، ‌هیچ دو راسی از به هم متصل نباشند، و نیز
آنگاه گراف را با نماد روبرو نمایش می دهیم:

مثال

گراف های زیر نمونه هایی از گراف های چند بخشی کامل هستند.
img/daneshnameh_up/d/d6/mco0068c.jpg

img/daneshnameh_up/2/26/mco0068d.jpg

img/daneshnameh_up/4/49/mco0068e.jpg

تعداد یالهای یک گرافبرابر است با
برخلاف گراف های در بخشی کامل، گرافهای چند بخشی کامل همیشه منتظم نیستند. مگر گرافهای کامل دو بخشی به صورت به قسمی که در این صورت درجه هر راس از این گراف برابر است با چرا که مجموعه ی راس هایimg/daneshnameh_up/c/c5/mco0068f.jpg ، به زیر مجموعه ی مساوی هر کدام با عضو افراز می شود و از هر راس از یکی از این زیر مجموعه ها به سایر زیر مجموعه ها یال رسم می شود. از آنجا که هر زیر مجموعه شامل راس است،‌ از هر راس یال خارج می گردد.

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0077.pdf

همچنین ببینید






تعداد بازدید ها: 14156


ارسال توضیح جدید
الزامی
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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..