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

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

K 7

, رسم بياني كامل بـ 7رؤوس

هندسيا، يشكل $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$

راجع أيضا

مصادر

Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, صفحة 436 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة); الوسيط |مؤلف1= و |الأخير1= تكرر أكثر من مرة (مساعدة); الوسيط |مؤلف2= و |الأخير2= تكرر أكثر من مرة (مساعدة)CS1 maint: ref=harv (link).

بوابة رياضيات
بوابة علم الحاسوب

في كومنز صور وملفات عن: رسم بياني كامل

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, صفحة 436 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة); الوسيط |مؤلف1= و |الأخير1= تكرر أكثر من مرة (مساعدة); الوسيط |مؤلف2= و |الأخير2= تكرر أكثر من مرة (مساعدة)CS1 maint: ref=harv (link).