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

في مجال نظرية المخططات الرياضية ، يُعرف المخطط الكامل بأنه مخطط بسيط غير موجه، حيث يرتبط كل زوج من الرؤوس المختلفة بحافة فريدة . أما المخطط الموجه الكامل فهو مخطط موجه، حيث يرتبط كل زوج من الرؤوس المختلفة بزوج من الحواف الفريدة (حافة واحدة في كل اتجاه). ^{[ 1 ]}

يُؤرَّخ عادةً لنظرية الرسوم البيانية بأنها بدأت مع عمل ليونارد أويلر عام 1736 حول جسور كونيغسبرغ السبعة . مع ذلك، فقد ظهرت رسومات للرسوم البيانية الكاملة، برؤوسها الموضوعة على نقاط مضلع منتظم ، في القرن الثالث عشر، في عمل رامون لول . ^{[ 2 ]} يُشار إلى هذا النوع من الرسومات أحيانًا باسم الوردة الصوفية . ^{[ 3 ]}

يُرمز للرسم البياني الكامل ذي n رأسًا بالرمز K_{_n} . تزعم بعض المصادر أن الحرف K في هذا الرمز يرمز إلى الكلمة الألمانية komplett ، ^{[ 4 ]} لكن الاسم الألماني للرسم البياني الكامل، vollständiger Graph ، لا يحتوي على الحرف K ، وتذكر مصادر أخرى أن هذا الرمز يُكرّم إسهامات كازيميرز كوراتوفسكي في نظرية الرسوم البيانية. ^{[ 5 ]}

للرسم البياني K _{_n عدد} n ( n -1)/2 من الحواف ( وهو عدد مثلثي )، وهو رسم بياني منتظم من الدرجة n -1 . جميع الرسوم البيانية الكاملة هي زمر عظمى خاصة بها . وهي متصلة اتصالاً تاماً، حيث أن القطع الرأسي الوحيد الذي يفصل الرسم البياني هو مجموعة الرؤوس الكاملة. الرسم البياني المكمل للرسم البياني الكامل هو رسم بياني فارغ .

إذا تم إعطاء كل حافة من حواف الرسم البياني الكامل اتجاهًا ، فإن الرسم البياني الموجه الناتج يسمى بطولة .

يمكن تقسيم الرسم البياني K _{_n} إلى n شجرة T _{_i} بحيث تحتوي T _i على i رأسًا. ^{[ 6 ]} تتساءل فرضية رينجل عما إذا كان من الممكن تقسيم الرسم البياني الكامل K _{_{2n +1}} إلى نسخ من أي شجرة ذات n حافة. ^{​​[ 7 ]} من المعروف أن هذا صحيح بالنسبة لقيم n الكبيرة بما فيه الكفاية . ^{[ 8 ] [ 9 ]}

يُعطى عدد جميع المسارات المختلفة بين زوج محدد من الرؤوس في K _{n +2} بالصيغة ^{[ 10 ]}

${\displaystyle w_{n+2}=n!e_{n}=\lfloor en!\rfloor ,}$

حيث يشير e إلى ثابت أويلر ، و

${\displaystyle e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}.}$

يتم تحديد عدد التطابقات في الرسوم البيانية الكاملة بواسطة أرقام الهواتف

1، 1، 2، 4، 10، 26، 76، 232، 764، 2620، 9496، 35696، 140152، 568504، 2390480، 10349536، 46206736، ... (التسلسل A000085 في OEIS ) .

تُعطي هذه الأرقام أكبر قيمة ممكنة لمؤشر هوسويا لرسم بياني ذي n رأسًا. ^{[ 11 ]} يُعطى عدد التطابقات التامة للرسم البياني الكامل K _{_n} (حيث n عدد زوجي) بالعامل المزدوج ( n - 1)!! . ^{[ 12 ]}

أرقام التقاطعات حتى K ₂₇ معروفة، بينما يتطلب K ₂₈ إما 7233 أو 7234 تقاطعًا. يتم جمع المزيد من القيم من خلال مشروع رقم التقاطع المستقيم. ^{[ 13 ]} أرقام التقاطع المستقيم لـ K _n هي

0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... (التسلسل A014540 في OEIS ) .

الرسم البياني الكامل ذو n عقدة هو رسم بياني لحواف مُجَسَّم بسيط ذي ( n - 1) _بُعد . هندسيًا، يُشكِّل K₃ مجموعة حواف مثلث ، _و K₄ مجموعة حواف رباعي الأوجه ، ^وهكذا . مُجَسَّم تشاسار ، وهو مُجَسَّم غير محدب ذو طوبولوجيا طارة ، له الرسم البياني الكامل K₇ كهيكل عظمي له . ^[ ₁₅ ^] كل مُجَسَّم مُجاور في أربعة أبعاد أو أكثر له أيضًا هيكل عظمي كامل.

جميع المخططات K1 إلى K4 هي مخططات مستوية. مع ذلك، يجب _أن يحتوي كل رسم مستوي لمخطط كامل بخمسة رؤوس أو أكثر على تقاطع، ويلعب المخطط الكامل غير المستوي _{K5 دورًا محوريًا} في توصيف المخططات المستوية: فبحسب نظرية كوراتوفسكي ، يكون المخطط مستويًا إذا وفقط إذا لم يحتوِ على K5 أو المخطط الثنائي الكامل K3,3 كجزء فرعي، وبحسب _نظرية فاغنر، تنطبق النتيجة نفسها على المخططات الجزئية بدلًا من الأجزاء الفرعية. وباعتباره جزءًا من عائلة بيترسن ، يلعب K6 دورًا مشابهًا كأحد المخططات الجزئية المحظورة للتضمين غير المرتبط . ^{[ 16 ]} بعبارة أخرى، وكماأثبت ^{كونواي وغوردون [ 17 ]} _{، فإن كل تضمين لـ} K6 في فضاء ثلاثي الأبعاد يكون مرتبطًا جوهريًا، مع وجود زوج واحد على الأقل من المثلثات المرتبطة _. أظهر كونواي وجوردون أيضًا أن أي تضمين ثلاثي الأبعاد لـ K ₇ يحتوي على دورة هاميلتونية مضمنة في الفضاء كعقدة غير تافهة .

أكمل الرسوم البيانية حول${\displaystyle n}$الرؤوس، لـ${\displaystyle n}$الأرقام بين 1 و 12 موضحة أدناه مع عدد الحواف:

ك 1 : 0	ك ٢ : ١	ك 3 : 3	ك 4 : 6
ك ٥ : ١٠	ك 6 : 15	ك 7 : 21	ك 8 : 28
ك 9 : 36	K 10 : 45	ك 11 : 55	ك 12 : 66

• شبكة متصلة بالكامل ، في مجال شبكات الحاسوب
• الرسم البياني الثنائي الكامل (أو ثنائي الزمرة )، وهو رسم بياني ثنائي خاص حيث يكون كل رأس على أحد جانبي التقسيم متصلاً بكل رأس على الجانب الآخر
• المعقد البسيط ، وهو مطابق للرسم البياني الكامل لـ${\displaystyle n+1}$الرؤوس، حيث${\displaystyle n}$هو بُعد المُجَسَّم البسيط.

• وايسشتاين، إريك دبليو. "الرسم البياني الكامل" . عالم الرياضيات .