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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
K7, رسم بياني كامل بـ 7رؤوس

في نظرية المخططات, رسم بياني كامل, هو رسم بياني غير موجّه بسيط بحيث أنه كل زوج من الرؤوس متصل بضلع.

هندسيا, يشكل K3 مجموعة أضلاع مثلث, ويشكل K4 مجموعة أضلاع رباعي سطوح.

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

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

خصائص[عدل]

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

أمثلة[عدل]

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

K1: 0 K2: 1 K3: 3 K4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K5: 10 K6: 15 K7: 21 K8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K9: 36 K10: 45 K11: 55 K12: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg

راجع أيضا[عدل]

مصادر[عدل]

  1. ^ Gries، David؛ Schneider، Fred B. (1993)، A Logical Approach to Discrete Math، Springer-Verlag، صفحة 436  More than one of |author1= و |last1= specified (help); More than one of |author2= و |last2= specified (help).