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

نگارش: 1



این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت 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

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







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