اتصال ديناميكي

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 13 صور
الموسوعة الحرة

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

مجموعة رؤوس الرسم البياني V ثابتة، لكن مجموعة الحواف E قابلة للتغيير. الحالات الثلاث، مرتبة حسب صعوبتها، هي:

  • يتم إضافة الحواف فقط إلى الرسم البياني (ويمكن تسمية هذا بالاتصال التزايدي )؛
  • يتم حذف الحواف فقط من الرسم البياني (يمكن تسمية هذا بالاتصال التناقصي )؛
  • يمكن إضافة الحواف أو حذفها (وهذا ما يمكن تسميته بالاتصال الديناميكي الكامل ).

بعد كل إضافة/حذف لحافة، يجب أن يتكيف هيكل الاتصال الديناميكي بحيث يمكنه تقديم إجابات سريعة على الاستفسارات من الشكل "هل يوجد مسار بين x و y ؟" (بصورة مكافئة: "هل تنتمي الرؤوس x و y إلى نفس المكون المتصل؟").

الاتصال التدريجي

إذا كان بالإمكان إضافة الحواف فقط، فيمكن حل مشكلة الاتصال الديناميكي باستخدام بنية بيانات المجموعات المنفصلة . تمثل كل مجموعة مكونًا متصلًا؛ يوجد مسار بين x و y إذا وفقط إذا كانا ينتميان إلى نفس المجموعة. الوقت المستهلك لكل عملية هوΘ(α(ن)){\displaystyle \Theta (\alpha (n))}حيث n هو عدد الرؤوس و α هي دالة أكرمان العكسية . [ 1 ] [ 2 ]

الاتصال المتناقص

تم حل الحالة التي لا يمكن فيها حذف الحواف إلا بواسطة شيمون إيفن ويوسي شيلواخ . [ 3 ]

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

الرسوم البيانية غير الدورية (الغابات)

عند حذف الحافة u - v في غابة ، يتم تقسيم الشجرة التي تحتوي على تلك الحافة إلى شجرتين: إحداهما تحتوي على u والأخرى تحتوي على v . يتم تحديث الجدول بالطريقة التالية.

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

بما أننا نعيد تسمية المكون الفرعي الأصغر دائمًا، فإن الوقت المستهلك لعملية الحذف هويا(سجل⁡(ن)){\displaystyle O(\log(n))}.

الرسوم البيانية العامة

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

العملية أ
يشبه هذا حالة الرسم البياني غير الدوري: حيث توجد عمليتان فرعيتان تقومان بالمسح من طرفي الحافة المحذوفة. إذا انتهت إحدى العمليتين الفرعيتين قبل الوصول إلى الطرف الآخر، فهذا يعني أن المكون قد انقسم إلى مكونين فرعيين، ويتم تحديث اسم المكون الفرعي الأصغر، كما في السابق. وبالتالي، فإن الوقت المستهلك لعملية الحذف هو نفسه مرة أخرى.يا(سجل⁡(ن)){\displaystyle O(\log(n))}.
العملية ب
يستخدم هذا الأسلوب بنية بحث العرض أولاً (BFS) ، والتي تُهيأ كما يلي: يُختار رأس r ، ويبدأ البحث منه. الرأس الوحيد في المستوى 0 هو r . جميع الرؤوس التي تبعد مسافة i عن الجذر تقع في المستوى i . إذا لم تكن الشبكة G متصلة، يبدأ مسح جديد من رأس غير ممسوح v ، ويُوضع v في المستوى 1، ويُربط v بالجذر r بحافة اصطناعية ؛ جميع الرؤوس التي تبعد مسافة i عن v تقع الآن في المستوى i + 1، وهكذا. تُستخدم الحواف الاصطناعية للحفاظ على جميع المكونات المتصلة في بنية بحث العرض أولاً واحدة، وتُستخدم لهذا الغرض فقط. من الواضح أن الحواف الاصطناعية تُستخدم فقط في العملية B.

