گراف کامل گراف سادهای است که در آن هر رأس به تمامی راسهای دیگر به وسیلهٔ یک یال متصل است. معمولاً گراف کاملِ راسی را با نمایش میدهند. آغاز نظریه گرافها معمولاً با کار اویلر بر روی هفت پلِ کونیکسبرگ در سال ۱۷۳۶ گره خورده است.[1] با این حال، تاریخچه گرافهای کامل به رسمهای رامون یوی در قرن سیزدهم بازمیگردد، که رئوس گراف را در گوشههای چندضلعی منتظم قرار میداد.[2][3] این رسمها با عنوان گل رز عرفانی نیز شناخته میشوند.[4]
خواص
- تعداد یالهای یک گراف کامل راسی است.[5]
- هر گراف کاملی گروهک بیشین خود است.[5]
- مکمل یک گراف کامل، گراف تهی است.[5]
- تعداد تطابقهای کامل یک گراف کامل راسی برابر است با . [6]
مثال
شکل پایین شامل گرافهای کامل که دارای یک تا هشت رأس هستند میباشد:
ماتریس مجاورت گراف کامل
تمامی درایههای گراف کامل ۱ هستند به جز درایههای روی قطر اصلی که صفر هستند چون گراف کامل طوقه وجود ندارد.
منابع
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.