گراف کامل

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

خواص

تعداد یالهای یک گراف کامل $n$ راسی ${\frac {n\times {\bigl (}n-1{\bigr )}}{2}}$ است.^[۵]
هر گراف کاملی گروهک بیشین خود است.^[۵]
مکمل یک گراف کامل، گراف تهی است.^[۵]
تعداد تطابق‌های کامل یک گراف کامل $n$ راسی برابر است با $(n-1)!!$ . ^[۶]

مثال

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

$K_{1}:0$	$K_{2}:1$	$K_{3}:3$	$K_{4}:6$

$K_{5}:10$	$K_{6}:15$	$K_{7}:21$	$K_{8}:28$

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

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

${\begin{bmatrix}0&1&1&\ldots &1\\1&0&1&\ldots &1\\1&1&\ddots &\ddots &\vdots \\\vdots &\vdots &\ddots &0&1\\1&\ldots &1&1&0\end{bmatrix}}_{n*n}$

منابع

↑ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
↑ Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 0191630624 {{citation}}: External link in |contributionurl= (help); Unknown parameter |contributionurl= ignored (|contribution-url= suggested) (help).
↑ Read, Ronald C.; Wilson, Robin J. (1998), An Atlas of Graphs, Clarendon Press, p. ii, ISBN 9780198532897.
↑ Mystic Rose, nrich.maths.org, retrieved 23 January 2012.
↑ ^۵٫۰ ^۵٫۱ ^۵٫۲ Rosen, Kenneth (2018-07-09). Discrete Mathematics and Its Applications (به انگلیسی).
↑ 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. Retrieved 2007. {{cite book}}: Check date values in: |بازبینی= (help)

این یک مقالهٔ خرد ریاضیات است. می‌توانید با گسترش آن به ویکی‌پدیا کمک کنید.

[:1-1] Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.

[knuth-2] Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 0191630624 {{citation}}: External link in |contributionurl= (help); Unknown parameter |contributionurl= ignored (|contribution-url= suggested) (help).

[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.

[:0-5] ۵٫۰ ^۵٫۱ ^۵٫۲ Rosen, Kenneth (2018-07-09). Discrete Mathematics and Its Applications (به انگلیسی).

[6] Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]