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

گرافهای منظم

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



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


گراف منتظم

هر گاه درجه ی هر راس گراف برابر باشد،‌ را یک گراف منتظم گوییم. یا گراف منتظم از درجه. تعداد یالهای یک گراف منتظم راسی برابر است با .

مثال

هر گراف تهی یک گراف 0- منتظم و هر گراف راسی کامل یک گراف منتظم است.
گراف زیر یک گراف 3 -منتظم است:
img/daneshnameh_up/3/3f/mco0083a.jpg

هرگراف دوری یک گراف 2- منتظم است:
img/daneshnameh_up/7/78/mco0083b.jpg


قضیه

در هیچ گرافمنتظمی که زوج است پل وجود ندارد.
به خاطر آورید که در یک گراف همبند پل یالی است که با حذف آن گراف ناهمبند می شود.
اثبات
فرض کنید چنین نباشد – پس یک گراف منتظم از درجه ی است و دارای پل می باشد – با حذف این پل،‌ گراف به دو گراف همبند نامجاور تبدیل می شود. که هر کدام از این دو دقیقاً‌ دارای یک راس فرد می باشد که امکان پذیر نیست.

مثال

ثابت کنید هر گراف فرد منتظم ( یعنی گراف منتظم ) تعداد زوجی راس دارد.
اثبات
به سادگی از آنجا که مجموع کل درجات باید زوج باشد به برهان خلف اگر تعداد رئوس فرد باشد چون درجه هر کدام هم فرد است مجموع آنها فرد می شود نه زوج.

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

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

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



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


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