گراف منتظم

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 04 شهریور 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 33 مرتبه

تعریف گراف (r - منتظم)

گراف ساده G از مرتبه p را (r - منتظم) می‌نامیم، هرگاه درجه هر راس G برابر r باشد یا گرافی را منتظم می‌گوییم که همه راس‌های آن درجه یکسانی داشته باشند و تعداد این درجه عدد r باشد.

به‌عنوان نمونه گراف ساده زیر، یک گراف (4 - منتظم) است، یا گراف منتظمی است که همه راس‌های آن درجه یکسان 4 را دارد:

گراف منتظم - پیمان گردلو

دریافت مثال

قضایای گراف منتظم

قضیه

تعداد یال‌های گراف (r - منتظم) که تعداد راس‌های آن برابر p باشد، از رابطه زیر به‌دست می‌آید:

q=12pr

r درجه هر راس گراف منتظم می‌باشد.

نکته

اولین نتیجه از قضیه فوق:

i=1pdeg(vi)=pr

i=1pdeg(vi)=2qi=1pdeg(vi)=pr

i=1pdeg(vi)=2qifq=12pr2q=pr


دومین نتیجه از قضیه فوق:

if   q=12pr2q=pr

این مطلب نشان می‌دهد که در هر گراف (r - منتظم)، pr باید عددی زوج باشد، به‌عبارت دیگر از بین r و p حداقل یکی باید عدد زوج باشد و ضمنا p>r می‌باشد.   

p×r=2q

زوج=زوج×زوج

زوج=فرد×زوج

زوج=زوج×فرد

دریافت مثال

نکته

1- گراف (r - منتظم) همان گراف منتظم است که همه راس‌های آن درجه یکسان r را دارد.   

2- در هر گراف ساده δ2qpΔ می‌باشد.

بدیهی است که در گراف (r - منتظم) چون همه راس‌ها از درجه r هستند، پس بزرگ‌ترین درجه  و کوچک‌ترین درجه δ با هم برابرند، یعنی:

δ=2qp=Δpr=2qr=2qp    δ=r=Δ

3- تعداد گراف‌های (r - منتظم) از مرتبه p برابر است با: 

 p            ;    p=2n            ,  r=0,1,...,p-1p+12     ;    p=2n1     ,  r=0,2,4,...,p-1

4- یک گراف (2 - منتظم) می‌تواند یک حلقه با n گره باشد. 

5- برای گراف (r - منتظم) که r عددی فرد است، از آنجا که مجموع درجات بایستی عددی زوج باشد، پس تعداد راس‌ها بایستی عددی زوج باشد تا در r ضرب گردد و مجموع درجات عددی زوج شود. 

بنابراین نمی‌توان با تعداد گره‌های فرد، گراف (r - منتظم) برای r فرد، طراحی کرد.    

6- در گراف (r - منتظم) همواره q<p22 و تعداد عناصر صفر در تمام سطرها و ستون‌های ماتریس مجاورت مساوی هستند. 

دریافت مثال

مثال‌ها و جواب‌ها

گراف منتظم

5,000تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید