شاه کلید نکات
شاه کلید سوال
مسئله 1: اگر G یک گراف با n رأس و v یک رأس آن باشد و \({d_G}\left( v \right)\) و \({d_{\overline G }}\left( v \right)\) به ترتیب درجه رأس v در گراف های G و \(\overline G \) باشند، مقدار \({d_G}\left( v \right) + {d_{\overline G }}\left( v \right)\) را به دست آورید.
این مجموع برابر است با تعداد یال هایی که امکان رسم آن ها از یک رأس در گراف ساده وجود دارد. از طرفی در یک گراف ساده ی n رأسی، حداکثر n-1 یال از یک رأس آن می گذرد؛
\({d_G}(v) + {d_{\overline G }}(v) = n - 1\)
مسئله 2: یک گراف n رأسی حداکثر چند یال می تواند داشته باشد؟
برابر است با تعداد پاره خط هایی که با وجود n نقطه غیر واقع در خط راست می توان رسم کرد؛ یعنی:
\(\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right) = \frac{{n(n - 1)}}{2}\)
مسئله 3: اگر G یک گراف n رأسی باشد، مقدار\(q\left( G \right) + q\left( {\overline G } \right)\) را به دست آورید.
این مجموع برابر است با حداکثر تعداد یال های ممکن در یک گراف ساده n رأسی، که بنا به مسئله قبل\(\frac{{n(n - 1)}}{2}\) خواهد بود.
1736019749.png)