يتمتع هذا الهيكل بالخصائص التالية. يمتلك الرأس v في المستوى i ، حيث i > 0، ثلاثة أنواع فقط من الحواف: حواف خلفية تربطه بالمستوى i - 1 (يوجد على الأقل حافة واحدة من هذا النوع، وقد تكون اصطناعية)، وحواف محلية تربطه بحواف أخرى في المستوى i (يوجد صفر أو أكثر من هذه الحواف)، وحواف أمامية تربطه بحواف في المستوى i + 1 (يوجد صفر أو أكثر من هذه الحواف). لذا، لكل رأس v ، نحتفظ بثلاث مجموعات من الحواف (خلفية، محلية، وأمامية).

عند حذف الحافة u - v ، هناك خياران: إما أن يكون u و v في نفس المستوى، أو أنهما في مستويات يختلف رقمها بمقدار 1.

الحالة 1
يقع كل من u و v على نفس المستوى. في هذه الحالة، لا يمكن لحذف الحافة تغيير المكونات. تُحذف الحافة ببساطة من مجموعات الحواف المحلية لـ u و v ، ويتوقف البرنامج B (وبالتالي يتوقف البرنامج A أيضًا). يبقى هيكل خوارزمية البحث في العرض أولًا (BFS) صالحًا.
الحالة الثانية
u و v على مستويين مختلفين. دون الإخلال بعمومية المسألة ، نفترض أن u في المستوى i − 1 و v في المستوى i ؛ وبالتالي يجب إزالة الحافة من forward( u ) ومن backward( v ).
الحالة 2.1
إذا لم يكن المسار العكسي الجديد ( v ) فارغًا، فإن المكونات لم تتغير: هناك حواف أخرى تربط v بالمسار العكسي. تتوقف العملية B (وتتوقف العملية A أيضًا).
الحالة 2.2
إذا كانت قائمة الرؤوس الجديدة (الرأس v ) فارغة، فإن الرأس v لم يعد متصلاً بالمستوى i - 1، وبالتالي فإن المسافة بينه وبين الجذر لم تعد i ؛ بل يجب أن تكون على الأقل i + 1. بالإضافة إلى ذلك، قد توجد رؤوس أخرى متصلة بالرأس v ، تزداد المسافة بينها وبين الجذر نتيجةً للحذف. لحساب المسافات المُحدَّثة، نستخدم قائمة انتظار Q، التي تحتوي في البداية على الرأس v فقط .

طالما أن Q ليست فارغة:

  1. w  := dequeue(Q)
  2. قم بإزالة w من مستواه (على سبيل المثال، j )، وضعه في المستوى التالي ( j + 1).
  3. تحديث معلومات الجيران المحليين:
    • لكل حافة w − x في local( w )، قم بإزالتها من local( x ) وضعها في forward( x ).
    • backward( w )  := local( w )
  4. تحديث الجيران الأماميين:
    • لكل حافة w - x في forward( w )، قم بإزالتها من backward( x ) وضعها في local( x )؛ إذا كانت backward( x ) الجديدة فارغة، فقم بإضافة x إلى قائمة الانتظار Q.
    • local( w )  := forward( w )
    • forward( w )  := مجموعة فارغة
  5. إذا كانت قائمة الانتظار الجديدة ( w ) فارغة، فأضف w مرة أخرى إلى قائمة الانتظار Q.

