المسار الأويلري

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 14 صور
الموسوعة الحرة
تحتوي الرسوم البيانية المتعددة لكل من جسور كونيغسبرغ وألغاز الغرف الخمس على أكثر من رأسين فرديين (باللون البرتقالي)، وبالتالي فهي ليست أويلرية ومن ثم لا توجد حلول للألغاز.
كل رأس من رؤوس هذا الرسم البياني له درجة زوجية. لذلك، فهو رسم بياني أويلري. وباتباع الحواف بالترتيب الأبجدي نحصل على دائرة/دورة أويلرية.

في نظرية المخططات ، يُعرف المسار الأويلري (أو المسار الأويلري ) بأنه مسار في مخطط محدود يمر بكل حافة مرة واحدة فقط (مع إمكانية إعادة زيارة الرؤوس). وبالمثل، فإن الدائرة الأويلرية أو الدورة الأويلرية هي مسار أويلري يبدأ وينتهي عند نفس الرأس . وقد ناقش ليونارد أويلر هذه المفاهيم لأول مرة أثناء حله لمسألة جسور كونيغسبرغ السبعة الشهيرة عام 1736. ويمكن صياغة المسألة رياضياً على النحو التالي:

بالنظر إلى الرسم البياني في الصورة، هل من الممكن إنشاء مسار (أو دورة ؛ أي مسار يبدأ وينتهي عند نفس الرأس) يزور كل حافة مرة واحدة بالضبط؟

أثبت أويلر أن الشرط الضروري لوجود الدوائر الأويلرية هو أن تكون جميع رؤوس الرسم البياني ذات درجة زوجية ، وذكر دون برهان أن الرسوم البيانية المتصلة التي جميع رؤوسها ذات درجة زوجية تحتوي على دائرة أويلرية. نُشر أول برهان كامل لهذا الادعاء الأخير بعد وفاته عام 1873 على يد كارل هيرهولتزر . [ 1 ] يُعرف هذا باسم نظرية أويلر.

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

يُستخدم مصطلح "الرسم البياني الأويلري" بمعنيين شائعين في نظرية الرسوم البيانية. أحدهما هو رسم بياني يحتوي على دائرة أويلرية، والآخر هو رسم بياني تكون فيه جميع الرؤوس ذات درجة زوجية. ويتطابق هذان التعريفان بالنسبة للرسوم البيانية المتصلة. [ 2 ]

لكي توجد مسارات أويلرية، يجب أن يكون لرأسين أو صفر من الرؤوس درجة فردية ؛ وهذا يعني أن مخطط كونيغسبرغ ليس أويلريًا. إذا لم تكن هناك رؤوس ذات درجة فردية، فإن جميع المسارات الأويلرية عبارة عن دوائر. إذا كان هناك رأسان فقط ذوا درجة فردية، فإن جميع المسارات الأويلرية تبدأ من أحدهما وتنتهي عند الآخر. يُطلق على المخطط الذي يحتوي على مسار أويلري ولكن ليس دائرة أويلرية اسم شبه أويلري .

تعريف

المسار الأويلري ، [ ملاحظة 1 ] أو مسار أويلر ، في الرسم البياني غير الموجه هو مسار يستخدم كل حافة مرة واحدة فقط. إذا وُجد مثل هذا المسار، يُسمى الرسم البياني قابلاً للاجتياز أو شبه أويلري . [ 3 ]

الدورة الأويلرية ، [ ملاحظة 1 ] وتُسمى أيضًا الدائرة الأويلرية أو جولة أويلر ، في الرسم البياني غير الموجه هي دائرة تستخدم كل حافة مرة واحدة فقط. إذا وُجدت مثل هذه الدورة، يُسمى الرسم البياني أويلريًا أو أحادي المسار . [ 4 ] يُستخدم مصطلح "الرسم البياني الأويلري" أحيانًا بمعنى أضعف للدلالة على رسم بياني تكون فيه درجة كل رأس زوجية. بالنسبة للرسوم البيانية المتصلة المحدودة ، يكون التعريفان متكافئين، بينما يكون الرسم البياني غير المتصل أويلريًا بالمعنى الأضعف إذا وفقط إذا كان لكل مكون متصل فيه دورة أويلرية.

بالنسبة للرسوم البيانية الموجهة ، يجب استبدال "path" بـ directed path و "cycle" بـ directed cycle .

