تعاریف و مفاهیم: گراف کامل

در نظریه گراف، یک گراف کامل، یک گراف ساده و بدون جهت است که هر بین هر دو راس آن دقیقاً یک یال وجود داشته باشد.

یک گراف کامل از مرتبه n، که با Kn نشان داده می شود، دارای n راس و n(n − 1)/2 یال است. یک گراف کامل یک گراف منتظم از درجه n-1 است. در شکل بالا، گراف های کامل از مرتبه یک تا مرتبه 12 نمایش داده شده است.

نکته ها:

-- از تعریف این نوع گراف معلوم است که گراف کامل از مرتبه اول، هیچ یالی ندارد.

-- نام گذاری: حرف K در Kn ابتدای واژه آلمانی komplett (کامل) می باشد. البته برخی معتقدند از آنجایی که گراف کامل در زبان آلمانی معادل Vollständiger Graph می باشد، نماد K از نام دانشمند لهستانی، کازیمیر کوراتوسکی (Kazimierz Kuratowski) که در زمینه گرافها فعالیت های زیادی داشته، گرفته شده است.

-- تعداد یالهای گرافهای کامل، اعداد مثلثی هستند:

0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, ...