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