گراف کامل (Complete Graph)، در ریاضیات (Mathematics)
انواع گراف ساده (Simple Graph) را در آموزش زیر شرح دادیم :
گراف کامل (Complete Graph) :
گراف کامل گرافی است که در آن، بین هر دو رأس متمایز، دقیقا یک یال وجود دارد. به عبارت دیگر، تمام رأس های گراف دو به دو با یکدیگر در ارتباط هستند. اگر یک گراف کامل
\[ n \]رأس داشته باشد، آن را با نماد
\[ K_n \]نمایش می دهند. تعداد یال ها در این گراف برابر است با تعداد راه های انتخاب ۲ رأس از
\[ n \]رأس، که طبق فرمول ترکیبات (Combinations) محاسبه می شود. در این گراف، درجه هر رأس برابر
\[ n-1 \]است، زیرا هر رأس به تمام رأس های دیگر (به جز خودش) متصل است. به عنوان مثال، گراف کامل ۳ رأسی (
\[ K_3 \]) یک مثلث است، و گراف کامل ۴ رأسی (
\[ K_4 \]) یک چهارضلعی با تمام قطرهایش است. گراف های کامل در نظریه رمزی (Ramsey Theory) و به عنوان مثالی از چگال ترین (Dense) گراف های ممکن کاربرد فراوانی دارند. اگر به دنبال گرافی بگردیم که بیشترین تعداد یال ممکن را برای یک تعداد رأس مشخص داشته باشد، گراف کامل پاسخ ما است.
\[ K_n \quad \text{تعداد یال ها} = \binom{n}{2} = \frac{n(n-1)}{2} \]