إذا لم يؤدِ حذف الحافة إلى كسر أي مكون، وكنا في الحالة 2.2، فسيتوقف الإجراء في النهاية. في هذه الحالة، من السهل ملاحظة أن بنية البحث في العرض أولاً (BFS) محفوظة بشكل صحيح. أما إذا أدى حذفها إلى كسر أحد المكونات، فلن يتوقف الإجراء تلقائيًا. ومع ذلك، ستتوقف العملية A، التي تتعرف على الكسر، وستتوقف كلتا العمليتين. في هذه الحالة، يتم تجاهل جميع التغييرات التي أُجريت على بنية BFS، ونعود إلى بنية BFS التي كانت لدينا قبل الحذف مباشرةً، باستثناء أن الحافة المحذوفة قد استُبدلت الآن بحافة اصطناعية. من الواضح أن v في هذه الحالة هو الآن جذر شجرة تتضمن المكون الجديد، وربما مكونات إضافية، من خلال بعض الحواف الاصطناعية الأخرى. كذلك، لا توجد حواف تربط أحفاد v بأي رؤوس ليست من أحفاد v ، باستثناء الحافة الاصطناعية .u-v{\displaystyle uv}[ 4 ]​​

كلما تمت معالجة حافة في الإجراء، ينخفض ​​أحد طرفيها بمقدار مستوى واحد. وبما أن أدنى مستوى يمكن أن يصل إليه رأس في عمليات التشغيل التي تنتهي بواسطة العملية B هو|V|-1{\displaystyle |V|-1}، وتكون تكلفة كل حافة محدودة بـ2|V|{\displaystyle 2|V|}وبالتالي، فإن الوقت المستهلك لكل عملية حذف هويا(ن){\displaystyle O(n)}.

اتصال ديناميكي بالكامل

الرسوم البيانية غير الدورية (الغابات)

يمكن تمثيل الغابة باستخدام مجموعة من أشجار القطع المتصلة أو أشجار جولات أويلر . عندئذٍ، يمكن حل مشكلة الاتصال الديناميكي بسهولة، حيث أنه لكل عقدتين x وy، تكون x متصلة بـ y إذا وفقط إذاFأناندRooت(x)=FأناندRooت(y){\displaystyle \mathrm {FindRoot} (x)=\mathrm {FindRoot} (y)}. وقت التحديث المستهلك ووقت الاستعلام كلاهما O(log( n )).

الرسوم البيانية العامة

يمكن تمثيل أي رسم بياني عام بواسطة غابته الممتدة - وهي غابة تحتوي على شجرة لكل مكون متصل من الرسم البياني. نسمي هذه الغابة الممتدة F. ويمكن تمثيل F نفسها بواسطة غابة من أشجار جولات أويلر .

تُنفَّذ عمليتا الاستعلام والإدراج باستخدام العمليات المناظرة على أشجار ET التي تُمثِّل F. أما العملية الأكثر تعقيدًا فهي الحذف، وتحديدًا حذف حافة موجودة في إحدى الأشجار الممتدة لـ F. يؤدي هذا إلى تقسيم الشجرة الممتدة إلى شجرتين، ولكن من المحتمل وجود حافة أخرى تربط بينهما. يكمن التحدي في إيجاد حافة بديلة بسرعة، إن وُجدت. يتطلب هذا بنية بيانات أكثر تعقيدًا. يرد وصف بعض هذه البنى أدناه.

هيكل المستوى

يُخصص لكل حافة في الرسم البياني مستوى . ليكن L = log n . يُهيأ مستوى كل حافة تُضاف إلى الرسم البياني إلى L ، وقد يتناقص باتجاه الصفر أثناء عمليات الحذف.

لكل قيمة i بين 0 و L ، نُعرّف Gi على أنها الرسم البياني الفرعي الذي يتكون من الحواف التي تقع عند المستوى i أو أقل، و F <sub>i</sub> على أنها غابة ممتدة من Gi . تُسمى غابتنا F السابقة الآن F<sub> L</sub> . سنحتفظ بتسلسل تنازلي للغابات F <sub> L </sub> ⊇ ... ⊇ F <sub>0</sub> . [ 5 ] [ 6 ]

العمليات

تستخدم عمليات الاستعلام والإدراج فقط أكبر غابة F L. يتم الرجوع إلى الرسوم البيانية الفرعية الأصغر فقط أثناء عملية الحذف، وعلى وجه الخصوص، حذف حافة موجودة في إحدى الأشجار الممتدة لـ F L.