إن تعريف وخصائص المسارات والدورات والرسوم البيانية الأويلرية صالحة للرسوم البيانية المتعددة أيضًا.

التوجيه الأويلري للرسم البياني غير الموجه G هو تعيين اتجاه لكل حافة من حواف G بحيث يكون مجموع درجات الدخول والخروج لكل رأس v مساويًا لمجموع درجات الخروج . يوجد هذا التوجيه لأي رسم بياني غير موجه تكون فيه جميع الرؤوس ذات درجة زوجية، ويمكن إيجاده بإنشاء مسار أويلري في كل مكون متصل من G ثم توجيه الحواف وفقًا لهذا المسار. [ 5 ] كل توجيه أويلري لرسم بياني متصل هو توجيه قوي ، وهو توجيه يجعل الرسم البياني الموجه الناتج متصلًا بقوة .

ملكيات

  • تحتوي الرسمة البيانية غير الموجهة على دورة أويلرية إذا وفقط إذا كان لكل رأس درجة زوجية، وجميع رؤوسها ذات الدرجة غير الصفرية تنتمي إلى مكون متصل واحد . [ 6 ]
  • يمكن تحليل الرسم البياني غير الموجه إلى دورات منفصلة الحواف إذا وفقط إذا كانت جميع رؤوسه ذات درجة زوجية. لذا، يحتوي الرسم البياني على دورة أويلرية إذا وفقط إذا كان من الممكن تحليله إلى دورات منفصلة الحواف وكانت رؤوسه ذات الدرجة غير الصفرية تنتمي إلى مكون متصل واحد.
  • يحتوي الرسم البياني غير الموجه على مسار أويلري إذا وفقط إذا كان هناك صفر أو رأسان فقط من الرؤوس ذات الدرجة الفردية، وجميع رؤوسه ذات الدرجة غير الصفرية تنتمي إلى مكون متصل واحد. [ 6 ]
  • يحتوي الرسم البياني الموجه على دورة أويلرية إذا وفقط إذا كان لكل رأس درجة دخول ودرجة خروج متساوية ، وكانت جميع رؤوسه ذات الدرجة غير الصفرية تنتمي إلى مكون واحد متصل بقوة . وبالمثل، يحتوي الرسم البياني الموجه على دورة أويلرية إذا وفقط إذا كان من الممكن تقسيمه إلى دورات موجهة منفصلة الحواف، وكانت جميع رؤوسه ذات الدرجة غير الصفرية تنتمي إلى مكون واحد متصل بقوة. [ 6 ]
  • يحتوي الرسم البياني الموجه على مسار أويلري إذا وفقط إذا كان رأس واحد على الأكثر له فرق درجة الدخول ( الدرجة الخارجية ) - درجة الدخول ( الدرجة الداخلية ) = 1، وكان رأس واحد على الأكثر له فرق درجة الدخول (الدرجة الداخلية) - درجة الدخول (الدرجة الخارجية) = 1، وكان لكل رأس آخر درجة دخول ودرجة خروج متساوية، وكانت جميع رؤوسه ذات الدرجة غير الصفرية تنتمي إلى مكون متصل واحد من الرسم البياني غير الموجه الأساسي. [ 6 ]

إنشاء مسارات ودوائر أويلرية

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

خوارزمية فلوري

خوارزمية فلوري خوارزمية أنيقة ولكنها غير فعالة، ويعود تاريخها إلى عام 1883. [ 7 ] لنفترض وجود رسم بياني معروف بأن جميع حوافه تقع في نفس المكون، وأن لديه على الأكثر رأسين من الدرجة الفردية. تبدأ الخوارزمية من رأس ذي درجة فردية، أو، إذا لم يكن للرسم البياني أي رأس من الدرجة الفردية، تبدأ من رأس يتم اختياره عشوائيًا. في كل خطوة، تختار الخوارزمية الحافة التالية في المسار بحيث لا يؤدي حذفها إلى فصل الرسم البياني، إلا إذا لم تكن هناك حافة من هذا النوع، فحينها تختار الحافة المتبقية عند الرأس الحالي. ثم تنتقل إلى الطرف الآخر لتلك الحافة وتحذفها. في نهاية الخوارزمية، لا تتبقى أي حواف، ويشكل التسلسل الذي تم اختيار الحواف منه دورة أويلرية إذا لم يكن للرسم البياني أي رؤوس من الدرجة الفردية، أو مسارًا أويلريًا إذا كان هناك رأسان فقط من الدرجة الفردية.

