مرجع
آخر الزيارات

تقنية رحلة أويلر

687 كلمة•0 مشاهدة•🗒️ منذ 13 يوماً
باختصار: تقنية رحلة أويلر تقنية رحلة أويلر(Euler tour technique (ETT)),سميت على اسم ليونهارت أويلر Leonhard Euler,هي عملية في نظرية البيان (graph theory) لتمثيل الأشجار. تجد هنا «تقنية رحلة أويلر».
المحتويات
  1. تقنية رحلة أويلر
تقنية رحلة أويلر

تقنية رحلة أويلر

أشجار رحلة أويلر:

ومن ناحية أخرى، أنشئ لائحة المجاورة (adjacency list) لكل عقدة (مسماة next) وخريطة من العقد إلى أول الداخلين الى لائحة المجاورة(مسماه first).

من جهة ثانية، الوقت المأخوذ حتى يتم ترتيب n عنصر بالتوازي, فإذا احتوت الشجرة على n عقدة , كما في الاشجار عدد الوصلات يكون اقل بواحد من عدد العقد الكلي.

كذلك، تقنية رحلة أويلر(Euler tour technique (ETT)),سميت على اسم ليونهارت أويلر Leonhard Euler,هي عملية في نظرية البيان (graph theory) لتمثيل الأشجار. الشجرة ممثلة كبيان موجه (directed graph) يحتوي وصلتين موجهتين (directed edge) لكل وصلة في الشجرة, لاحقًا يمكن للشجرة أن تمثل كحلقة أويلرية (Eulerian circuit ) من البيان الموجه, تقنية أويلر تسمح بحساب نظير (parallel computation) فعال لحلول مسائل شائعة في نظرية البيان الخوارزمي (algorithmic graph theory). تم تقديمها لأول مرة من قبل تارجان وفيشكن في 1984(Tarjan and Vishkin).

من جهة ثانية، معطى شجرة غير موجهة ممثلة بمجموعة وصلات, تمثيل تقنية رحلة أويلر يمكن بناؤه بالتوازي كما يلي:

البناء الكلي يأخذ عمل W(n) = (O(sort(n)).

وعلى صعيد آخر، اذا كانت الوصلة السابقة (x,y) بحيث x ≠ u, اذن ابدأ من عقدة مختلفة, و عين first(u)=(u,v).

من جهة ثانية، هينزينغر وكينغ اقترحوا تمثيل شجرة عبر وضع رحلة أويلر الخاصة بها في شجرة بحث ثنائي متوازنة( balanced binary search tree), مرمزة بالمؤشرات في الرحلة. كمثال على ذلك, الشجرة الغير متوازنة في المثال السابق, لديها 7 عقد, سوف تمثل بشجرة بحث ثنائي متوازنة لديها 14 عقدة, واحدة لكل مرة تظهر فيها كل عقدة في الرحلة. يمكننا تمثيل غابة( بيان بدون حلقات) باستعمال مجموعة من أشجار رحلة اويلر- شجرة رحلة أويلر لكل شجرة من الغابة. هذا التمثيل يسمح لنا باجابة سؤال "ما هو جذر العقدة v؟" بسرعة فقط بالانتقال إلى العقدة الأولى في شجرة رحلة أويلر(نظرًا لأن العقد في شجرة رحلة أويلر مرمزة بموقعها في رحلة أويلر، حيث يكون الجذر هي العقدة الأولى والأخيرة في الرحلة). عندما يتم تحديث الغابة الممثلة (مثل ربط شجرتين بشجرة واحدة أو تقسيم شجرة إلى شجرتين)، يمكن تحديث الهيكل المقابل لجولة أويلر في وقت O(log(n)). تتمتع أشجار الوصل/القطع(Link/cut trees) بأداء مشابه. بينما تعتبر أشجار الوصل و القطع جيدة للحفاظ على التجميعات على مسارات الشجرة (مما يجعلها خيارًا جيدًا كهيكل بيانات في خوارزميات تدفق الشبكة)، فإن أشجار رحلة أويلر أفضل في الاحتفاظ بمعلومات التجميع على الأشجار الفرعية.

ومن ناحية أخرى، غير ذلك إذا كانت x = u, ابدأ من نفس العقدة, عين next(x,y)=(u,v).

علاوةً على ذلك، رتب لائحة الوصلات معجميا (lexicographically)( نفترض هنا أن عقد(nodes) الشجرة مرتبة,و أن الجذر (root) هو أول عنصر في هذا الترتيب).

تحديد تحديد أدنى سلفّ/جد مشترك لعقدتين ما.

كذلك، حدد مستوى كل عقدة: قم ب مجموع البادئات على رحلة أويلر, بحيث كل قيمة وصلة تقدم تساوي 1 و قيمة كل وصلة تراجع تساوي -1. عندها تكون قيمة وصلة التقدم (u,v) هي مستوى v.

وعلى صعيد آخر، تصنيف وصلات التراجع والتقدم: قم بترتيب اللائحة على رحلة أويلر و احفظ النتيجة في مصفوفة ثنائية الأبعاد مسماة A ثم (u,v) تكون وصلة التقدم إذا كانت A(u,v) < A(v,u) و وصلة تراجع في حالة العكس.

اللائحة الناتجة succ ستكون حلقية.

ننشئ لائحة متناسقة من الوصلات الموجهة:

ومن جهة أخرى، لكل وصلة غير موجهة {u,v} في الشجرة, أدرج (u,v) و (v,u) في لائحة الوصلات.

الإنشاء:

وفي هذا الصدد، إذا كان لدى الشجرة جذر, يمكننا أن نقسم اللائحة الحلقية succ عند الجذر في تلك الحالة, يمكننا ذكر وصلات التراجع و التقدم: لديك زوج من العقد u,v,,أول ظهور لأي من (u,v) أو (v,u) في شجرة رحلة أويلر يسمى وصلة التقدم, و الظهور الثاني يسمر وصلة التراجع. هذا يرجع الى فكرة انه في المرة الاولى التي يتم فيها المرور عبر هذه الوصلة يزداد البعد عن الجذر, بينما في المرة الثانية هذا البعد يقل.

إضافةً إلى ذلك، إعادة تجذير الشجرة يمكن القيام بها في وقت ثابت هو O(1) من خلال قسم اللائحة الحلقية succ عند الجذر الجديد.

إضافةً إلى ذلك، أنشئ لائحة وصلات (مسماه succ) في ترتيب أويلر تور عبر تعيين مؤشرات succ(u,v) لكل الوصلات (u,v) بالتوازي متبعا القاعدة التالية:

التطبيقات:

وفي هذا السياق، عدد العقد في شجرة جزئية معادة التجذير عند v: افترض أن أب v هو u,: حدد وصلة التقدم (u,v) والتراجع (v,u) , ثم احسب عدد وصلات التقدم بين (v,u) و (u,v) مستعملا المجموع التراكمي.

من جانب آخر، كل المسائل التالية يمكن حلها بتعقيد O(Prefix sum(n)) (الوقت المستغرق لحل مسألة المجموع التراكمي ( prefix sum) بالتوازي من أجل لائحة فيها n عنصر):

المراجع:

الجذور, وصلات التقدم والتراجع:

لكل وصلة (u,v) في اللائحة و قم بالتوازي:

وفي هذا الصدد، مؤشر البحث بالعمق(depth-first search) اولا لعقدة ما: احسب عدد وصلات التقدم من البداية وحتى (u,v) مع تضمينها.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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