عند حذف حافة مثل e = x − y ، تُزال أولاً من F L ومن جميع الغابات الممتدة الأصغر التي تنتمي إليها، أي من كل F i حيث i ≥ level( e ). ثم نبحث عن حافة بديلة.

ابدأ بأصغر غابة ممتدة تحتوي على العقدة e ، وهي F <sub>i </sub> حيث i = level( e ). تنتمي الحافة e إلى شجرة معينة T ⊆ F <sub> i</sub> . بعد حذف e ، تُقسّم الشجرة T إلى شجرتين أصغر: T <sub>x</sub> التي تحتوي على العقدة x، و T<sub> y</sub> التي تحتوي على العقدة y . تُعتبر حافة T <sub>i</sub> حافة استبدال، إذا وفقط إذا كانت تربط عقدة في T<sub> x </sub> بعقدة في T<sub> y</sub> . لنفترض دون فقدان أن T<sub> x</sub> هي الشجرة الأصغر (أي تحتوي على نصف عدد عقد T<sub>i</sub> على الأكثر ؛ يمكننا تحديد حجم كل شجرة فرعية من خلال إضافة تعليق إلى أشجار أويلر).

نقوم أولاً بتقليل مستوى كل حافة من T x بمقدار 1. ثم نمر على جميع الحواف ε ذات المستوى i والتي تحتوي على عقدة واحدة على الأقل في T x :

  • إذا كانت العقدة الأخرى لـ ε موجودة في T y ، فسيتم العثور على حافة بديلة! أضف هذه الحافة إلى F i وإلى جميع الغابات التي تحتويها حتى F L ، وانتهى الأمر. يتم تثبيت الغابات الممتدة. لاحظ أنه من أجل تغطية تكلفة هذا البحث، نقوم بتقليل مستوى الحواف التي تمت زيارتها أثناء البحث.
  • إذا كانت العقدة الأخرى لـ ε موجودة في T x ، فإن هذه ليست حافة استبدال، ولـ "معاقبتها" على إضاعة وقتنا، نقوم بتقليل مستواها بمقدار 1.
تحليل

سينخفض ​​مستوى كل حافة بمقدار لوغاريتم n مرة على الأكثر. لماذا؟ لأنه مع كل انخفاض، تنتقل الحافة إلى شجرة لا يتجاوز حجمها نصف حجم شجرتها في المستوى السابق. لذا، في كل مستوى i ، يكون عدد العقد في كل مكون متصل 2i على الأكثر . وبالتالي، يكون مستوى الحافة دائمًا صفرًا على الأقل.

كل حافة يتم تقليل مستواها، تأخذيا(إل جي⁡ن){\displaystyle O(\lg n)}يستغرق البحث (باستخدام عمليات شجرة ET) وقتًا إجماليًا. إجمالاً، يستغرق كل حافة مُدرجة وقتًا أطول.يا(إل جي2⁡ن){\displaystyle O(\lg ^{2}n)}الوقت اللازم لحذفها، وبالتالي فإن الوقت المستهلك للحذف هو يا(إل جي2⁡ن){\displaystyle O(\lg ^{2}n)}الجزء المتبقي من عملية الحذف يأخذ أيضًايا(إل جي2⁡ن){\displaystyle O(\lg ^{2}n)}الوقت، حيث يتعين علينا حذف الحافة من على الأكثريا(إل جي⁡ن){\displaystyle O(\lg n)}المستويات، والحذف من كل مستوى يستغرقيا(إل جي⁡ن){\displaystyle O(\lg n)}(باستخدام عمليات ET مرة أخرى).

إجمالاً، يبلغ الوقت المستهلك لكل تحديثيا(إل جي2⁡ن){\displaystyle O(\lg ^{2}n)}يمكن تحسين وقت كل استعلام إلىيا(إل جي⁡ن/إل جي⁡إل جي⁡ن){\displaystyle O(\lg n/\lg \lg n)}.

