الاتصال (نظرية الرسم البياني)

يصبح هذا الرسم البياني غير متصل عند إزالة الحافة المتقطعة.

في الرياضيات وعلوم الحاسوب ، يُعدّ الاتصال أحد المفاهيم الأساسية في نظرية الرسوم البيانية : إذ يُحدد الحد الأدنى لعدد العناصر (العُقد أو الحواف) التي يجب إزالتها لفصل العُقد المتبقية إلى رسمين بيانيين فرعيين معزولين أو أكثر . ^{[ 1 ]} ويرتبط هذا المفهوم ارتباطًا وثيقًا بنظرية مسائل تدفق الشبكات . ويُعتبر اتصال الرسم البياني مقياسًا مهمًا لمرونته كشبكة.

الرؤوس المتصلة والرسوم البيانية

عند الرأس 0، يكون هذا الرسم البياني غير متصل. أما بقية الرسم البياني فهي متصلة.

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

يُقال إن الرسم البياني متصل إذا كان كل زوج من رؤوسه متصلاً. وهذا يعني وجود مسار بين كل زوج من الرؤوس. أما الرسم البياني غير الموجه وغير المتصل فيُسمى غير متصل . وبالتالي، يكون الرسم البياني غير الموجه $G$ غير متصل إذا وُجد رأسان في $G$ بحيث لا يوجد مسار في $G$ ينتهي بهذين الرأسين. الرسم البياني ذو الرأس الواحد فقط يكون متصلاً. أما الرسم البياني عديم الحواف ذو رأسين أو أكثر فيكون غير متصل.

A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is unilaterally connected or unilateral (also called semiconnected) if it contains a directed path from $u$ to $v$ or a directed path from $v$ to $u$ for every pair of vertices $u, v$ .^[2] It is strongly connected, or simply strong, if it contains a directed path from $u$ to $v$ and a directed path from $v$ to $u$ for every pair of vertices $u, v$ .

Components and cuts

A connected component is a maximal connected subgraph of an undirected graph. Each vertex belongs to exactly one connected component, as does each edge. A graph is connected if and only if it has exactly one connected component.

The strong components are the maximal strongly connected subgraphs of a directed graph.

A vertex cut or separating set of a connected graph $G$ is a set of vertices whose removal renders $G$ disconnected. The vertex connectivity $κ (G)$ (where $G$ is not a complete graph) is the size of a smallest vertex cut. A graph is called $k$ -vertex-connected or $k$ -connected if its vertex connectivity is $k$ or greater.

More precisely, any graph $G$ (complete or not) is said to be $k$ -vertex-connected if it contains at least $k + 1$ vertices, but does not contain a set of $k - 1$ vertices whose removal disconnects the graph; and $κ (G)$ is defined as the largest $k$ such that $G$ is $k$ -connected. In particular, a complete graph with $n$ vertices, denoted $K n$ , has no vertex cuts at all, but $κ (K n) = n - 1$ .

القطع الرأسي لرأسين $u$ و $v$ هو مجموعة من الرؤوس التي يؤدي حذفها من الرسم البياني إلى فصل $u$ و $v$ . الاتصال المحلي $κ (u, v)$ هو حجم أصغر قطع رأسي يفصل $u$ و $v$ . الاتصال المحلي متناظر في الرسوم البيانية غير الموجهة؛ أي أن $κ (u, v) = κ (v, u)$ . علاوة على ذلك، باستثناء الرسوم البيانية الكاملة، فإن $κ (G)$ يساوي الحد الأدنى لـ $κ (u, v)$ على جميع أزواج الرؤوس غير المتجاورة $u و v$ .

يُطلق على الاتصال $الثنائي أيضًا اسم$ الاتصال الثنائي، ويُطلق على الاتصال $الثلاثي$ أيضًا اسم الاتصال الثلاثي . ويُطلق أحيانًا على الرسم البياني $G$ المتصل ولكنه ليس متصلًا $ثنائيًا اسم الرسم البياني$ القابل للفصل .

