مسیر در گراف ساده

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

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

در گراف G=(V,E) یک مسیر از راس v1 به راس vp دنباله‌ای از راس‌های متمایز گراف G به‌صورت زیر است:

v1...vivj...vp

به‌طوری که هر دو راس متوالی vivj در گراف G مجاورند و هیچ راس تکراری یافت نمی‌شود. 

طول مسیر 

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

تمرین

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

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

مسیرهای به طول 3,2,1 را نشان دهید.

S1 مسیری از u به v با طول 1 است:

S1:u,v    ;    m+1=2m=1


لازم به توضیح است که m+1 تعداد رئوس مسیر 1 است و m طول مسیر می‌باشد.


S2 مسیری از v به z با طول 2 است: 

S2:v,t,z    ;    m+1=3m=2


S3 مسیری از u به t با طول 3 است: 

S3:u,w,z,t    ;    m+1=4m=3

تمرین

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

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

طول مسیر a به d چقدر است؟

S:a,f,b,c,e,d    ;    m+1=6m=5

طول مسیر b به e چقدر است؟

S:b,c,a,f,e    ;    m+1=5m=4

نکته

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

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

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

دریافت مثال

مسیر و رابطه هم‌ارزی

فرض کنید گراف G=(V,E) داده شده است، می‌خواهیم نشان دهیم رابطه زیر یک رابطه هم‌ارزی بر مجموعه VG است:

وجود یک مسیر از u  و v به‌طوری‌که u,  vVG یک رابطه هم‌ارزی بر مجموعه VG است.

رابطه ریاضی مفهوم فوق به‌صورت زیر است:

وجود یک مسیر از u به vu,vV(G)  ,  uRv      

بررسی خاصیت بازتابی R:

چون مسیر متشکل از یک راس، مسیر به طول صفر می‌باشد، پس رابطه مذکور خاصیت بازتابی دارد، یعنی یک مسیر به طول صفر از u به u وجود دارد لذا رابطه فوق خاصیت بازتابی دارد.

بررسی خاصیت تقارنی R:

در گراف‌های مورد بحث چون جهت مطرح نیست، پس اگر از u به v یک مسیر وجود داشته باشد از v به u هم یک مسیر وجود دارد، چرا که حداقل می‌توان گفت مسیر برگشت پذیر است لذا رابطه فوق خاصیت تقارنی دارد.

بررسی خاصیت متعدی R:  

اگر در گراف مذکور از u به v یک مسیر و از v به w یک مسیر وجود داشته باشد و داشته باشیم:

u,v,wV(G)

با فرض عدم اشتراک دو مسیر موجود، در سایر راس‌های گراف، می‌توان گفت حداقل در راس v با یک‌دیگر مشترک هستند، لذا یک مسیر از u به w وجود دارد، پس این رابطه خاصیت متعدی دارد. 

بنابراین رابطه وجود یک مسیر بین دو راس، یک رابطه هم‌ارزی است.

نکته

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

2- فرض کنید u و v راس‌های گراف G باشند.  

فاصله بین u و v که به‌صورت du,v نوشته می‌شود را تعریف می‌کنیم:  

اگر u=v باشد، آن‌گاه du,v=0 در غیر این‌صورت du,v طول کوتاه‌ترین مسیر بین u و v است.   

اگر بین u و v مسیری وجود نداشته باشد، آن‌گاه du,v تعریف نشده است.   


3- در مسیر α=v0,v1,...,vp داریم: 

مسیر α ساده است، اگر تمام راس‌های آن متمایز باشد. 

مسیر α گذر است، اگر تمام یال‌های آن متمایز باشد. 

مسیر α بسته است اگر v0=vp یعنی در مسیر α مبدا و انتهای یکی باشد.  

مسیر α دور است، اگر بسته باشد و تمام راس‌های آن به‌جز v0=vp متمایز باشند.  

توجه کنید که در یک گراف بین مسیرهای ساده، گذرها و مسیرهای بسته و دور‌ها رابطه شمولی به قرار زیر وجود دارد:

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


4- قدم Walk

اگر x و y دو راس در گراف G=(V,E) باشند، یک دنباله تناوبی محدود به‌صورت زیر از راس‌ها و یال‌ها که با شروع از x و پایان با y و طی کردن n یال صورت می‌گیرد، یک قدم از x به y می‌باشد. 

x=x1e1  x2e2x3e3...en1xn1enxn=yei=xi1,xi    ;    1in

طول یک قدم همان n یال طی شده است.

دریافت مثال

قضیه

یک مسیر از راس u به راس v وجود دارد، اگر و فقط اگر از u به v یک مسیر ساده وجود داشته باشد. 

مسیری را ساده می‌گویند، اگر تمام راس‌های آن متمایز باشد.

اثبات

از آنجا که هر مسیر ساده، یک مسیر است، از این رو تنها لازم است ثابت کنیم اگر مسیری مانند α از u به v وجود داشته باشد، آن‌گاه یک مسیر ساده از u به v وجود دارد. 

اثبات را با استفاده از استقرای ریاضی روی طول n از α انجام می‌دهیم.    

فرض کنید n=1 یعنی α=(u,v) باشد، آن‌گاه α یک مسیر ساده از u به v است.  

فرض کنید n>1 به‌صورت زیر باشد:

α=u=v0,v1,...,vn1,v=vn

اگر هیچ راسی تکرار نشده باشد، آن‌گاه α یک مسیر ساده از u به v است، فرض کنید یک راس مثلا vi=vj تکراری باشد که در آن i<j است، آن‌گاه: 

β=v0,v1,...,vi,vj+1,...,vn

یک مسیر از u=v0 به v=vn به طول کوچک‌تر از n است، بنا به استقرا، یک مسیر از u به v وجود دارد.  

تعریف گراف متصل 

اگر G=(V,E) یک گراف باشد در صورتی‌که یک مسیر بین هردو راس جدا از هم در گراف وجود داشته باشد آن را گراف متصل گویند.

اگر یک گراف متصل نباشد، می‌توان مجموع راس‌های گراف را به زیر مجموعه‌هایی پارتیشن نمود که هر یک معرف یک گراف متصل باشند، به هر یک از این زیرمجموعه‌ها یک مولفه از گراف اولیه گویند و برای گراف G=(V,E) تعداد مولفه‌های گراف G را با KG نمایش می‌دهند.

به‌عنوان نمونه، گراف زیر را در نظر بگیرید:

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

گراف فوق، متصل نمی‌باشد و دارای دو مولفه V1=a,b,c,dV2=e,f می‌باشد از این رو دو مولفه داریم (دو زیر مجموعه متصل) پس:

KG=2

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

مسیر در گراف ساده

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

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