مع ذلك، قد يكون أسوأ وقت لكل تحديث هويا(ن){\displaystyle O(n)}لقد كان السؤال عما إذا كان من الممكن تحسين أسوأ وقت ممكن سؤالاً مفتوحاً، إلى أن تم حله بالإيجاب من خلال بنية Cutset.

هيكل Cutset

بفرض وجود رسم بياني G(V, E) ومجموعة جزئية T⊆V، يُعرَّف cutset(T) على أنه مجموعة الحواف التي تربط T بـ V\T. بنية cutset هي بنية بيانات، دون الحاجة إلى تخزين الرسم البياني بأكمله في الذاكرة، يمكنها العثور بسرعة على حافة في cutset، إن وُجدت. [ 7 ]

ابدأ بإعطاء رقم لكل رأس. لنفترض أن هناك n رأسًا؛ عندها يمكن تمثيل كل رأس برقم مكون من log( n ) بت. بعد ذلك، أعطِ رقمًا لكل حافة، وهو عبارة عن سلسلة من أرقام رؤوسها - رقم مكون من 2 log( n ) بت.

لكل رأس v ، احسب واحتفظ بـ xor( v )، وهو xor لأعداد جميع الحواف المجاورة له.

لكل مجموعة جزئية T⊆V، يمكن حساب xor(T) = عملية XOR لقيم جميع رؤوس T. لنفترض وجود حافة e = u − v ، وهي حافة داخلية في T (أي أن u و v تنتميان إلى T). يُدرج العدد e مرتين في xor(T) - مرة مع u ومرة ​​مع v . بما أن عملية XOR لأي عدد مع نفسه تساوي صفرًا، فإن e لا تؤثر على xor(T). بالتالي، فإن xor(T) هي في الواقع عملية XOR لجميع الحواف في cutset(T). هناك عدة خيارات:

  • إذا كانت xor(T)=0، فيمكننا الرد بثقة أن cutset(T) فارغة.
  • إذا كان xor(T) هو عدد حافة حقيقية e ، فمن المحتمل أن تكون e هي الحافة الوحيدة في cutset(T)، ويمكننا إرجاع e . كما يمكننا قراءة طرفي e من عددها بتقسيمها إلى lg( n ) بتًا من اليسار وlg( n ) بتًا من اليمين.
  • الخيار الثالث هو أن xor(T) عدد غير صفري لا يُمثل حافة حقيقية. لا يحدث هذا إلا إذا كانت هناك حافتان أو أكثر في cutset(T)، لأنه في هذه الحالة يكون xor(T) هو عملية XOR لعدة أعداد من الحواف. في هذه الحالة، نُبلغ عن "فشل"، لأننا نعلم بوجود حواف في cutset ولكن لا يمكننا تحديد أي حافة منفردة. [ 8 ]

هدفنا الآن هو التعامل مع هذا الخيار الثالث.

أولًا، أنشئ سلسلة من مستويات lg( n ) لهياكل cutset، يحتوي كل منها على نصف الحواف تقريبًا من المستوى الأعلى (أي، لكل مستوى، اختر كل حافة من المستوى الأعلى باحتمالية 1/2). إذا أعادت دالة xor(T) في المستوى الأول قيمة غير صالحة، مما يعني أن cutset(T) تحتوي على حافتين أو أكثر، فهناك احتمال أن تُعيد دالة xor(T) في المستوى التالي، الذي يحتوي على عدد أقل من الحواف، قيمة صالحة لأن cutset(T) ستحتوي على حافة واحدة. إذا استمرت دالة xor(T) في إرجاع قيمة غير صالحة، فانتقل إلى المستوى التالي، وهكذا. بما أن عدد الحواف يتناقص، فهناك حالتان:

  • الحالة الجيدة هي أننا نجد في النهاية مستوى يحتوي فيه cutset(T) على حافة واحدة؛ ثم نعيد تلك الحافة وننهي الأمر.
  • الحالة السيئة هي أننا نجد في النهاية مستوى لا يحتوي فيه cutset(T) على أي حواف؛ ثم نبلغ عن "فشل"، لأننا نعلم أن هناك حواف في cutset ولكن لا يمكننا تحديد أي حافة واحدة.

