شاه کلید نکات
شاه کلید سوال
![[شاه کلید مای درس] | مسیر در گراف](https://dl.my-dars.com/upload/image/03 (8)1728766181.jpg)
فرض کنیم u و v دو راس از گراف G باشند. یک مسیر از u به v در G دنباله ای متشکل از راس های دو به دو متمایز است که از u شروع و به v ختم می شود به طوری که هر دو راس متوالی در این مسیر، مجاور هستند. طول مسیر همان تعداد یال های طی شده است که یکی کمتر از تعداد راس ها است.
هر راس به تنهایی، یک مسیر به طول صفر از خودش به خودش است.
گرافی که تنها از یک مسیر n راسی تشکیل شده باشد با \({P_n}\) نمایش می دهیم.
گراف G را همبند گوییم، هر گاه بین هر دو راس آن حداقل یک مسیر وجود داشته باشد، مانند گراف زیر:
گرافی که همبند نباشد را ناهمبند می نامیم. مانند گراف های زیر:
1 اگر \(q\langle p - 1\) باشد، گراف قطعا نا همبند است.
2 اگر \(q\rangle (\frac{{p - 1}}{2})\) باشد، گراف قطعا همبند است. همچنین اگر در گرافی \(\Delta = p - 1\) باشد (یعنی یک راس به همه وصل باشد) گراف قطعا همبند است.
یک دور به طول m در گراف G دنباله ای از \(m + 1\) راس، که راس های متوالی مجاور بوده و m راس اول آن دو به دو متمایز بوده و راس آخر همان راس اول باشد. در شکل زیر دور \({v_1}{v_2}{v_3}{v_4}{v_1}\) را ببینید. این دور به طول 4 است.
1 حداقل طول دور می تواند 3 باشد.
2 طول دور همان تعداد یال های طی شده است.
گرافی را که تنها از یک دور n راسی تشکیل شده باشد با \({C_n}\) نمایش می دهیم.
برای مثال \({C_5}\) را در شکل زیر می بینید:
تمرین
1 با توجه به گراف زیر یک مجموعه ی احاطه گر مینیمال بنویسید که مینیمم نباشد.
مجموعه ی \(\{ a,b,c,d,e\} \) احاطه گر مینیمال است ولی مینیمم نیست، مجموعه ی احاطه گر مینیمم این گراف \(\{ c,l,f\} \) می باشد.
2 درستی یا نادرستی گزاره های زیر را برسی کنید.
الف) مجموعه ی احاطه گر هر گراف، مساوی مجموعه ی احاطه گر مینیمم آن است.
نادرست
ب) مجموعه احاطه گر مینیمم هر دو گراف زیر یک مجموعه ی دو عضوی است.
درست
تهیه کننده: جابر عامری و الماسی کیا
