الدورة (نظرية الرسم البياني)

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة
رسم بياني بحواف ملونة لتوضيح مسار مغلق ، H–A–B–A–H، باللون الأخضر؛ دائرة تمثل مسارًا مغلقًا تكون فيه جميع الحواف متميزة، B–D–E–F–D–C–B، باللون الأزرق؛ ودورة تمثل مسارًا مغلقًا تكون فيه جميع الرؤوس متميزة، H–D–G–H، باللون الأحمر.

في نظرية المخططات ، تُعرَّف الدورة في المخطط بأنها مسار غير فارغ تتساوى فيه الرؤوس الأولى والأخيرة فقط . أما الدورة الموجهة في المخطط الموجه فهي مسار موجه غير فارغ تتساوى فيه الرؤوس الأولى والأخيرة فقط.

يُطلق على الرسم البياني الخالي من الدورات اسم الرسم البياني غير الدوري . ويُطلق على الرسم البياني الموجه الخالي من الدورات الموجهة اسم الرسم البياني الموجه غير الدوري . ويُطلق على الرسم البياني المتصل الخالي من الدورات اسم الشجرة .

التعريفات

الدائرة والدورة

  • الدائرة هي مسار غير فارغ تكون فيه الرؤوس الأولى والأخيرة متساوية ( مسار مغلق ) . [ 1 ]
ليكن G = ( V , E , Φ ) رسمًا بيانيًا. الدائرة هي مسار غير فارغ ( e1 , e2 , ... , en ) مع تسلسل رؤوس ( v1 , v2 , ... , vn , v1 ) .
  • الدائرة أو الدائرة البسيطة هي دائرة تكون فيها v1 ، ...، vn قيمًا مختلفة. [ 1 ]
  • يُطلق على n طول الدائرة أو طول الدورة .

الدائرة الموجهة والدورة الموجهة

  • الدائرة الموجهة هي مسار موجه غير فارغ تكون فيه الرؤوس الأولى والأخيرة متساوية ( مسار موجه مغلق ). [ 1 ]
ليكن G = ( V , E , Φ ) رسمًا بيانيًا موجهًا. الدائرة الموجهة هي مسار موجه غير فارغ ( e1 , e2 , ... , en ) مع تسلسل رؤوس ( v1 , v2 , ... , vn , v1 ) .
  • الدورة الموجهة أو الدائرة الموجهة البسيطة هي دائرة موجهة تكون فيها v1 ، ...، vn قيمًا مختلفة. [ 1 ]
  • يُطلق على n طول الدائرة الموجهة أو طول الدورة الموجهة .

دراجة بدون أسلاك

في هذا الرسم البياني، الدورة الخضراء A–B–C–D–E–F–A خالية من الأوتار، بينما الدورة الحمراء G–H–I–J–K–L–G ليست كذلك. والسبب في ذلك هو أن الحافة {K, I} تُشكّل وترًا.

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

محيط الرسم البياني هو طول أقصر دورة فيه؛ وهذه الدورة بالضرورة خالية من الأوتار. تُعرَّف الأقفاص بأنها أصغر الرسوم البيانية المنتظمة ذات تركيبات معينة من الدرجة والمحيط.

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

مساحة للدراجات

قد يشير مصطلح "الدورة" أيضًا إلى عنصر من عناصر فضاء الدورات في الرسم البياني. توجد العديد من فضاءات الدورات، واحد لكل حقل معاملات أو حلقة. وأكثرها شيوعًا هو فضاء الدورات الثنائي (يُسمى عادةً ببساطة فضاء الدورات )، والذي يتكون من مجموعات الحواف ذات الدرجة الزوجية عند كل رأس؛ وهو يشكل فضاءً متجهيًا على الحقل ذي العنصرين . وبحسب نظرية فيبلن ، يمكن تكوين كل عنصر من عناصر فضاء الدورات كاتحاد منفصل الحواف لدورات بسيطة. أساس الدورات في الرسم البياني هو مجموعة من الدورات البسيطة التي تُشكل أساسًا لفضاء الدورات. [ 2 ]

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

الكشف عن الدورة

يمكن تحديد وجود دورة في الرسوم البيانية الموجهة وغير الموجهة من خلال ما إذا كان البحث العميق أولاً (DFS) يعثر على حافة تشير إلى سلف للرأس الحالي (أي أنها تحتوي على حافة خلفية ). [ 4 ] جميع الحواف الخلفية التي يتجاهلها البحث العميق أولاً هي جزء من دورات. [ 5 ] في الرسم البياني غير الموجه، لا تُحتسب الحافة المؤدية إلى والد العقدة كحافة خلفية، ولكن العثور على أي رأس آخر تمت زيارته مسبقًا يشير إلى وجود حافة خلفية. في حالة الرسوم البيانية غير الموجهة، يتطلب الأمر O ( n ) فقط من الوقت للعثور على دورة في رسم بياني ذي n رأس، حيث لا يمكن أن يكون أكثر من n  -  1 حافة من حواف الشجرة.

