مقالات

6.3: دوائر أويلر


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

التعريف: مسار أويلر

مسار ينتقل عبر كل حافة من حواف الرسم البياني المتصل مرة واحدة ومرة ​​واحدة فقط ويبدأ وينتهي عند رؤوس مختلفة

مثال ( PageIndex {1} ): مسار أويلر

مسار أويلر للرسم البياني أعلاه هو F ، A ، B ، C ، F ، E ، C ، D ، E كما هو موضح أدناه.

ينتقل مسار أويلر هذا في كل حافة مرة واحدة ومرة ​​واحدة فقط ويبدأ وينتهي عند رؤوس مختلفة. لا يمكن أن يحتوي هذا الرسم البياني على دائرة أويلر لأنه لا يمكن لمسار أويلر أن يبدأ وينتهي عند نفس الرأس دون عبور حافة واحدة على الأقل أكثر من مرة.

التعريف: حلبة أويلر

مسار أويلر يبدأ وينتهي عند نفس الرأس

مثال ( PageIndex {2} ): حلبة أويلر

دائرة أويلر للرسم البياني أعلاه هي E ، A ، B ، F ، E ، F ، D ، C ، E كما هو موضح أدناه.

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

نظرية أويلر ( PageIndex {1} ): إذا كان للرسم البياني أي رؤوس ذات درجة فردية ، فلا يمكن أن يحتوي على دائرة أويلر.

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

نظرية أويلر ( PageIndex {2} ): إذا كان الرسم البياني يحتوي على أكثر من رأسين من الدرجة الفردية ، فلا يمكن أن يكون له مسار أويلر.

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

نظرية أويلر ( PageIndex {3} ): مجموع درجات جميع رؤوس الرسم البياني يساوي ضعف عدد الأضلاع (وبالتالي يجب أن يكون عددًا زوجيًا).

لذلك ، يجب أن يكون عدد رؤوس الدرجة الفردية زوجيًا.

إيجاد دوائر أويلر

  1. تأكد من أن كل قمة في الشبكة لها درجة متساوية.
  2. ابدأ دائرة أويلر في أي قمة في الشبكة.
  3. عندما تختار الحواف ، لا تستخدم أبدًا حافة هي الاتصال الوحيد بجزء من الشبكة لم تزره بالفعل.
  4. قم بتسمية الحواف بالترتيب الذي تسافر إليه واستمر في ذلك حتى تسافر على طول كل حافة مرة واحدة بالضبط وينتهي بك الأمر عند قمة البداية.

مثال ( PageIndex {3} ): البحث عن دائرة أويلر

يحتوي الرسم البياني الموضح أعلاه على دائرة أويلر لأن كل رأس في الرسم البياني بأكمله هو درجة زوجية. وهكذا ، ابدأ من قمة واحدة ، وانتقل فوق كل رأس مرة واحدة ومرة ​​واحدة فقط ، وانتهي عند نقطة البداية. أحد الأمثلة على دائرة أويلر لهذا الرسم البياني هو A ، E ، A ، B ، C ، B ، E ، C ، D ، E ، F ، D ، F ، A. هذه دائرة تنتقل فوق كل حافة مرة واحدة فقط مرة واحدة ويبدأ وينتهي في نفس المكان. توجد دارات أويلر أخرى لهذا الرسم البياني. هذا مثال واحد فقط.

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


شاهد الفيديو: صيانة القاطع الهوائي air circuit breaker (ديسمبر 2021).