يمكن تعريف مفاهيم مماثلة للحواف. في الحالة البسيطة التي يؤدي فيها قطع حافة واحدة محددة إلى فصل الرسم البياني، تُسمى تلك الحافة جسرًا . وبشكل أعم، يُعرَّف قطع الحواف في الرسم البياني $G$ بأنه مجموعة من الحواف التي يؤدي حذفها إلى فصل الرسم البياني. يُمثل معامل اتصال الحواف $λ (G)$ طول أصغر قطع للحواف، بينما يُمثل معامل اتصال الحواف المحلي $λ (u, v)$ بين رأسين $u و v$ طول أصغر قطع للحواف يفصل $u$ عن $v$ . وكما ذكرنا، فإن معامل اتصال الحواف المحلي متناظر. يُسمى الرسم البياني $k-$ متصلًا بالحواف إذا كان معامل اتصال حوافه $k$ أو أكبر.

يُقال إن الرسم البياني متصل اتصالاً تاماً إذا كانت درجة اتصاله تساوي أدنى درجة له . ويُقال إن الرسم البياني متصل اتصالاً تاماً بالحواف إذا كانت درجة اتصال حوافه تساوي أدنى درجة له. ^{[ 3 ]}

الاتصال الفائق والمفرط

يُقال عن الرسم البياني أنه فائق الاتصال أو فائق-κ إذا كان كل قطع رأسي أدنى يعزل رأسًا. ويُقال عن الرسم البياني أنه فائق الاتصال أو فائق-κ إذا كان حذف كل قطع رأسي أدنى يُنشئ مكونين فقط، أحدهما رأس معزول. ويُقال عن الرسم البياني أنه شبه فائق الاتصال أو شبه فائق-κ إذا كان أي قطع رأسي أدنى يفصل الرسم البياني إلى مكونين فقط. ^{[ 4 ]}

بتعبير أدق: يُقال عن الرسم البياني المتصل $G أنه$ فائق الاتصال أو فائق-κ إذا كانت جميع القطوع الرأسية الدنيا تتكون من الرؤوس المجاورة لرأس واحد (أدنى درجة). ويُقال عن الرسم البياني المتصل $G أنه$ فائق الاتصال الحافي أو فائق-λ إذا كانت جميع القطوع الحافية الدنيا تتكون من الحواف المتصلة برأس ما (أدنى درجة). ^{[ 5 ]}

تُسمى مجموعة القطع $X$ في $G مجموعة قطع غير تافهة إذا لم تحتوي$ $X$ على الجوار $N(u)$ لأي رأس $u \notin X.$ عندئذٍ تكون خاصية الاتصال الفائق $\kappa _{1}$ من $G$ هو $\kappa _{1}(G)=\min\{|X|:X{\text{ مجموعة قطع غير تافهة}}\}.$

قطع حافة غير تافه والاتصال الفائق للحافة $\lambda _{1}(G)$ يتم تعريفها بشكل مماثل. ^{[ 6 ]}

نظرية مينجر

إحدى أهم الحقائق المتعلقة بالاتصال في الرسوم البيانية هي نظرية مينجر ، التي تحدد الاتصال والاتصال بين الحواف في الرسم البياني من حيث عدد المسارات المستقلة بين الرؤوس.

إذا كان $u$ و $v$ رأسين في الرسم البياني $G$ ، فإن مجموعة المسارات بين $u$ و $v$ تُسمى مستقلة إذا لم يشترك أي مسارين منها في رأس واحد (باستثناء $u$ و $v$ أنفسهما). وبالمثل، تُسمى المجموعة مستقلة عن الحواف إذا لم يشترك أي مسارين فيها في حافة واحدة. يُكتب عدد المسارات المستقلة بين $u$ و $v على النحو$ $κ'(u, v)$ ، ويُكتب عدد المسارات المستقلة عن الحواف بين $u$ و $v على النحو$ $λ'(u, v)$ .

تنص نظرية مينجر على أنه بالنسبة للرؤوس المختلفة u و v ، فإن $λ (u, v)$ تساوي $λ'(u, v)$ ، وإذا لم يكن u مجاورًا لـ v أيضًا، فإن $κ (u, v)$ تساوي $κ'(u, v)$ . ^{[ 7 ]}^{[ 8 ]} هذه الحقيقة هي في الواقع حالة خاصة من نظرية التدفق الأقصى والقطع الأدنى .

الجوانب الحسابية

يمكن حل مشكلة تحديد ما إذا كان رأسان في رسم بياني متصلين بكفاءة باستخدام خوارزمية بحث ، مثل البحث بالعرض أولاً . وبشكل عام، من السهل حسابيًا تحديد ما إذا كان الرسم البياني متصلاً (على سبيل المثال، باستخدام بنية بيانات المجموعة المنفصلة )، أو حساب عدد المكونات المتصلة. يمكن كتابة خوارزمية بسيطة بلغة شبه رمزية كما يلي:

ابدأ من أي عقدة عشوائية في الرسم البياني $G.$
انطلق من تلك العقدة باستخدام البحث العميق أولاً أو البحث العرضي أولاً، مع حساب جميع العقد التي تم الوصول إليها.
بمجرد اجتياز الرسم البياني بالكامل، إذا كان عدد العقد المحسوبة يساوي عدد عقد $G$ ، فإن الرسم البياني يكون متصلاً؛ وإلا فإنه يكون غير متصل.

بحسب نظرية مينجر ، لأي رأسين $u$ و $v$ في رسم بياني متصل $G$ ، يمكن تحديد العددين $κ (u, v)$ و $λ (u, v) بكفاءة باستخدام خوارزمية$ التدفق الأقصى والقطع الأدنى . ويمكن بعد ذلك حساب اتصال $G$ واتصال حوافه كأصغر قيم لـ $κ (u, v)$ و $λ (u, v)$ على التوالي.

في نظرية التعقيد الحسابي ، SL هي فئة من المشكلات التي يمكن اختزالها في فضاء لوغاريتمي إلى مشكلة تحديد ما إذا كان رأسان في الرسم البياني متصلين، والتي أثبت عمر رينغولد أنها تساوي L في عام 2004. ^[⁹^] وبالتالي، يمكن حل اتصال الرسم البياني غير الموجه في مساحة $O(log$ $n$ $) .$

تُسمى مسألة حساب احتمالية اتصال رسم بياني عشوائي من نوع برنولي بموثوقية الشبكة، وتُسمى مسألة حساب ما إذا كان رأسان مُعطيان متصلين بمسألة موثوقية ST. كلتا المسألتين من المسائل الصعبة من نوع #P . ^{[ 10 ]}

عدد الرسوم البيانية المتصلة

يُدرج عدد الرسوم البيانية المتصلة والمصنفة والمختلفة ذات n عقدة في الموسوعة الإلكترونية لتسلسلات الأعداد الصحيحة كتسلسل A001187 . أما الحدود القليلة الأولى غير التافهة فهي

ن	الرسوم البيانية
1	1
2	1
3	4
4	38
5	728
6	26704
7	1866256
8	251548592

أمثلة

تكون اتصالات الرؤوس والحواف في الرسم البياني غير المتصل $صفرًا$ .
$1-$ الاتصالية تعادل الاتصالية بالنسبة للرسوم البيانية التي تحتوي على رأسين على الأقل.
الرسم البياني الكامل المكون من $n$ رأسًا له اتصال حواف يساوي $n - 1.$ كل رسم بياني بسيط آخر مكون من $n$ رأسًا له اتصال حواف أصغر تمامًا.
في الشجرة ، يكون الاتصال المحلي بين أي رأسين متميزين هو $1$ .

حدود الاتصال

تكون نسبة اتصال الرؤوس في الرسم البياني أقل من أو تساوي نسبة اتصال الحواف. أي أن $κ (G) \leq λ (G)$ .
تكون درجة اتصال الحواف في الرسم البياني الذي يحتوي على رأسين على الأقل أقل من أو تساوي الحد الأدنى لدرجة الرسم البياني، لأن إزالة جميع الحواف المتصلة برأس ذي درجة دنيا سيؤدي إلى فصل ذلك الرأس عن بقية الرسم البياني. ^{[ 1 ]}
بالنسبة للرسم البياني المتعدي الرؤوس من الدرجة $d$ ، لدينا: $2(d + 1)/3 \leq κ (G) \leq λ (G) = d$ . ^{[ 11 ]}
بالنسبة للرسم البياني المتعدي الرؤوس من الدرجة $d \leq 4$ ، أو لأي رسم بياني كايلي الأدنى (غير الموجه) من الدرجة $d$ ، أو لأي رسم بياني متناظر من الدرجة $d$ ، فإن كلا نوعي الاتصال متساويان: $κ (G) = λ (G) = d$ . ^{[ 12 ]}

خصائص أخرى

