گراف کامل (Complete Graph)، در ریاضیات (Mathematics)
انواع گراف منتظم (Regular Graph) را در آموزش زیر شرح دادیم :
گراف کامل (Complete Graph) :
گراف کامل با نماد
\[ K_n \]شناخته می شود و حالتی خاص از گراف های منظم است. در این گراف، هر راس به تمام
\[ n-1 \]راس دیگر متصل است. بنابراین،
\[ K_n \]یک گراف
\[ (n-1) \]-منظم است.
تعداد یال ها در یک گراف کامل برابر است با:
\[ \frac{n(n-1)}{2} \]
گراف های کامل نقش مهمی در قضیه رمزی (Ramsey Theory) و به عنوان مثالی از گراف هایی با بیشترین تعداد یال ممکن برای یک گراف ساده با
\[ n \]راس دارند. آن ها حداکثر چگالی (Density) ممکن را دارا هستند و هر گراف دیگری با
\[ n \]راس، زیرگرافی از
\[ K_n \]محسوب می شود.
نویسنده علیرضا گلمکانی
شماره کلید 5551
گزینه ها 
نظرات 0 0 0