مستخدم:جوليان عويد/ملعب

طريقة حل دارّة اويلر

ما هي دارة اويلر ؟

هي مجموعة نقاط موصولة باضلاع ، وكل ضلع يمتد بين نقطتين ولا يمكن ان يمتد ويمر بثلاث نقاط ،

لكن يمكن ان يمتد بين نقطتين بينهما نقطة أُخرى او ان يكون لنقطتان اكثر من ضلع مشترك ولا يختلف الوضع بين الضلع المستقيم والمنحني ، تجدون مثال على ذلك في الصورة

لدارة اويلر ثلاثة احتمالات :

1- دائرة اويلر :

وهي الابسط بحيث تنص على البدء من نقطة والمرور على كل الاضلاع كل ضلع بالضبط مرة واحدة والعودة الى نفس النقطة

كيف نعرف ان كانت الدارة تحوي دائرة اويلر ؟

الدارة التي فيها كل الدرجات زوجية تحوي دائرة اويلر.

ما هي الدرجات ؟

هي عدد الاضلاع الخارجة من الراس ( النقطة)

خوارزمية لايجاد دائرة اويلر في دارة اويلرية : * الخوارزمية*

(الامثلة مبنية على الدارة اعلاه)

1 - نفحص درجات جميع الرؤوس في الدارة بواسطة ԁ()= x

مثال : ԁ(z)=4

(ملاحظة : في هذا المثال لم تُسمى الرؤوس لذلك وضعت اسم z وايضا في هذا المثال كل النقاط يمكن ان تكون z )

اذا كانت كل الدرجات زوجية ننتقل للخطوة التالية ، وإن لم يكن فهذا يعني بانه لا يمكن ان توجد دائرة اويلر

2- نبدا بعمل دوائر صغيرة :

C₁ = (a, b , c,z,a) .1

الدائرة 1 تبدا وتنتهي بالنقطة a

نقوم بتغطية الاضلاع التي مررنا عليها

نقوم باختيار نقطة من بينها كمثال النقطة b

C₂=(b,x,z,a,b) .2

ونكرر الخطوة حتى نغطي جميع الاضلاع

3. نقوم بجمع جميع الدوائر :

,x,z,a,b,c,z,a)C_E=(a,b

كما هو واضح : بدانا ب C₁ ثم عندما وصلنا لنقطة البداية ل C₂ تركنا الدائرة الاولى وبدانا بالثانية وهكذا نبدا بالنزول الى ان نصل لآخر دائرة ثم عندما ننهيها نبدا

بالصعود الى النقطة التي توقفنا فيها الى ان نصل الى الى الدائرة الاولى وننهي بها وبهذا نكون قد وجدنا الدائرة . المصدر : جامعة التخنيون - حيفا

ملاحظة : الحالتين الاخريتين ستضافان فيما بعد