بينما يكون اجتياز الرسم البياني في خوارزمية فلوري خطيًا بالنسبة لعدد الحواف، أييا(|هـ|){\displaystyle O(|E|)}كما نحتاج إلى مراعاة تعقيد عملية اكتشاف الجسور . إذا أعدنا تشغيل خوارزمية تارجان الخطية لإيجاد الجسور [ 8 ] بعد إزالة كل حافة، فسيكون لخوارزمية فلوري تعقيد زمني قدرهيا(|هـ|2){\displaystyle O(|E|^{2})}تسمح خوارزمية البحث الديناميكي عن الجسور التي وضعها ثورب (2000) بتحسين ذلك إلىيا(|هـ|⋅سجل3⁡|هـ|⋅سجل⁡سجل⁡|هـ|){\displaystyle O(|E|\cdot \log ^{3}|E|\cdot \log \log |E|)}لكن هذا لا يزال أبطأ بكثير من الخوارزميات البديلة.

خوارزمية هيرهولتزر

تقدم ورقة هيرهولزر لعام 1873 طريقة مختلفة لإيجاد دورات أويلر وهي أكثر كفاءة من خوارزمية فلوري:

  • اختر أي رأس بداية v ، واتبع مسارًا من الحواف من ذلك الرأس حتى تعود إليه . من المستحيل أن تتعثر عند أي رأس آخر غير v ، لأن الدرجة الزوجية لجميع الرؤوس تضمن أنه عند دخول المسار إلى رأس آخر w، يجب أن تكون هناك حافة غير مستخدمة تغادر w . المسار المتشكل بهذه الطريقة هو مسار مغلق، ولكنه قد لا يغطي جميع رؤوس وحواف الرسم البياني الأولي.
  • طالما أن هناك رأسًا u ينتمي إلى الجولة الحالية ولكن له حواف مجاورة ليست جزءًا من الجولة، ابدأ مسارًا آخر من u ، واتبع الحواف غير المستخدمة حتى العودة إلى u ، وقم بضم الجولة التي تم تشكيلها بهذه الطريقة إلى الجولة السابقة.
  • بما أننا نفترض أن الرسم البياني الأصلي متصل ، فإن تكرار الخطوة السابقة سيؤدي إلى استنفاد جميع حواف الرسم البياني.

باستخدام بنية بيانات مثل القائمة المرتبطة ثنائياً للحفاظ على مجموعة الحواف غير المستخدمة المتصلة بكل رأس، وللحفاظ على قائمة الرؤوس في الجولة الحالية التي تحتوي على حواف غير مستخدمة، وللحفاظ على الجولة نفسها، يمكن تنفيذ العمليات الفردية للخوارزمية (إيجاد الحواف غير المستخدمة الخارجة من كل رأس، وإيجاد رأس بداية جديد للجولة، وربط جولتين تشتركان في رأس واحد) في وقت ثابت لكل منها، وبالتالي تستغرق الخوارزمية الإجمالية وقتًا خطيًا .يا(|هـ|){\displaystyle O(|E|)}[ 9 ]​

يمكن أيضًا تطبيق هذه الخوارزمية باستخدام قائمة انتظار مزدوجة (deque) . ولأنّ التعثر لا يحدث إلا عندما تمثل قائمة الانتظار المزدوجة مسارًا مغلقًا، ينبغي تدويرها بإزالة الحواف من ذيلها وإضافتها إلى رأسها حتى يتم حل المشكلة، ثم الاستمرار حتى يتم حساب جميع الحواف. يستغرق هذا أيضًا وقتًا خطيًا، حيث لا يتجاوز عدد عمليات التدوير المنفذة أبدًا قيمة معينة.|هـ|{\displaystyle |E|}(بشكل بديهي، يتم نقل أي حواف "سيئة" إلى الرأس، بينما تتم إضافة حواف جديدة إلى الذيل)

عدّ الدوائر الأويلرية

قضايا التعقيد

يمكن حساب عدد الدوائر الأويلرية في رسم بياني موجه باستخدام ما يُعرف بنظرية BEST ، نسبةً إلى دي بروين ، وفان آردين- إهرنفست ، وسميث ، وتوت . تنص هذه النظرية على أن عدد الدوائر الأويلرية في الرسم البياني الموجه هو حاصل ضرب مضروب درجة معينة في عدد التفرعات الجذرية . ويمكن حساب هذا الأخير كمحدد باستخدام نظرية شجرة المصفوفة ، مما يوفر خوارزمية ذات زمن متعدد الحدود.

