شاه کلید نکات
شاه کلید سوال
![[شاه کلید مای درس] | انواع گراف](https://dl.my-dars.com/upload/image/02 (9)1728766141.jpg)
گرافی که درجه ی همه راس های آن r باشد، گراف r-منظم (از مرتبه p) نامیده می شود. برای نمونه گراف های زیر 2-منتظم و 3-منتظم هستند:
گفتیم هر گراف، مجموع درجه ها برابر 
می شود. حال در گراف r-منتظم p راسی داریم:
مجموع درجه ها = \(r + r + ... + r = 2q \Rightarrow pr = 2q\)
یعنی در گراف های منتظم ضرب مرتبه در درجه راس ها، دو برابر تعداد یال ها می شود.
یعنی pr همواره عددی زوج است؛ پس p و r نمی توانند هر دو فرد باشد (یعنی گراف فرد-منتظم از مرتبه فرد نداریم).
مثال
1 یک گراف 2-منتظم 5 راسی رسم کنید که دارای بیش از یک مجموعه ی احاطه گر مینیمم با اندازه 2 باشد. حداقل دو تا از مجموعه های احاطه گر مینیمم آن را بنویسید.
مجموعه های احاطه گر مینیمم، مجموعه های زیر می باشند.
\(\{ a,c\} ,\{ a,d\} \)
2 یک گراف 8 راسی با عدد احاطه گری 2 رسم کنید که دارای فقط یک مجموعه ی احاطه گر باشد.
در گراف زیر تنها مجموعه ی \(\{ c,g\} \) احاطه گر مینیمم می باشد.
گرافی از مرتبه ی p که هر دو راس آن مجاور باشند را گراف کامل نامیده و با \({K_p}\) نشان می دهیم.
در واقع گراف های کامل حداکثر تعداد یال ها را در مرتبه ی خود دارند و دیگر نمی توانیم به آن ها یال اضافه کنیم.
در جدول زیر گراف های کامل تا مرتبه 5 را مشاهده کنید:
1 درجه ی هر راس در گراف کامل p راسی \(p - 1\) است. یعنی گراف کامل \({K_p}\)، یک گراف \(p - 1\) منتظم است.
2 تعداد یال ها در گراف کامل p راسی برابر است با:
مجموع درجه ها = \((p - 1) + (p - 1) + ... + (p - 1) = 2q \Rightarrow q = \frac{{p(p - 1)}}{2}\)
مکمل گراف G که آن را با \({G^c}\) یا \(\bar G\) نشان می دهیم، گرافی است که مجموعه راس های آن همان مجموعه ی راس ها است و دو راس در \(\bar G\) مجاورند اگر در G مجاور نباشند. برای مثال در شکل زیر یک گراف کامل و مکمل آن را می بینید:
اگر تعداد یال های G و \(\bar G\) را با هم جمع کنیم، برابر تعداد یال های گراف کامل می شود؛ یعنی:
\(q(G) + q(\bar G) = \frac{{p(p - 1)}}{2}\)
مکمل گرافی r-منتظم گرافی \(\bar r\)-منتظم بوده و \(r + \bar r = p - 1\)
گراف H را یک زیر گراف از G می گوییم هر گاه \(E(H) \subseteq E(G),V(H) \subseteq V(G)\)
برای مثال گراف G و سه زیر گراف آن را در زیر مشاهده می کنید:
تهیه کننده: جابر عامری و الماسی کیا
