رسم بياني كامل

معلومات عامة
صنف فرعي من	القائمة ... بيان غير مُوجَّه ; بيان مرتبط ; cluster graph ; بيان فِدَريّ ; complete multipartite graph ; threshold graph ; Hamming graph ; Kneser graph ; traceable graph ; Hamilton-connected graph ; symmetric graph ; strongly regular graph
يدرسه	نظرية البيان
له ميزة	ترابط رؤوسي ; ترابط وصلاتي
نصف قطر البيان	1
قطر البيان	1
النقيض	edgeless graph

في نظرية المخططات, الرسم البياني الكامل (بالإنجليزية: Complete Graph)‏, هو رسم بياني غير موجه بسيط بحيث أنه كل زوج من الرؤوس متصل بضلع.

هندسيا، يشكل $K 3$ مجموعة أضلاع مثلث، ويشكل $K 4$ مجموعة أضلاع رباعي سطوح.

$K 1$ وحتى $K 4$ تشكل مخططات مستوية, بينما كل رسم مستو لرسم بياني كامل بخمسة رؤوس أو أكثر يحتوي على نقطة تقاطع.

في نظرية التعقيد الحسابي, تمت برهنة أن مسألة ايجاد أكبر رسم بياني جزئي كامل في رسم بياني معطى هي مسألة np صعبة, بينما مسألة تحديد وجود رسم بياني كامل هي مسألة NP كاملة.

خصائص

للرسم البياني الكامل بـ $n$ رؤوس يوجد ${\binom {n}{2}}={\frac {n(n-1)}{2}}$ أضلاع (عدد مثلثي), ويشار إليه بـ $K n$ (من komplett بالألمانية والتي تعني كامل).^[1] هو رسم بياني منتظم من الدرجة $n - 1$ .

أمثلة

رسوم بيانية كاملة ذات n أضلاع، لكل n بين 1 و 12, تظهر بالأسفل مع عدد الأضلاع:

$K 1 : 0$	$K 2 : 1$	$K 3 : 3$	$K 4 : 6$

$K 5 : 10$	$K 6 : 15$	$K 7 : 21$	$K 8 : 28$

$K 9 : 36$	$K 10 : 45$	$K 11 : 55$	$K 12 : 66$

راجع أيضا

مصادر

^ David Gries، David؛ Fred B. Schneider، Fred B. (1993)، A Logical Approach to Discrete Math، Springer-Verlag، ص. 436 {{استشهاد}}: الوسيط |الأخير1= و|مؤلف1= تكرر أكثر من مرة (مساعدة) والوسيط |الأخير2= و|مؤلف2= تكرر أكثر من مرة (مساعدة).

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.

[1] David Gries، David؛ Fred B. Schneider، Fred B. (1993)، A Logical Approach to Discrete Math، Springer-Verlag، ص. 436 {{استشهاد}}: الوسيط |الأخير1= و|مؤلف1= تكرر أكثر من مرة (مساعدة) والوسيط |الأخير2= و|مؤلف2= تكرر أكثر من مرة (مساعدة).

[لغات أخرى]

[لغات أخرى]

[الإنجليزية]

[لغات أخرى]

[الإنجليزية]

[الإنجليزية]

[الإنجليزية]

[الإنجليزية]

[الإنجليزية]

[الإنجليزية]

[الإنجليزية]

[الإنجليزية]

[لغات أخرى]

[لغات أخرى]

[الإنجليزية]

[1]

صنف فرعي من	القائمة ... بيان غير مُوجَّه ^{[لغات أخرى]} بيان مرتبط ^{[لغات أخرى]} cluster graph ^{[الإنجليزية]} بيان فِدَريّ ^{[لغات أخرى]} complete multipartite graph ^{[الإنجليزية]} threshold graph ^{[الإنجليزية]} Hamming graph ^{[الإنجليزية]} Kneser graph ^{[الإنجليزية]} traceable graph ^{[الإنجليزية]} Hamilton-connected graph ^{[الإنجليزية]} symmetric graph ^{[الإنجليزية]} strongly regular graph ^{[الإنجليزية]}
يدرسه	نظرية البيان
له ميزة	ترابط رؤوسي ^{[لغات أخرى]} ترابط وصلاتي ^{[لغات أخرى]}
نصف قطر البيان	1
قطر البيان	1
النقيض	edgeless graph ^{[الإنجليزية]}