فهم دائرة أولوريان في نظرية غراف

ودائرة من الـ(إيوليريان) هي مشية مغلقة تقطع كل حافة من الرسوم البيانية مرة واحدة وتعود إلى منعطف البداية، وينشأ هذا المفهوم من الجسور السبع الشهيرة لمشكلة (كونيسبرج) التي طرحها ليونهارد إيولر في عام 1736، وقد أثبت Euler أن هذه الدائرة لا توجد إلا إذا كان كل منحرف في الرسم البياني له درجة من التفاؤل، وأن الرسم البياني يظل مترابطا (تبين).

To state it formally: let G = (]V, ]E) is an undirected graph. An Eulerian circuit exists if and only if every vertex

ما هو ألغوريثم هيرهولزر؟

(هيروليس) هو أسلوب فعال في بناء دائرة (إيوليزر) عند استيفاء الشروط اللازمة، وهو يبني الدائرة من خلال إيجاد سلسلة من الدورات ودمجها، ويبدأ الخوارزمية في وقت متسلسل ([FL])

المفاهيم الرئيسية

  • Cycle detection:] Starting from a vertex, follow unused edges until returning to the starting vertex.
  • Merging cycles:] When a vertex on the current circuit still has unused edges, a new cycle is formed from that vertex and inserted into the circuit.
  • Edge removal:] As edges are used, they are marked or removed to avoid revisiting them.

وصف تفصيلي لـ " هيرهولزر "

ويمكن تنفيذ الخوارزمية بصورة استجمامية أو متكررة، والفكرة الأساسية هي بناء دائرة من خلال توسيع نطاق الدوائر الفرعية بصورة متكررة، وفيما يلي تفاصيلها.

الخطوة 1: اختيار بداية فيرتكس

(أ) أن تختار أي منحرف منحرف على الأقل حافة واحدة، وبما أن الرسم البياني متصل، وكل الدرجات حتى، فإن أي منحرف سيعمل، وعادة ما يبدأ الخوارزمية في المنعطف [(FLT:0]]v.

الخطوة 2: تعقب مركبة

من التفريغ الحالي، اتبع أي حافة غير مستخدمة إلى جار، تابع السير على طول الحواف غير المستخدمة، ووسم كل حافة كما استخدمت، حتى تعود إلى منعطف البداية، وهذا ينتج دورة C وإذا كانت الدورة تحتوي على جميع حواف الرسم البياني، فإن الخوارزمية تنتهي - لدينا دائرة إيلوريان.

الخطوة 3: العثور على الفيريتش مع العشب غير المستعمل

Scan the current circuit for any vertex u that still has incident unused edges. If none exist, the algorithm is complete. otherwise, let ]u be such a vertex.

الخطوة 4: بناء دورة جديدة من u]

(د) أن يكرر عملية تقصي الدورة بين الأطراف غير المستخدمة، وينشئ هذا دورة جديدة u تبدأ وتنتهي في u .

الخطوة 5: دمج المركبة الجديدة في الدائرة الرئيسية

Insert C] into the main circuit at the position of u. The resulting walk is still a circuit (مغلقة) and covers all edges visited so far. Return to Step 3.

ونظرا لأن كل منحرف منحرف منحرف منحرف، فإن العملية لا تلتصق أبدا: فعندما تدخل منحرفا، سيكون هناك دائما حافة غير مستخدمة للمغادرة، إلى أن تصبح درجة اللافيكس صفرا، ويضمن الخوارزمية أن المشي النهائي يشمل كل حافة بالضبط مرة واحدة.

مثال: بناء دائرة إيوليريان

)أ( أن تنظر في رسم بياني غير موجه مع الفقرات ألف وباء وجيم ودال وهاء: ألف وجيم ودال وجيم ودال ودال ودال ودال ودال ودال )وهذه علامة صغيرة تكون فيها كل منحرفين )ألف( = ٣ درجة مئوية( ودرجة )ب( و ٤ درجة مئوية( و ٤ درجة مئوية و ٣ درجة مئوية( و ٢ )د( و ٣ درجة مئوية( و ٢ )هاء((.

تشغيل Algorithm Hierholzer ' s Algorithm:

  • ١ - حواف المتابعة: ١ - ٢ )استخدام( ٢ - ٣ )استخدام( الآن عند ٣: الحافة غير المستخدمة ٣ - ٤ )استخدام( و ٤ - ٥ )استخدام( و ٥ - ٣ )استخدام( - العودة الى ٣، ولكن نقطة الانطلاق الأولى لم نعد بعد، وفي الواقع، يتعين أن تشكل الخوارزمية دورة تعود الى نقطة البداية ١ - ١.
  • Scan C1: vertex 3 has unused edges. Start new cycle at 3: 34, 4‐5, 5 — Cycle C2 = 3 —4- -5 -
  • دمج C2 إلى C1 في اللافقار 3: الناتج عن الدائرة: 1 -2-34 - - -5 -1 - جميع الحواف المستخدمة، الدائرة هي Eulerian.

ويوضح هذا المثال اناقة الخوارزمية: إذ يتم اكتشاف الدورات وجمعها دون هوادة.

اعتبارات التعقيد والتنفيذ

The Hierholzer’s Algorithm runs in O](]V + E) + عند استخدام قائمة الإجحاف وهياكل البيانات الفعالة لإزالة الحواف (e.g.

وفيما يتعلق بالرسوم البيانية الموجهة، فإن النهج نفسه يعمل على أن يكون الرسم البياني هو " إيوليريان " )أي أن درجة المكافآت تساوي درجة خارجية في كل منحرف(.

مقارنة مع الغوريثم الفلوري

Another well —known algorithm for finding Eulerian circuits is Fleury’s Algorithm, which works by traversing edges while ensuring that the remaining graph stays connected (i.e., avoiding bridges). Fleury’s algorithm runs in O([Flar check]

طلبات الإغوريديثم في هيرهولزر

القدرة على إيجاد دائرة (إيوليريان) بكفاءة لديها العديد من الاستخدامات الحقيقية للعالم

مشكلة البريد الصيني

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

الشبكة: تصميم المركبات

وتستخدم دوائر الإيلوريان في تصميم طرق فعالة لأجهزة مسح الشوارع وجمع القمامة ونقل عبوات الشبكة حيث يجب أن تُغَطَّر كل وصلة على وجه الدقة مرة واحدة، ويساعد الخوارزمية على تقليل السفر الزائد إلى أدنى حد.

جمعية تجزؤ الحمض النووي

وفي البيولوجيا الحسابية، يعتمد نهج الرسوم البيانية في تجمع الجينوم على إيجاد مسارات أو دوائر إيوليريان من خلال رسومات الكميمير، كما أن خوارزمية هيرهولزر هي عنصر أساسي من العديد من التجمعات، مما يتيح إعادة بناء التسلسلات المتقاربة من القراءات القصيرة.

التكوين التكويني والزيائي

وتستخدم آثار البوليريان في توليد الميوز وفي بعض الخوارزميات التي يجب رسمها دون رفع القلم، وتوفر الخوارزمية بناء أمثل.

اختبار الدائرة المتكاملة

وفي تصميم كبير جداً للتكامل بين القطاعات، يمكن أن يُنظَّم اختبار جميع الاتصالات على أنها مشكلة في الدائرة الإيوليانية، مما يقلل من حركة المُختبرين.

المزيد من القراءة والموارد الخارجية

ولزيادة فهمكم لدوائر إيوليريان وخوارزمية هيرهولزر، يوصى بالموارد التالية:

خاتمة

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