وردت نظرية BEST لأول مرة بهذا الشكل في "ملاحظة أُضيفت أثناء البرهان" في ورقة آردين-إهرنفست ودي بروين (1951). كان البرهان الأصلي تقابليًا ، وقد عمّم متتاليات دي بروين . وهو يُعدّ تعديلًا على نتيجة سابقة لسميث وتوت (1941).

يُعدّ حساب عدد الدوائر الإيلرية على الرسوم البيانية غير الموجهة أكثر صعوبة. ومن المعروف أن هذه المسألة من فئة #P-complete . [ 10 ] وفي سياق إيجابي، يُعتقد أن استخدام طريقة مونت كارلو لسلاسل ماركوف ، عبر تحويلات كوتزيج (التي قدمها أنطون كوتزيج عام 1968)، يُعطي تقريبًا دقيقًا لعدد الدوائر الإيلرية في الرسم البياني، على الرغم من عدم وجود دليل قاطع على ذلك حتى الآن (حتى بالنسبة للرسوم البيانية ذات الدرجة المحدودة).

حالات خاصة

تم تحديد صيغة تقاربية لعدد الدوائر الأويلرية في الرسوم البيانية الكاملة بواسطة مكاي وروبنسون ( 1995 ) : [ 11 ]

ec⁡(كن)=2(ن+1)2π12هـ-ن22+1112ن(ن-2)(ن+1)2(1+يا(ن-12+ϵ)).{\displaystyle \operatorname {ec} (K_{n})=2^{\frac {(n+1)}{2}}\pi ^{\frac {1}{2}}e^{{\frac {-n^{2}}{2}}+{\frac {11}{12}}}n^{\frac {(n-2)(n+1)}{2}}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}

وقد تم الحصول على صيغة مماثلة لاحقًا بواسطة MI Isaev (2009) للرسوم البيانية الثنائية الكاملة : [ 12 ]

