منو
 کاربر Online
470 کاربر online
تاریخچه ی: گرافهای منظم

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!گراف منتظم
هر گاه درجه ی هر راس گراف {TEX()} {G} {TEX} برابر {TEX()} {r} {TEX} باشد،‌{TEX()} {G} {TEX} را یک گراف {TEX()} {-r} {TEX}منتظم گوییم. یا ((گراف)) منتظم از درجه{TEX()} {r} {TEX}. تعداد یالهای یک گراف {TEX()} {-r} {TEX}منتظم {TEX()} {n} {TEX} راسی برابر است با {TEX()} {\frac{nr}{2}} {TEX}.
---
!!مثال
هر گراف تهی یک گراف 0- منتظم و هر گراف {TEX()} {n} {TEX}راسی کامل یک گراف {TEX()} {-n-1} {TEX}منتظم است.
گراف زیر یک گراف 3 -منتظم است:
::{picture=img/daneshnameh_up/3/3f/mco0083a.jpg}::
هرگراف دوری یک گراف 2- منتظم است:
::{picture=img/daneshnameh_up/7/78/mco0083b.jpg}::
---
!قضیه
در هیچ گراف{TEX()} {-r} {TEX}منتظمی که {TEX()} {r} {TEX}زوج است پل وجود ندارد.
به خاطر آورید که در یک گراف همبند پل یالی است که با حذف آن گراف ناهمبند می شود.
__اثبات__
فرض کنید چنین نباشد – پس {TEX()} {G} {TEX} یک گراف منتظم از درجه ی{TEX()} {2h} {TEX} است و{TEX()} {G} {TEX} دارای پل می باشد – با حذف این پل،‌ گراف {TEX()} {G} {TEX} به دو ((گراف همبند)) نامجاور تبدیل می شود. که هر کدام از این دو دقیقاً‌ دارای یک راس فرد می باشد که امکان پذیر نیست.
---
!!مثال
ثابت کنید هر گراف فرد منتظم ( یعنی گراف {TEX()} {2(k)+1} {TEX}منتظم {TEX()} {k\in Z} {TEX}) تعداد زوجی راس دارد.
__اثبات__
به سادگی از آنجا که مجموع کل درجات باید زوج باشد به برهان خلف اگر تعداد رئوس فرد باشد چون درجه هر کدام هم فرد است مجموع آنها فرد می شود نه زوج.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0072.pdf]
---
!همچنین ببینید
*((گراف پترسن ))
*((گراف ستاره))
#@^

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