تعاریف و ویژگی‌های گراف-2

تعاریف

بزرگ ترین و کوچک ترین درجه یک گراف: بزرگترین عدد در بین درجات رئوس گراف \(G\) را با \(∆(G)\) و کوچکترین آن‌ها را با \(\delta(G)\) نمایش می‌دهیم و به ترتیب آن‌ها را ماکزیمم و مینیمم درجه گراف می‌نامیم.

زیر گراف: گرافیست که مجموعه رئوس و یال‌های آن زیر مجموعه ای از مجموعه رئوس و سال‌های گراف اصلی باشد.

مکمل گراف: مکمل گراف \(G\) که آن را با  \(\bar{G}\) یا \(G^c\) نمایش می‌دهیم گرافی است که مجموعه رئوس آن همان مجموعه رئوس گراف \(G\) است و بین دو رأس یک یال است اگر و تنها اگر بین همان دو رأس در \(G\) یالی وجود نداشته باشد.

نکات

حد‌‍اکثر درجه یک رأس در یک گراف \(n\) رأسی برابر \(n-1\) است.

\[d_{G}(v)+d_{\bar{G}}(v)=n-1\]

حد‌اکثر تعداد یال در یک گراف \(n\) رأسی برابر \(\binom{n}{2}\) است.

\[q(G)+q({\bar{G}})=\binom{n}{2}\]