ec⁡(كن،ن)=(ن2-1)!2ن2ن2-ن+12π-ن+12نن-1(1+يا(ن-12+ϵ)).{\displaystyle \operatorname {ec} (K_{n,n})=\left({\frac {n}{2}}-1\right)!^{2n}2^{n^{2}-n+{\frac {1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}

التطبيقات

تُستخدم مسارات أويلر في المعلوماتية الحيوية لإعادة بناء تسلسل الحمض النووي من أجزائه. [ 13 ] كما تُستخدم في تصميم دوائر CMOS لإيجاد الترتيب الأمثل للبوابات المنطقية . [ 14 ] توجد بعض الخوارزميات لمعالجة الأشجار التي تعتمد على جولة أويلر للشجرة (حيث تُعامل كل حافة كزوج من الأقواس). [ 15 ] [ 16 ] يمكن إنشاء متواليات دي بروين كمسارات أويلر لرسوم بيانية دي بروين . [ 17 ]

في الرسوم البيانية اللانهائية

رسم بياني لانهائي جميع درجات رؤوسه تساوي أربعة، ولكن بدون خط أويلري

في الرسم البياني اللانهائي ، يُقابل مفهوم المسار الأويلري أو الدورة الأويلرية خط أويلري، وهو مسار لانهائي مزدوج يغطي جميع حواف الرسم البياني. ولا يكفي لوجود هذا المسار أن يكون الرسم البياني متصلاً وأن تكون جميع درجات رؤوسه زوجية؛ فعلى سبيل المثال، لا يحتوي الرسم البياني اللانهائي لكايلي الموضح، حيث تساوي جميع درجات الرؤوس أربعة، على خط أويلري. وقد وصف إردوش وغرونوالد ووايزفيلد (1936) الرسوم البيانية اللانهائية التي تحتوي على خطوط أويلرية . ولكي يحتوي الرسم البياني اللانهائي أو الرسم البياني المتعدد G على خط أويلري، فمن الضروري والكافي استيفاء جميع الشروط التالية: [ 18 ] [ 19 ]

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

الرسوم البيانية غير الموجهة لأويلر

وضع أويلر شرطًا ضروريًا لكي يكون الرسم البياني المحدود أويلريًا، وهو أن تكون جميع رؤوسه ذات درجة زوجية. وقد أثبت هيرهولتزر أن هذا شرط كافٍ في ورقة بحثية نُشرت عام ١٨٧٣. ويؤدي هذا إلى البيان الضروري والكافي التالي لما يجب أن يتوفر في الرسم البياني المحدود ليكون أويلريًا: يكون الرسم البياني المحدود غير الموجه والمتصل أويلريًا إذا وفقط إذا كانت كل رأس من رؤوس G ذات درجة زوجية. [ ٢٠ ]

وقد أثبت فيبلين النتيجة التالية في عام 1912: يكون الرسم البياني المتصل غير الموجه أويلريًا إذا وفقط إذا كان اتحادًا منفصلاً لبعض الدورات. [ 20 ]

الرسم البياني الموجه ذو الدرجات الزوجية فقط والذي ليس رسمًا بيانيًا أويلريًا، بمثابة مثال مضاد للقول بأن الشرط الكافي لكي يكون الرسم البياني الموجه أويلريًا هو أن تكون جميع درجاته زوجية.
الرسم البياني الموجه ذو الدرجات الزوجية فقط والذي ليس رسمًا بيانيًا أويلريًا، بمثابة مثال مضاد للقول بأن الشرط الكافي لكي يكون الرسم البياني الموجه أويلريًا هو أن تكون جميع درجاته زوجية.

قام هيرهولزر بتطوير خوارزمية زمنية خطية لإنشاء مسار أويلري في رسم بياني غير موجه.

الرسوم البيانية الموجهة لأويلر

من الممكن وجود رسم بياني موجه ذي درجات خروج زوجية، ولكنه ليس رسمًا بيانيًا أويلريًا. بما أن الدائرة الأويلرية تغادر رأسًا ما بنفس عدد مرات دخولها إليه، فإن الشرط الضروري لوجود دائرة أويلرية هو تساوي درجة الدخول ودرجة الخروج عند كل رأس. من البديهي أن الاتصال ضروري أيضًا. وقد أثبت كونيغ أن هذه الشروط كافية أيضًا. أي أن الرسم البياني الموجه يكون أويلريًا إذا وفقط إذا كان متصلًا وكانت درجة الدخول ودرجة الخروج متساوية عند كل رأس. [ 20 ]

في هذه النظرية، لا يهم ما إذا كان "متصل" يعني "متصل بشكل ضعيف" أو "متصل بشكل قوي" لأنهما متكافئان بالنسبة للرسوم البيانية الأويلرية.

خوارزمية هيرهولزر ذات الوقت الخطي لإنشاء جولة أويلرية قابلة للتطبيق أيضًا على الرسوم البيانية الموجهة. [ 20 ]

الرسوم البيانية المختلطة لأويلر

هذا الرسم البياني المختلط هو رسم بياني أويلري. الرسم البياني زوجي ولكنه غير متناظر، مما يثبت أن الزوجية والتناظر ليسا شرطين ضروريين وكافيين لكي يكون الرسم البياني المختلط رسمًا بيانيًا أويلريًا.
هذا الرسم البياني المختلط هو رسم بياني أويلري. الرسم البياني زوجي ولكنه غير متناظر، مما يثبت أن الزوجية والتناظر ليسا شرطين ضروريين وكافيين لكي يكون الرسم البياني المختلط رسمًا بيانيًا أويلريًا.

تُضمن جميع الرسوم البيانية المختلطة التي تكون زوجية ومتناظرة أن تكون رسومًا بيانية أويلرية. ومع ذلك، فهذا ليس شرطًا ضروريًا، إذ من الممكن إنشاء رسم بياني غير متناظر وزوجي يكون أويلريًا. [ 20 ]

أثبت فورد وفولكرسون في عام 1962 في كتابهما "التدفقات في الشبكات " [ 21 ] شرطًا ضروريًا وكافيًا لكي يكون الرسم البياني أويلريًا، وهو أن كل رأس يجب أن يكون زوجيًا ويحقق شرط التوازن، أي لكل مجموعة فرعية من الرؤوس S، يجب أن يكون الفرق بين عدد الأقواس الخارجة من S والداخلة إلى S أقل من أو يساوي عدد الحواف المتصلة بـ S. [ 20 ]

إن عملية التحقق مما إذا كان الرسم البياني المختلط من نوع أويلر أصعب من التحقق مما إذا كان الرسم البياني غير الموجه أو الموجه من نوع أويلر لأن شرط المجموعة المتوازنة يتعلق بكل مجموعة فرعية ممكنة من الرؤوس.

دورات وجسور أويلر

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

يُعرَّف الرسم البياني شبه الأويلري بأنه رسم بياني يمكن تحويله إلى رسم بياني أويلري بإضافة حافة واحدة (أو بعبارة أخرى، رسم بياني يحتوي على مسار أويلري). كل رسم بياني شبه أويلري يكون شبه خالي من الجسور، ولكن العكس غير صحيح.

تتقاطع فئتا الرسوم البيانية عديمة الجسور والرسوم البيانية شبه الأويلرية تقاطعًا غير فارغ (فالرسوم البيانية الأويلرية هي رسوم بيانية عديمة الجسور وشبه أويلرية)، لكنهما لا تحتويان بعضهما بعضًا. [ 22 ] : الملحق ب

رسم بياني مختلط زوجي ينتهك شرط المجموعة المتوازنة، وبالتالي فهو ليس رسمًا بيانيًا أويلريًا.
رسم بياني مختلط زوجي ينتهك شرط المجموعة المتوازنة، وبالتالي فهو ليس رسمًا بيانيًا أويلريًا.
رسم بياني مختلط زوجي يحقق شرط المجموعة المتوازنة، وبالتالي فهو رسم بياني مختلط أويلري.
رسم بياني مختلط زوجي يحقق شرط المجموعة المتوازنة، وبالتالي فهو رسم بياني مختلط أويلري.

انظر أيضاً

ملحوظات

  1. 1 2 يحصر بعض الناس مصطلحي "المسار" و "الدوران" للدلالة على المسار والدوران غير المتقاطعين . يُعرف المسار المتقاطع (محتملًا) باسم " المسار" أو " الممشى المفتوح "، بينما يُعرف الدوران المتقاطع (محتملًا) باسم " الدائرة" أو " الممشى المغلق" . يمكن تجنب هذا الالتباس باستخدام مصطلحي "المسار الأويلري" و"الدائرة الأويلرية" عندما يُسمح بالتقاطع الذاتي.

مراجع

  1. ↑ إن إل بيغز ، إي كي لويد، وآر جيه ويلسون ، نظرية الرسم البياني، 1736-1936 ، مطبعة كلارندون، أكسفورد، 1976، 8-9، ISBN 0-19-853901-0.
  2. ↑ سي إل مالوز، إن جيه إيه سلون (1975). "الرسوم البيانية الثنائية، وفئات التبديل، ورسوم أويلر متساوية في العدد" (ملف PDF) . مجلة SIAM للرياضيات التطبيقية . 28 (4): 876-880 . doi : 10.1137/0128070 . JSTOR 2100368 . 
  3. ↑ جون-إيتشي ياماغوتشي، مقدمة في نظرية الرسم البياني .
  4. ↑ ملخص شوم لنظرية ومسائل نظرية الرسوم البيانية، بقلم في كي بالاكريشنان.
  5. ↑ شريجفر، أ. (1983)، "حدود عدد التوجهات الأويلرية" ، كومبيناتوريكا ، 3 ( 3-4 ): 375-380 ، doi : 10.1007/BF02579193 ، MR 0729790 ، S2CID 13708977  .
  6. 1 2 3 4 بوليا، جورج ؛ تارجان، روبرت إي .؛ وودز، دونالد ر. (أكتوبر 2009)، "المسارات الهاميلتونية والأويلرية"، ملاحظات حول التوافقية التمهيدية ، بيركهاوزر بوسطن، ص 157-168 ، doi : 10.1007/978-0-8176-4953-1_13 ، ISBN  9780817649531
  7. ^ فلوري ، بيير هنري (1883)، “Deux problèmes de Géométrie de الوضع” ، مجلة الرياضيات الأولية ، الجزء الثاني. (بالفرنسية) 2 : 257 – 261.
  8. ↑ تارجان، ر. إندري (1974)، "ملاحظة حول إيجاد جسور الرسم البياني"، رسائل معالجة المعلومات ، 2 (6): 160-161 ، doi : 10.1016/0020-0190(74)90003-9 ، MR 0349483 .
  9. ↑ فليشنر، هربرت (1991)، "X.1 خوارزميات للمسارات الأويلرية"، الرسوم البيانية الأويلرية والمواضيع ذات الصلة: الجزء 1، المجلد 2 ، حوليات الرياضيات المتقطعة، المجلد 50، إلسيفير، الصفحات X.1–13 ، ISBN   978-0-444-89110-5.
  10. ↑ برايتويل ووينكلر ، " ملاحظة حول عد الدوائر الأويلرية "، 2004.
  11. ↑ بريندان مكاي وروبرت دبليو روبنسون، التعداد التقاربي للدوائر الأويلرية في الرسم البياني الكامل ، كومبيناتوريكا ، 10 (1995)، العدد 4، 367-377.
  12. ↑ إم آي إيسايف (2009). "العدد التقاربي للدوائر الأويلرية في الرسوم البيانية الثنائية الكاملة". وقائع المؤتمر الثاني والخمسين لـ MFTI (باللغة الروسية). موسكو: 111-114 .
  13. ↑ بيفزنر، بافيل أ.؛ تانغ، هايكسو؛ ووترمان، مايكل س. (2001). "نهج مسار أويلر لتجميع شظايا الحمض النووي" . وقائع الأكاديمية الوطنية للعلوم في الولايات المتحدة الأمريكية . 98 (17): 9748-9753 . Bibcode : 2001PNAS...98.9748P . doi : 10.1073/pnas.171285098 . PMC 55524. PMID 11504945 .  
  14. ↑ روي، كونتال (2007). "الترتيب الأمثل لبوابات منطق CMOS باستخدام منهج مسار أويلر: بعض الأفكار والتفسيرات" . مجلة الحوسبة وتكنولوجيا المعلومات . 15 (1): 85-92 . doi : 10.2498/cit.1000731 .
  15. ^ تارجان، روبرت إي. فيشكين، عوزي (1985). “خوارزمية اتصال ثنائي متوازي فعالة”. مجلة SIAM للحوسبة . 14 (4): 862– 874. سايتسيركس 10.1.1.465.8898 . دوى : 10.1137/0214061 . 
  16. ↑ بيركمان، عمر؛ فيشكين، عوزي (أبريل 1994). "إيجاد الأسلاف في الأشجار". مجلة علوم الحاسوب والأنظمة . 2. 48 (2): 214-230 . doi : 10.1016/S0022-0000(05)80002-9 .
  17. ↑ سافاج، كارلا (يناير 1997). "دراسة استقصائية لرموز غراي التوافقية". مجلة SIAM Review . 39 (4): 605-629 . doi : 10.1137/S0036144595295272 . ISSN 0036-1445 . 
  18. ^ كومجاث، بيتر (2013)، “عمل إردوس على الرسوم البيانية اللانهائية” ، الذكرى المئوية لإردوس ، بولياي سوك. الرياضيات. مسمار، المجلد. 25 يانوس بولياي الرياضيات. شركة نفط الجنوب، بودابست، الصفحات من 325 إلى 345، دوى : 10.1007/978-3-642-39286-3_11 ، السيد 3203602   .
  19. ↑ بولوباس، بيلا (1998)، نظرية الرسم البياني الحديثة ، نصوص الدراسات العليا في الرياضيات، المجلد 184، سبرينغر-فيرلاغ، نيويورك، ص 20، doi : 10.1007/978-1-4612-0619-4 ، ISBN   0-387-98488-7MR 1633290​ .
  20. 1 2 3 4 5 6 كوربيران، أنخيل؛ لابورت، جيلبرت، محرران. (2015). توجيه الأقواس: المشكلات والأساليب والتطبيقات . سلسلة MOS-SIAM في التحسين. SIAM. doi : 10.1137/1.9781611973679 . ISBN 978-1-61197-366-2تم الاطلاع عليه بتاريخ 19-08-2022 .
  21. ↑ إل آر فورد؛ دي آر فولكرسون (1962). التدفقات في الشبكات . برينستون، نيوجيرسي: مطبعة جامعة برينستون. ISBN 9780691079622.{{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
  22. ↑ بي، شياوهوي؛ إلكيند، إديث؛ سيغال-هاليفي، إيريل؛ سوكسومبونغ، ​​واروت (31-03-2025). "تقسيم كعكة بيانية" . مجلة SIAM للرياضيات المتقطعة . 39 (1): 19-54 . arXiv : 1910.14129 . doi : 10.1137/22M1500502 . ISSN 0895-4801 . 

فهرس