دور در گراف ساده

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

تعریف دور در گراف ساده

اگر ابتدا و انتهای یک مسیر یکسان باشد، دور Cycle نامیده می‌شود، به‌عبارت دیگر یک دور از گراف G دنباله‌ای مانند زیر است:

v1v2...vmvm+1v1    ;    m3

که متشکل از m+1 راس است.

طول یک دور

دنباله v1v2...vmvm+1 متمایزند و عدد m طول این دور از گراف ساده G نامیده می‌شود. 

در واقع دوری که متشکل از m+1 راس با شرط mN باشد، دوری با طول m نامیده می‌شود.

توجه کنید که طول یک دور در گراف ساده G برابر تعداد یال‌های آن است.

برای یافتن تعداد دورهای به طول m در گراف ساده از فرمول زیر می‌توان استفاده کرد.

pm×(m1)!2

p تعداد راس‌های گراف ساده است.

به‌عنوان نمونه در گراف شکل زیر:

دور در گراف ساده - پیمان گردلو

دنباله xuvx یک دور به طول سه است.

در گراف زیر uvwuywuzyxwvuzyx دورهایی به‌ترتیب با طول 6,4,3 هستند.

دور در گراف ساده - پیمان گردلو

نکته

1- گرافی را که تنها از یک دورِ n راسی تشکیل شده باشد را با Cn نمایش می‌دهیم.

در گراف زیر C5 را مشاهده می‌کنید:

دور در گراف ساده - پیمان گردلو

دریافت مثال

نکته

2- طول یک دور در گراف ساده G حداقل برابر سه می‌باشد.

3- در یک گراف، اگر دوری به طول m وجود داشته باشد، حتما مسیری به طول m-1 موجود است.

4- اگر راس‌های w و u بخشی از یک دور در گراف ساده G باشند و یک یال از این دور حذف شود، آن‌گاه هم‌چنان یک مسیر از w به u در G وجود دارد.    

5- قدم، مدار، دور

قدم باز: در قدم x-y اگر n>1 و xy باشد، می‌گوییم قدم باز است.

قدم بسته: در قدم x-y اگر n>1 و x=y باشد، می‌گوییم قدم بسته است.

مدار: اگر یک گذرگاه x-y بسته باشد، آن‌را مدار گویند. 

دور: به مسیری که بسته باشد، دور گویند.

تمرین

گراف زیر را در نظر بگیرید:

دور در گراف ساده - پیمان گردلو

در دنباله‌های زیر، قدم، مدار، دور را مشخص کنید. 

bcdecf

دنباله فوق یک قدم باز از b به f است که دارای طول 5 است و تنها راس c تکرار شده است ولی هیچ یالی تکراری نشده است.

fceda

دنباله فوق یک قدم باز از f به a می‌باشد، که نه یالی و نه راسی تکرار شده است و طول آن برابر چهاراست.

abdceab

دنباله فوق یک قدم باز از a به b می‌باشد که دارای طول شش است، دراین دنباله راس b تکرار شده است. 

bcdb

دنباله فوق یک قدم بسته از b به b می‌باشد.

abdceda

دنباله فوق یک مدار از a به a می‌باشد و به‌دلیل تکرار d یک دور نیست. 

نکته

6- در گراف G=(V,E) اگر راس‌های x,yV در قسمتی از یک مدار گراف G باشند و یک یال از مدار حذف شود، هنوز یک مسیر از x به y وجود دارد.  

7- اگر گراف G=(V,E) متصل و شامل یک مدار باشد، آن‌گاه یک یال از مدار می‌تواند حذف شود و گراف، متصل باقی بماند.

یادآوری

به‌طور کلی می‌توان جدول زیر را داشت:

دور در گراف ساده - پیمان گردلو

دریافت مثال

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

دور در گراف ساده

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

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