يتم الحفاظ على الترابط من خلال تماثلات الرسم البياني .
إذا كانت $G$ متصلة، فإن الرسم البياني الخطي الخاص بها $L (G)$ يكون متصلاً أيضًا.
يكون الرسم البياني $G متصلاً بالحواف من الدرجة$ $2$ إذا وفقط إذا كان له اتجاه متصل بقوة.
تنص نظرية بالينسكي على أن الرسم البياني متعدد الأوجه ( الهيكل $العظمي$ ) لمتعدد الأوجه المحدب ذي البعد $k$ هو رسم بياني متصل $بـ k رأس.$ ^[¹³^] وتُعطي نظرية شتاينيتز السابقة ، التي تنص على أن أي رسم بياني مستوٍ متصل بـ 3 رؤوس هو رسم بياني متعدد الأوجه ( نظرية شتاينيتز )، عكسًا جزئيًا لهذه النظرية .
وفقًا لنظرية ديراك في خوارزمية الرسم البياني الهندسي ، إذا كان الرسم البياني متصلًا من الدرجة $k لـ$ $k \geq 2$ ، فإنه لكل مجموعة من $k$ رأسًا في الرسم البياني توجد دورة تمر بجميع الرؤوس في تلك المجموعة. ^{[ 14 ]}^{[ 15 ]} والعكس صحيح عندما $k = 2$ .

انظر أيضاً

مراجع

1 2 ديستل، ر. (2005). "نظرية الرسم البياني، الطبعة الإلكترونية" . ص 12.
↑ الفصل 11: الرسوم البيانية الموجهة: مبدأ الازدواجية للرسوم البيانية الموجهة: التعريف
↑ غروس، جوناثان ل.؛ يلين، جاي (2004). دليل نظرية الرسم البياني . مطبعة سي آر سي . ص 335. ISBN 978-1-58488-090-5.
↑ ليو، تشينغهاي؛ تشانغ، تشاو (2010-03-01). "وجود حد أعلى لنوعين من الاتصال المقيد" . الرياضيات التطبيقية المنفصلة . 158 (5): 516-521 . doi : 10.1016/j.dam.2009.10.017 .
↑ غروس، جوناثان ل.؛ يلين، جاي (2004). دليل نظرية الرسم البياني . مطبعة سي آر سي . ص 338. ISBN 978-1-58488-090-5.
↑ بالبوينا، كامينو؛ كارمونا، أنجيليس (1 أكتوبر 2001). "حول الاتصال والاتصال الفائق للرسوم البيانية الثنائية الموجهة والرسوم البيانية". آرس كومبيناتوريكا . 61 : 3-22 . CiteSeerX 10.1.1.101.1458 .
↑ جيبونز، أ. (1985). نظرية الرسم البياني الخوارزمية . مطبعة جامعة كامبريدج .
↑ ناغاموتشي، هـ.؛ إيباراكي، ت. (2008). الجوانب الخوارزمية لاتصال الرسم البياني . مطبعة جامعة كامبريدج.
↑ رينغولد، عمر (2008). "الاتصال غير الموجه في فضاء اللوغاريتم". مجلة ACM . 55 (4): 1-24 . doi : 10.1145/1391289.1391291 . S2CID 207168478 .
↑ بروفان، ج. سكوت؛ بول، مايكل أو. (1983). "تعقيد عدّ القطوع وحساب احتمالية اتصال الرسم البياني". مجلة SIAM للحوسبة . 12 (4): 777-788 . doi : 10.1137/0212053 . MR 0721012 . .
↑ جودسيل، سي.؛ رويل ، جي. (2001). نظرية الرسم البياني الجبرية . سبرينغر فيرلاغ.
↑ باباي، ل. (1996). مجموعات التشاكل الذاتي، التشاكل، إعادة البناء . تقرير فني TR-94-10. جامعة شيكاغو. مؤرشف من الأصل بتاريخ 11-06-2010.الفصل 27 من كتاب "دليل التوافقية" .
↑ بالينسكي، إم إل (1961). "حول بنية الرسم البياني للمجسمات المحدبة في الفضاء ذي البعد $n$ " . مجلة المحيط الهادئ للرياضيات . 11 (2): 431-434 . doi : 10.2140/pjm.1961.11.431 .
^ ديراك، غابرييل أندرو (1960). "في الرسم التجريدي vorhandene vollständige 4-Graphen und ihre Unterteilungen". الرياضيات Nachrichten . 22 ( 1– 2): 61– 85. دوى : 10.1002/mana.19600220107 . السيد 0121311 . .
↑ فلاندري، إيفلين؛ لي، هاو؛ ماركزيك، أنتوني؛ ووزنياك، ماريوس (2007). "تعميم لنظرية ديراك حول الدورات التي تمر عبر $k$ رأسًا في الرسوم البيانية المتصلة $k$ " . الرياضيات المتقطعة . 307 ( 7-8 ): 878-884 . doi : 10.1016/j.disc.2005.11.052 . MR 2297171 . .

