الاتصال الطرفي

في نظرية الرسم البياني ، يكون الرسم البياني المتصل متصلاً بـ k حافة إذا ظل متصلاً كلما تمت إزالة أقل من k حافة.

إن اتصال الحواف في الرسم البياني هو أكبر قيمة k التي يكون عندها الرسم البياني متصلاً بالحواف من الدرجة k .

تمت دراسة اتصال الحواف وحصر الرسوم البيانية المتصلة بالحواف من قبل كاميل جوردان في عام 1869. ^{[ 1 ]}

يترك${\displaystyle G=(V,E)}$ليكن رسمًا بيانيًا عشوائيًا. إذا كان الرسم البياني الفرعي${\displaystyle G'=(V,E\setminus X)}$متصل للجميع${\displaystyle X\subseteq E}$أين${\displaystyle |X|<k}$إذاً، يُقال إن G متصلة من الدرجة k من الحواف. اتصال الحواف لـ${\displaystyle G}$هي القيمة القصوى k التي تجعل G متصلة بـ k حافة. ​​أصغر مجموعة X التي يؤدي حذفها إلى فصل G تُسمى قطعًا أدنى في G.

يُقدّم صيغ اتصال الحواف لنظرية مينجر توصيفًا بديلًا ومكافئًا، من حيث المسارات المنفصلة حوافًا في الرسم البياني. إذا وفقط إذا شكّل كل رأسين في الرسم البياني G نهايتي k مسارًا، لا يشترك أي مسارين منها في حافة واحدة، فإن G يكون متصلًا k حافة. ​​من جهة، يكون هذا سهلًا: إذا وُجد نظام مسارات كهذا، فإن كل مجموعة X تحتوي على أقل من k حافة تكون منفصلة عن مسار واحد على الأقل، ويبقى زوج الرؤوس متصلًا حتى بعد حذف المجموعة X. من جهة أخرى، يمكن إثبات وجود نظام مسارات لكل زوج من الرؤوس في الرسم البياني لا يمكن فصله بإزالة عدد قليل من الحواف، باستخدام نظرية التدفق الأقصى والقطع الأدنى من نظرية تدفقات الشبكات .

تُعطي درجة الرأس الدنيا حدًا أعلى بديهيًا لاتصال الحواف. أي، إذا كان الرسم البياني${\displaystyle G=(V,E)}$إذا كانت المجموعة V متصلة بـ k حافة، فمن الضروري أن يكون k  ≤  δ( G )، حيث δ( G ) هي أدنى درجة لأي رأس v  ∈ V. يؤدي حذف جميع الحواف المتصلة بالرأس v إلى فصل v عن الرسم البياني. 

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

يمكن أيضًا تمييز الرسوم البيانية المتصلة بحافتين من خلال غياب الجسور ، أو من خلال وجود تجزئة أذنية ، أو من خلال نظرية روبنز التي تنص على أن هذه هي بالضبط الرسوم البيانية التي لها اتجاه قوي . ^{[ 3 ]}

وبموجب نتيجة لنظرية ناش-ويليامز ، فإن اتصال الحواف في الرسم البياني يوفر حدودًا لعدد الأشجار الممتدة المنفصلة الحواف التي يمكن العثور عليها داخل الرسم البياني.

توجد خوارزمية ذات زمن متعدد الحدود لتحديد أكبر قيمة لـ k التي تجعل الرسم البياني G متصلاً من الدرجة k من الحواف. تقوم خوارزمية بسيطة، لكل زوج (u,v) ، بتحديد أقصى تدفق من u إلى v مع ضبط سعة جميع الحواف في G على 1 لكلا الاتجاهين. يكون الرسم البياني متصلاً من الدرجة k من الحواف إذا وفقط إذا كان أقصى تدفق من u إلى v يساوي k على الأقل لأي زوج (u,v) ، وبالتالي فإن k هو أقل تدفق من u إلى v بين جميع الأزواج (u,v) .

إذا كان n هو عدد الرؤوس في الرسم البياني، فإن هذه الخوارزمية البسيطة ستؤدي${\displaystyle O(n^{2})}$تكرارات مسألة التدفق الأقصى، والتي يمكن حلها في${\displaystyle O(n^{3})}$الوقت. وبالتالي فإن تعقيد الخوارزمية البسيطة الموضحة أعلاه هو${\displaystyle O(n^{5})}$إجمالاً.

ستقوم خوارزمية محسّنة بحل مشكلة التدفق الأقصى لكل زوج (u,v) حيث تكون u ثابتة بشكل تعسفي بينما تتغير v عبر جميع الرؤوس. هذا يقلل من التعقيد إلى${\displaystyle O(n^{4})}$وهو سليم لأنه إذا وُجد قطع بسعة أقل من k ، فإنه سيفصل u عن رأس آخر. ويمكن تحسينه أكثر باستخدام خوارزمية غابو التي تعمل في أسوأ الحالات${\displaystyle O(n^{3})}$الوقت. ^{[ 4 ]}

يوفر متغير كارغر-شتاين لخوارزمية كارغر خوارزمية عشوائية أسرع لتحديد الاتصال، مع وقت تشغيل متوقع${\displaystyle O(n^{2}\log ^{3}n)}$[ ^{5 ]​}

مشكلة ذات صلة: إيجاد أصغر رسم بياني فرعي ممتد من G ذي k حافة متصلة (أي: اختيار أقل عدد ممكن من الحواف في G بحيث يكون اختيارك متصلاً بـ k حافة) هي مشكلة صعبة من نوع NP بالنسبة لـ${\displaystyle k\geq 2}$[ ^{6 ]​}

• الرسم البياني المتصل بـ k رأس
• الاتصال (نظرية الرسم البياني)
• استبعاد المطابقة