من الممكن إثبات أن احتمال النجاح لا يقل عن 1/9.

بعد ذلك، أنشئ مجموعة من C lg( n ) نسخة مستقلة من بنية المستويات، حيث C ثابت. في كل نسخة، قم بتقليص عشوائي مستقل للحواف من مستوى إلى آخر. جرّب كل استعلام على كل نسخة حتى تنجح إحداها. احتمال فشل جميع النسخ هو على الأكثر:

(1-1/9)جإل جي⁡ن=2-0.17جإل جي⁡ن=ن-0.17ج{\displaystyle (1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}}

باختيار C المناسب ، يمكننا جعل احتمال الفشل قريبًا جدًا من الصفر.

العمليات

يمكننا إضافة بنية مجموعة القطع إلى بنية الاتصال الديناميكية.

تتم عمليات الإدراج والحذف على بنية مجموعة القطع بنفس الطريقة تمامًا: يتم إدخال الحافة المدرجة/المحذوفة في كلا طرفيها باستخدام عملية XOR.

عند حذف حافة من الغابة الممتدة المستخدمة في بنية الاتصال الديناميكي، يتم استخدام بنية مجموعة القطع للعثور على حافة بديلة.

تحليل

لا تتطلب بنية مجموعة القطع الواحدة سوى O ( n log n ) من الذاكرة - أي رقم واحد فقط، مكون من 2 log n بت، لكل رأس من الرؤوس n . لسنا مضطرين للاحتفاظ بالحواف نفسها. بالنسبة للرسوم البيانية الكثيفة، يُعد هذا الخيار أقل تكلفة بكثير من الاحتفاظ بالرسم البياني بأكمله في الذاكرة.

علينا الاحتفاظ بـ lg( n ) نسخة، تحتوي كل منها على lg( n ) مستوى. وبالتالي، فإن إجمالي متطلبات الذاكرة هويا(نإل جي3⁡ن){\displaystyle O(n\lg ^{3}n)}⁠ .

يبلغ زمن الاستعلام O (polylog( n )) في أسوأ الحالات. وهذا يختلف عن بنية المستوى ، حيث يكون زمن الاستعلام O (polylog( n )) بعد استهلاكه، ولكن زمن أسوأ الحالات هو O ( n ).

اتصال ديناميكي دون اتصال بالإنترنت

إذا كان ترتيب حذف الحواف معروفًا مسبقًا، فيمكننا حل مشكلة الاتصال الديناميكي في الوقت المناسب.يا(سجل⁡ن){\displaystyle O(\log n)}لكل استعلام. إذا استطعنا الحفاظ على غابة ممتدة قصوى حيث تُرتَّب الحواف حسب وقت حذفها، فإننا نعلم أنه عند حذف حافة ما من الغابة، لا توجد حافة بديلة لها. فلو وُجدت حافة تربط نفس المكونين اللذين تربطهما الحافة المحذوفة، لكانت هذه الحافة الأخرى جزءًا من الغابة الممتدة القصوى بدلًا من الحافة المحذوفة. وهذا يجعل عملية الحذف بسيطة: يكفي أن نقسم الشجرة إلى جزئيها إذا كانت الحافة المراد حذفها جزءًا من غابتنا، أو نتجاهل العملية في غير ذلك.

إضافة حافة عملية أكثر تعقيدًا بعض الشيء. إذا أضفنا حافة e من u إلى v، فإذا لم تكن u وv متصلتين، فستكون هذه الحافة جزءًا من الغابة الممتدة القصوى. أما إذا كانتا متصلتين، فنريد إضافة u → v إلى غابتنا إذا كان ذلك سيُحسّن من امتدادها الأقصى. وللقيام بذلك، نحتاج إلى التحقق سريعًا من الحافة التي تستغرق أقصر وقت إزالة على المسار من u إلى v. إذا كان وقت إزالة هذه الحافة يأتي بعد وقت إزالة e، فلن تُحسّن e من امتداد الغابة القصوى. وإلا، فيجب حذف الحافة الأخرى واستبدالها بـ e.

