اتصال الرؤوس

في نظرية الرسم البياني ، يقال إن الرسم البياني المتصل G هو k -vertex-connected (أو k -connected ) إذا كان يحتوي على أكثر من k رأسًا ويظل متصلًا كلما تمت إزالة أقل من k رأسًا.

إن اتصال الرؤوس ، أو الاتصال فقط ، للرسم البياني هو أكبر قيمة k التي يكون عندها الرسم البياني متصلاً بـ k رأسًا.

تتمتع الرسوم البيانية (باستثناء الرسوم البيانية الكاملة ) باتصال k إذا كان k هو حجم أصغر مجموعة فرعية من الرؤوس التي يؤدي حذفها إلى فصل الرسم البياني. ^{[ 1 ]} في الرسوم البيانية الكاملة ، لا توجد مجموعة فرعية يؤدي حذفها إلى فصل الرسم البياني. تُعدّل بعض المصادر تعريف الاتصال للتعامل مع هذه الحالة، بتعريفه على أنه حجم أصغر مجموعة فرعية من الرؤوس التي يؤدي حذفها إما إلى رسم بياني منفصل أو رأس واحد. بالنسبة لهذا التباين، يكون اتصال الرسم البياني الكامل${\displaystyle K_{n}}$يكون${\displaystyle n-1}$[ ^{2 ]​}

التعريف المكافئ هو أن الرسم البياني الذي يحتوي على رأسين على الأقل يكون متصلاً من الرتبة k إذا كان من الممكن، لكل زوج من رؤوسه، إيجاد k مسارًا مستقلاً عن الرؤوس يربط بين هذين الرأسين؛ انظر نظرية مينجر ( ديستل 2005 ، ص 55) . ينتج عن هذا التعريف نفس النتيجة، n − 1، لاتصال الرسم البياني الكامل K _n . ^{[ 1 ]}   

الرسم البياني المتصل من الدرجة k هو رسم بياني متصل بحكم التعريف ؛ ويسمى ثنائي الاتصال عندما يكون k ≥ 2 وثلاثي الاتصال عندما يكون k ≥ 3.

يمكن حساب اتصال الرؤوس في الرسم البياني المدخل G في وقت متعدد الحدود بالطريقة التالية ^{[ 4 ]} : ​​ضع في اعتبارك جميع الأزواج الممكنة${\displaystyle (s,t)}$لفصل العقد غير المتجاورة، باستخدام نظرية مينجر لتبرير أن الفاصل ذو الحجم الأدنى لـ${\displaystyle (s,t)}$يمثل عدد المسارات المستقلة عن الرؤوس بينهما، ويتم ترميز المدخلات عن طريق مضاعفة كل رأس كحافة لتقليلها إلى حساب عدد المسارات المستقلة عن الحواف، ويتم حساب الحد الأقصى لعدد هذه المسارات عن طريق حساب الحد الأقصى للتدفق في الرسم البياني بينهما${\displaystyle s}$و${\displaystyle t}$بسعة 1 لكل حافة، مع ملاحظة أن تدفق${\displaystyle k}$يتوافق هذا الرسم البياني، وفقًا لنظرية التدفق التكاملي ، مع${\displaystyle k}$المسارات المستقلة عن الحواف من${\displaystyle s}$ل${\displaystyle t}$.

ليكن k≥2 .

• كل${\displaystyle k}$رسم بياني متصل من الرتبة على الأقل${\displaystyle 2k}$يحتوي على دورة طولها على الأقل${\displaystyle 2k}$
• في${\displaystyle k}$الرسم البياني المتصل، أي${\displaystyle k}$الرؤوس في${\displaystyle G}$تقع على دورة مشتركة . ^{[ 5 ]}

مساحة الدورة لـ${\displaystyle 3}$يتم توليد الرسم البياني المتصل بواسطة دوراته المستحثة غير المنفصلة . ^{[ 6 ]}

رسم بياني يحتوي على الأقل${\displaystyle 2k}$يُطلق على الرؤوس اسم${\displaystyle k}$-مرتبط إذا كان هناك${\displaystyle k}$مسارات منفصلة لأي تسلسلات ${\displaystyle a_{1},\dots ,a_{k}}$و${\displaystyle b_{1},\dots ,b_{k}}$ل${\displaystyle 2k}$رؤوس مميزة. كل${\displaystyle k}$الرسم البياني المرتبط هو${\displaystyle (2k-1)}$الرسم البياني المتصل، ولكن ليس بالضرورة${\displaystyle 2k}$-متصل. ^{[ 7 ]}

إذا كان الرسم البياني${\displaystyle 2k}$-متصل ولديه درجة متوسطة لا تقل عن${\displaystyle 16k}$إذن فهو${\displaystyle k}$مرتبط. ^{[ 8 ]}

• رسم بياني متصل بالحواف من الرتبة k
• الاتصال (نظرية الرسم البياني)
• نظرية مينجر
• التماسك الهيكلي
• تضمين Tutte
• فاصل الرؤوس

• ديستيل، راينهارد (2005)، نظرية الرسم البياني (  الطبعة الثالثة)، برلين، نيويورك: Springer-Verlag، ISBN 978-3-540-26183-4
• ديستل، راينهارد (2012)، نظرية الرسم البياني (الطبعة الإلكترونية الرابعة المصححة  ).
• ديستيل، راينهارد (2016)، نظرية الرسم البياني (  الطبعة الخامسة)، برلين، نيويورك: Springer-Verlag، ISBN 978-3-662-53621-6