تستطيع العديد من خوارزميات الفرز الطوبولوجي اكتشاف الحلقات أيضًا، لأنها تُشكل عائقًا أمام وجود الترتيب الطوبولوجي. كذلك، إذا قُسِّمَ رسم بياني مُوجَّه إلى مكونات مترابطة بقوة ، فإن الحلقات لا توجد إلا داخل هذه المكونات وليس بينها، لأن الحلقات مترابطة بقوة. [ 5 ]

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

تشمل تطبيقات اكتشاف الدورات استخدام رسوم بيانية للانتظار لاكتشاف حالات الجمود في الأنظمة المتزامنة. [ 6 ]

الخوارزمية

يمكن وصف استخدام البحث العميق أولاً لإيجاد دورة على النحو التالي:

لكل رأس v: تم زيارته(v) = تم الانتهاء(v) = خطأ لكل رأس v: DFS(v)

أين

DFS(v) = إذا تم الانتهاء(v): إرجاع إذا تمت زيارته (v): تم العثور على دورة يعود تم زيارته(v) = صحيح لكل جار w: DFS(w) تم الانتهاء(v) = صحيح

في الرسوم البيانية غير الموجهة، يُقصد بـ"الجوار" جميع الرؤوس المتصلة بالرأس v ، باستثناء الرأس الذي يتم استدعاؤه بشكل متكرر بواسطة خوارزمية البحث العمقي أولاً (DFS(v)) . يمنع هذا الاستثناء الخوارزمية من إيجاد دورة تافهة من الشكل v → w → v ؛ وتوجد هذه الدورات في كل رسم بياني غير موجه يحتوي على حافة واحدة على الأقل.

أما النسخة التي تستخدم البحث بالعرض أولاً فستجد دورة بأقصر طول ممكن.

تغطية الرسوم البيانية حسب الدورة

في بحثه المنشور عام ١٧٣٦ حول جسور كونيغسبرغ السبعة ، [ ٧ ] والذي يُعتبر على نطاق واسع بداية نظرية المخططات، [ ٨ ] [ ٩ ] أثبت ليونارد أويلر أنه لكي يكون للمخطط غير الموجه المحدود مسار مغلق يمر بكل حافة مرة واحدة فقط (مما يجعله مسارًا مغلقًا)، فإنه من الضروري والكافي أن يكون متصلًا باستثناء الرؤوس المعزولة (أي أن جميع الحواف تقع في مكون واحد) وأن تكون درجة كل رأس زوجية. [ ٧ ] أما في المخطط الموجه، فإن التوصيف المقابل لوجود مسار مغلق يمر بكل حافة مرة واحدة فقط هو أن يكون المخطط متصلًا بقوة وأن يكون عدد الحواف الداخلة والخارجة متساويًا عند كل رأس. في كلتا الحالتين، يُعرف المسار المغلق الناتج باسم مسار أويلر . إذا كان للرسم البياني غير الموجه المحدود درجة زوجية عند كل رأس من رؤوسه، بغض النظر عما إذا كان متصلاً أم لا، فمن الممكن إيجاد مجموعة من الدورات البسيطة التي تغطي كل حافة مرة واحدة بالضبط: هذه هي نظرية فيبلن . [ 10 ] عندما لا يستوفي الرسم البياني المتصل شروط نظرية أويلر، يمكن مع ذلك إيجاد مسار مغلق ذي طول أدنى يغطي كل حافة مرة واحدة على الأقل في وقت متعدد الحدود عن طريق حل مسألة فحص المسار .

تُعدّ مشكلة إيجاد دورة بسيطة واحدة تُغطي كل رأس مرة واحدة فقط، بدلاً من تغطية الحواف، أكثر صعوبة. تُعرف هذه الدورة بدورة هاميلتونية ، وتحديد وجودها مسألة NP-كاملة . [ 11 ] نُشرت العديد من الأبحاث حول فئات الرسوم البيانية التي يُمكن ضمان احتوائها على دورات هاميلتونية؛ ومن الأمثلة على ذلك نظرية أور التي تنص على أنه يُمكن دائمًا إيجاد دورة هاميلتونية في رسم بياني يكون فيه مجموع درجات كل زوج من الرؤوس غير المتجاورة مساويًا على الأقل للعدد الإجمالي للرؤوس في الرسم البياني. [ 12 ]

