گراف کامل

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

گراف کامل گراف ساده‌ای است که در آن هر رأس به تمامی راس‌های دیگر به وسیلهٔ یک یال متصل است. معمولاً گراف کاملِ راسی را با نمایش میدهند. آغاز نظریه گراف‌ها معمولاً با کار اویلر بر روی هفت پلِ کونیکسبرگ در سال ۱۷۳۶ گره خورده است.[۱] با این حال، تاریخچه گرافهای کامل به رسم‌های رامون یوی در قرن سیزدهم بازمی‌گردد، که رئوس گراف را در گوشه‌های چندضلعی منتظم قرار میداد.[۲][۳] این رسم‌ها با عنوان گل رز عرفانی نیز شناخته می‌شوند.[۴]

خواص[ویرایش]

  • تعداد یالهای یک گراف کامل راسی است.[۵]
  • هر گراف کاملی گروهک بیشین خود است.[۵]
  • مکمل یک گراف کامل، گراف تهی است.[۵]
  • تعداد تطابق‌های کامل یک گراف کامل راسی برابر است با . [۶]

مثال[ویرایش]

شکل پایین شامل گرافهای کامل که دارای یک تا هشت رأس هستند می‌باشد:

Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg

ماتریس مجاورت گراف کامل[ویرایش]

تمامی درایه‌های گراف کامل ۱ هستند به جز درایه‌های روی قطر اصلی که صفر هستند چون گراف کامل طوقه وجود ندارد.

منابع[ویرایش]

  1. Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
  2. Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 0191630624.
  3. Read, Ronald C.; Wilson, Robin J. (1998), An Atlas of Graphs, Clarendon Press, p. ii, ISBN 9780198532897.
  4. Mystic Rose, nrich.maths.org, retrieved 23 January 2012.
  5. ۵٫۰ ۵٫۱ ۵٫۲ Rosen, Kenneth (2018-07-09). Discrete Mathematics and Its Applications. ISBN 978-1259676512.
  6. Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.

Kenneth H, Rosen (1998). "Graphs". Discrete Mathematics and its Applications. SIGS Reference Library. William C Brown Pub; 4th edition. ISBN 0072899050. Retrieved 2007. Check date values in: |بازبینی= (help)