گراف کامل مسطح (Complete Planar Graph)، در ریاضیات (Mathematics)

انواع گراف مسطح (Planar Graph) را در آموزش زیر شرح دادیم :

گراف کامل مسطح (Complete Planar Graph) :

این گراف ها به گراف هایی گفته می شود که در آنها هر دو رأس توسط یک یال به هم متصل هستند (گراف کامل) و در عین حال خاصیت مسطح بودن نیز حفظ می شود. تنها گراف های کامل مسطح، گراف های با تعداد رأس ۱، ۲، ۳ و ۴ هستند:

\[ K_1 \]

،

\[ K_2 \]

،

\[ K_3 \]

و

\[ K_4 \]

. همانطور که گفته شد،

\[ K_5 \]

مسطح نیست. دلیل آن این است که

\[ K_5 \]

دارای ۵ رأس و ۱۰ یال است و برای مسطح بودن باید شرط

\[ E \leq 3V - 6 \]

را ارضا کند که برای

\[ K_5 \]

، داریم

\[ 10 \leq 3 \times 5 - 6 = 9 \]

که نادرست است. بنابراین

\[ K_5 \]

یک گراف غیرمسطح (Non-planar Graph) است.

\[ 10 \nleq 9 \quad \Rightarrow \quad K_5 \text{ غیرمسطح} \]