يتطلب هذا منا القيام بالعمليات التالية: إضافة حافة، وقطع حافة، والاستعلام عن الحافة الدنيا على مسار يمكن القيام به بسهولة تامة باستخدام شجرة قطع الروابط في log(n) لكل عملية.

انظر أيضاً

مراجع

  1. ↑ تارجان، روبرت إندري (1975). "كفاءة خوارزمية اتحاد مجموعات جيدة ولكنها غير خطية". مجلة ACM . 22 (2): 215-225 . CiteSeerX 10.1.1.399.6704 . doi : 10.1145/321879.321884 . S2CID 11105749 .  
  2. ↑ تارجان، روبرت إندري (1979). "فئة من الخوارزميات التي تتطلب وقتًا غير خطي للحفاظ على مجموعات منفصلة" . مجلة علوم الحاسوب والنظم . 18 (2): 110-127 . doi : 10.1016/0022-0000(79)90042-4 .
  3. ↑ شيلواخ، ي.؛ إيفن، س. (1981). "مسألة حذف الحواف عبر الإنترنت". مجلة ACM . 28 : 1-4 . doi : 10.1145/322234.322235 . S2CID 207746822 . 
  4. ↑ إحدى طرق استعادة البنية السابقة لحذف العنصر e دون الحاجة إلى نسخ البنية بأكملها هي الاحتفاظ بجميع التغييرات التي طرأت على بنية البحث في العرض أولاً (BFS) منذ حذف العنصر e في مكدس، ثم التراجع عنها واحدة تلو الأخرى. بهذه الطريقة، لا يتضاعف وقت المعالجة إلا بمقدار ثابت.
  5. ↑ هولم، ج.؛ دي ليشتنبرغ، ك.؛ ثورب، م. (2001). "خوارزميات حتمية متعددة اللوغاريتمات ديناميكية بالكامل للاتصال، والشجرة الممتدة الدنيا، والحافة الثنائية، والاتصال الثنائي". مجلة ACM . 48 (4): 723. doi : 10.1145/502090.502095 . S2CID 7273552 . 
  6. ↑ مشاكل الرسوم البيانية الديناميكية - في محاضرات هياكل البيانات المتقدمة. الأستاذ إريك ديمين؛ كاتبة المحاضرة: كاثرين لاي.
  7. ↑ كابرون، بي إم؛ كينغ، في؛ ماونتجوي، بي. (2013). اتصال الرسم البياني الديناميكي في أسوأ حالة زمنية متعددة اللوغاريتمات . وقائع الندوة السنوية الرابعة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة. ص 1131. doi : 10.1137/1.9781611973105.81 . ISBN  978-1-61197-251-1.
  8. ↑ هناك احتمال ضئيل أن ينتج عن عملية XOR لعدة حواف مختلفة رقمٌ يُصادف أنه رقم حافة أخرى. قد يؤدي هذا إلى نتيجة إيجابية خاطئة. لتقليل احتمال حدوث ذلك، يمكننا توسيع نطاق عدد الرؤوس إلى، على سبيل المثال، n ≥ 3 بدلاً من n . عندئذٍ، إذا كان هناك أكثر من حافة واحدة في cutset(T)، فستكون قيمة xor(T) عديمة المعنى تقريبًا، كما ذُكر سابقًا.
  • انظر أيضًا: ثورب، م. (2000). اتصال الرسم البياني الديناميكي الكامل شبه الأمثل . وقائع الندوة السنوية الثانية والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '00. ص 343. doi : 10.1145/335305.335345 . ISBN  1581131844.