گراف کامل ساده (Simple Complete Graph)، در ریاضیات (Mathematics)
انواع گراف کامل (Complete Graph) را در آموزش زیر شرح دادیم :
گراف کامل ساده (Simple Complete Graph) :
این نوع، رایج ترین و پایه ترین نوع گراف کامل است. یک گراف کامل ساده، گرافی بدون جهت (Undirected) است که در آن هر جفت از رئوس (Vertices) مجزا، دقیقا با یک یال (Edge) به هم متصل شده اند. به بیان دیگر، درجه (Degree) هر رأس، یعنی تعداد یال های متصل به آن، برابر است با تعداد کل رئوس منهای یک. این گراف ها با نماد
\[ K_n \]نشان داده می شوند که در آن
\[ n \]تعداد رئوس گراف است. برای مثال،
\[ K_3 \]یک مثلث،
\[ K_4 \]یک چهارضلعی کامل با تمام قطرهایش، و
\[ K_5 \]یک پنج ضلعی کامل است که به دلیل تقاطع یال ها در فضای دو بعدی، به صورت غیرمسطح (Non-planar) ترسیم می شود.
خواص این گراف ها بسیار منظم و متقارن است. تعداد یال ها در یک گراف کامل ساده با استفاده از فرمول ترکیبات (Combinations) به دست می آید، زیرا ما به دنبال تعداد راه های انتخاب ۲ رأس از بین
\[ n \]رأس هستیم. این فرمول به صورت زیر است:
\[ |E| = \binom{n}{2} = \frac{n(n-1)}{2} \]گراف های کامل ساده نقش مهمی در قضایای گراف، مانند قضیه توران (Turán's Theorem) دارند که به یافتن بیشترین تعداد یال در یک گراف بدون زیرگراف کامل مشخص می پردازد. همچنین، این گراف ها به عنوان مثالی از گراف های منظم (Regular Graphs) شناخته می شوند، زیرا همه رئوس دارای درجه یکسانی هستند.