تنص فرضية التغطية المزدوجة للدورة على أنه لكل رسم بياني بدون جسور ، توجد مجموعة متعددة من الدورات البسيطة التي تغطي كل حافة من حواف الرسم البياني مرتين بالضبط. ولا يزال إثبات صحة هذه الفرضية (أو إيجاد مثال مضاد لها) مسألة مفتوحة. [ 13 ]

فئات الرسوم البيانية المحددة بواسطة الدورة

يمكن تعريف أو تمييز العديد من الفئات المهمة من الرسوم البيانية من خلال دوراتها. وتشمل هذه الفئات ما يلي:

انظر أيضاً

مراجع

  1. 1 2 3 4 بندر وويليامسون 2010 ، ص 164.
  2. ↑ غروس، جوناثان ل.؛ يلين، جاي (2005)، "4.6 الرسوم البيانية والفضاءات المتجهة" ، نظرية الرسوم البيانية وتطبيقاتها (الطبعة الثانية  )، مطبعة سي آر سي، الصفحات 197-207 ، رقم ISBN  9781584885054تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 4 فبراير 2023 ، وتمت معاينته بتاريخ 27 سبتمبر 2016..
  3. ↑ ديستل، راينهارد (2012)، "1.9 بعض الجبر الخطي" ، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد 173، سبرينغر، الصفحات 23-28 ، مؤرشف من الأصل في 2023-02-04 ، تم استرجاعه في 2016-09-27  .
  4. ↑ تاكر، آلان (2006). "الفصل 2: ​​دوائر التغطية وتلوين الرسوم البيانية". التوافقية التطبيقية ( الطبعة الخامسة). هوبوكين: جون وايلي وأولاده. ص 49. ISBN   978-0-471-73507-6.
  5. 1 2 سيدجويك، روبرت (1983)، "خوارزميات الرسوم البيانية"، الخوارزميات ، أديسون-ويسلي، ISBN 0-201-06672-6
  6. ↑ سيلبرشاتز، أبراهام ؛ بيتر جالفين؛ جريج جان (2003). مفاهيم أنظمة التشغيل . جون وايلي وأولاده، ص 260. ISBN  0-471-25060-0.
  7. 1 2 أويلر، ليونارد (1741). "حل المشكلات المتعلقة بالمواقع الهندسية ذات الصلة" . Commentarii Academiae Scientiarum Petropolitanae (باللاتينية). 8 : 128-140 + اللوحة الثامنة .تُرجمت إلى الإنجليزية بعنوان حل مشكلة في هندسة الموضع ، مايكل بيرند.
  8. ↑ رايز، تيم (2018). "كونيغسبرغ أويلر: القوة التفسيرية للرياضيات" ( ملف PDF) . المجلة الأوروبية لفلسفة العلوم . 8 (3): 331-346 . doi : 10.1007/s13194-017-0189-x . S2CID 125194454. يمكن القول إن كون ورقة أويلر تُعدّ من أوائل ابتكارات نظرية المخططات هو أهم ما يميزها. 
  9. ↑ شيلدز، روب (2012). "الطوبولوجيا الثقافية: جسور كونيغسبورغ السبعة 1736". النظرية والثقافة والمجتمع . 29 ( 4-5 ): 43-57 . doi : 10.1177/0263276412451161 . S2CID 146875675 . 
  10. ↑ فيبلين، أوزوالد (1912)، "تطبيق المعادلات النمطية في تحليل المواقع"، حوليات الرياضيات ، السلسلة الثانية، 14 (1): 86-94 ، doi : 10.2307/1967604 ، JSTOR 1967604 .
  11. ↑ ريتشارد م. كارب (1972)، "قابلية الاختزال بين المسائل التوافقية" (ملف PDF) ، في ر. إي. ميلر وج. و. ثاتشر (محرران)، تعقيد الحسابات الحاسوبية ، نيويورك: بلينوم، الصفحات 85-103 ، مؤرشف (ملف PDF) من الأصل بتاريخ 10 فبراير 2021 ، تم استرجاعه بتاريخ 12 مارس 2014 {{citation}}: CS1 maint: موقع الناشر ( رابط ) .
  12. ↑ أور، أ. (1960)، "ملاحظة حول دوائر هاميلتون"، المجلة الرياضية الأمريكية الشهرية ، 67 (1): 55، doi : 10.2307/2308928 ، JSTOR 2308928 .
  13. ↑ ياغر، ف. (1985)، "دراسة استقصائية لتخمين الغطاء المزدوج للدورة"، حوليات الرياضيات المتقطعة 27 - الدورات في الرسوم البيانية ، دراسات الرياضيات في شمال هولندا، المجلد 27، الصفحات 1-12 ، doi : 10.1016/S0304-0208(08)72993-1 ، ISBN   978-0-444-87803-8.