في نظرية الحوسبة والرسم البياني ، تعتبر بنية الاتصال الديناميكي هي بنية بيانات تحافظ ديناميكيًا على المعلومات حول المكونات المتصلة للرسم البياني. أي أنها تبقي على الاتصال بين البيانات بالرغم من عمليات الحذف و الإضافة التي نقوم بها للعناصر و المكونات.
مثلا ليكن لدينا مجموعة رؤوس الرسم البياني V الثابتة ، و مجموعة الأضلاع التي تربط الرؤوس E القابلة للتغيير
. الحالات الثلاث مرتبة حسب الصعوبة هي:
تتم إضافة الحواف إلى الرسم البياني فقط (يمكن أن يسمى هذا الاتصال الديناميكي المتزايد)
يتم حذف الحواف فقط من الرسم البياني (يمكن أن يسمى هذا الاتصال الديناميكي التنازلي)
يمكن إضافة الحواف أو حذفها معا (يمكن أن يسمى هذا الاتصال الديناميكي بالكامل)
بعد كل إضافة / حذف للحافة ، يجب أن تتكيف بنية الاتصال الديناميكي مع نفسها بحيث يمكنها تقديم إجابات سريعة على استفسارات النموذج "هل هناك مسار بين x و y؟"(تكافئ : "هل تنتمي الرؤوس x و y إلى نفس المكون المتصل ؟").
مثلا في الصورة السابقة:
إضافة ضلع بين الرأسين 0 و 3 سيجعل البيان متصل ومن مكونة واحدة - 1 component
حذف الضلع بين الرأسين 3 و 4 سيجعل البيان مكون من 3 أجزاء - 3 components
يمكننا تبسطها بالعالم الطبيعي:
كشق طريق بين مدينتين (إضافة ضلع)
قطع طريق بين مدينتين (حذف ضلع)
يوجد العديد من الخوارزميات التي تعطينا معلومات عن البيان (أمثلة لخوارزميات بسيطة DFS - BFS ) (خوارزميات بناء البيان Prime - Kruskal ) وغيرهم ..
مراجع مفيدة
بنى معطيات الهرمية:
خوارزميات الرسوم البيانية:
مرجع أكاديمية حسوب الشامل للخوارزميات:
التعليقات