[diestel-1] 1 2 ديستل، ر. (2005). "نظرية الرسم البياني، الطبعة الإلكترونية" . ص 12.

[2] الفصل 11: الرسوم البيانية الموجهة: مبدأ الازدواجية للرسوم البيانية الموجهة: التعريف

[3] غروس، جوناثان ل.؛ يلين، جاي (2004). دليل نظرية الرسم البياني . مطبعة سي آر سي . ص 335. ISBN 978-1-58488-090-5.

[4] ليو، تشينغهاي؛ تشانغ، تشاو (2010-03-01). "وجود حد أعلى لنوعين من الاتصال المقيد" . الرياضيات التطبيقية المنفصلة . 158 (5): 516-521 . doi : 10.1016/j.dam.2009.10.017 .

[5] غروس، جوناثان ل.؛ يلين، جاي (2004). دليل نظرية الرسم البياني . مطبعة سي آر سي . ص 338. ISBN 978-1-58488-090-5.

[6] بالبوينا، كامينو؛ كارمونا، أنجيليس (1 أكتوبر 2001). "حول الاتصال والاتصال الفائق للرسوم البيانية الثنائية الموجهة والرسوم البيانية". آرس كومبيناتوريكا . 61 : 3-22 . CiteSeerX 10.1.1.101.1458 .

[7] جيبونز، أ. (1985). نظرية الرسم البياني الخوارزمية . مطبعة جامعة كامبريدج .

[8] ناغاموتشي، هـ.؛ إيباراكي، ت. (2008). الجوانب الخوارزمية لاتصال الرسم البياني . مطبعة جامعة كامبريدج.

[9] رينغولد، عمر (2008). "الاتصال غير الموجه في فضاء اللوغاريتم". مجلة ACM . 55 (4): 1-24 . doi : 10.1145/1391289.1391291 . S2CID 207168478 .

[10] بروفان، ج. سكوت؛ بول، مايكل أو. (1983). "تعقيد عدّ القطوع وحساب احتمالية اتصال الرسم البياني". مجلة SIAM للحوسبة . 12 (4): 777-788 . doi : 10.1137/0212053 . MR 0721012 . .

[GandR-11] جودسيل، سي.؛ رويل ، جي. (2001). نظرية الرسم البياني الجبرية . سبرينغر فيرلاغ.

[12] باباي، ل. (1996). مجموعات التشاكل الذاتي، التشاكل، إعادة البناء . تقرير فني TR-94-10. جامعة شيكاغو. مؤرشف من الأصل بتاريخ 11-06-2010.الفصل 27 من كتاب "دليل التوافقية" .

[13] بالينسكي، إم إل (1961). "حول بنية الرسم البياني للمجسمات المحدبة في الفضاء ذي البعد $n$ " . مجلة المحيط الهادئ للرياضيات . 11 (2): 431-434 . doi : 10.2140/pjm.1961.11.431 .

[14] ديراك، غابرييل أندرو (1960). "في الرسم التجريدي vorhandene vollständige 4-Graphen und ihre Unterteilungen". الرياضيات Nachrichten . 22 ( 1– 2): 61– 85. دوى : 10.1002/mana.19600220107 . السيد 0121311 . .

[15] فلاندري، إيفلين؛ لي، هاو؛ ماركزيك، أنتوني؛ ووزنياك، ماريوس (2007). "تعميم لنظرية ديراك حول الدورات التي تمر عبر $k$ رأسًا في الرسوم البيانية المتصلة $k$ " . الرياضيات المتقطعة . 307 ( 7-8 ): 878-884 . doi : 10.1016/j.disc.2005.11.052 . MR 2297171 . .

[ 1 ]

[2]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[

[ 10 ]

[ 11 ]

[ 12 ]

[

[ 14 ]

[ 15 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