بيان موجه خال من الحلقات
من ويكيبيديا، الموسوعة encyclopedia
البيان الموجه الخالي من الحلقات[1] (بالإنجليزية: Directed acyclic graph)، في الرياضيات، ولا سيما نظرية الرسم البياني وعلوم الكمبيوتر، الرسم البياني غير الدوري الموجه (DAG أو dag / ˈdæɡ / (حول هذا الصوت)) هو رسم بياني موجه بدون دورات موجهة. أي أنه يتكون من الرؤوس والحواف (تسمى أيضًا الأقواس)، مع توجيه كل حافة من رأس إلى آخر، بحيث لا توجد طريقة للبدء من أي قمة v واتباع تسلسل متسق من الحواف التي تتكرر في النهاية ل v مرة أخرى. بالتساوي، DAG هو رسم بياني موجه له ترتيب طوبولوجي، تسلسل من القمم بحيث يتم توجيه كل حافة من وقت سابق إلى لاحقًا في التسلسل.
هذه المقالة بحاجة لصندوق معلومات. |
هذه مقالة غير مراجعة. (ديسمبر 2020) |
يمكن لـ DAGs نمذجة العديد من أنواع المعلومات المختلفة. على سبيل المثال، يمكن نمذجة جدول بيانات على هيئة DAG ، برأس لكل خلية وحافة عندما تستخدم الصيغة في خلية واحدة القيمة من أخرى؛ يمكن استخدام الترتيب الطوبولوجي لـ DAG هذا لتحديث جميع قيم الخلايا عند تغيير جدول البيانات. وبالمثل، يمكن استخدام الترتيب الطوبولوجي لـ DAGs لطلب عمليات التجميع في ملف makefile. تستخدم تقنية تقييم البرنامج ومراجعته (PERT) DAGs لنمذجة معالم وأنشطة المشاريع البشرية الكبيرة، وجدولة هذه المشاريع لاستخدام أقل وقت إجمالي ممكن. تتضمن الكتل المنطقية التوافقية في تصميم الدوائر الإلكترونية، والعمليات في لغات برمجة تدفق البيانات، شبكات غير دورية لعناصر المعالجة. يمكن أن تمثل DAG أيضًا مجموعات من الأحداث وتأثيرها على بعضها البعض، إما في بنية احتمالية مثل شبكة Bayesian أو كسجل للبيانات التاريخية مثل أشجار العائلة أو تواريخ الإصدارات لأنظمة التحكم في المراجعة الموزعة. يمكن أيضًا استخدام DAGs كتمثيل مضغوط لبيانات التسلسل، مثل تمثيل الرسم البياني للكلمات الحلقية الموجه لمجموعة من السلاسل، أو تمثيل مخطط القرار الثنائي لتسلسل الخيارات الثنائية. بشكل أكثر تجريدًا، تشكل علاقة قابلية الوصول في DAG ترتيبًا جزئيًا، ويمكن تمثيل أي ترتيب جزئي محدود بواسطة DAG باستخدام قابلية الوصول.
تتضمن المشكلات الحسابية ذات الوقت متعدد الحدود المهمة في DAGs الفرز الطوبولوجي (حساب الترتيب الطوبولوجي)، وبناء الإغلاق الانتقالي والاختزال الانتقالي (أكبر وأصغر DAGs مع نفس علاقة قابلية الوصول، على التوالي) للمجموعات، ومشكلة الإغلاق، حيث الهدف هو العثور على مجموعة فرعية ذات وزن أدنى من الرؤوس بدون حواف تربطها ببقية الرسم البياني. يعد تحويل الرسم البياني الموجه بالدورات إلى DAG عن طريق حذف أقل عدد ممكن من الرؤوس أو الحواف (مجموعة قمة التغذية المرتدة ومشكلة مجموعة حافة التغذية المرتدة، على التوالي) مشكلة صعبة NP ، ولكن يمكن تحويل أي رسم بياني موجه إلى DAG (التكثيف) عن طريق التعاقد مع كل مكون متصل بقوة في خفة واحدة. يمكن حل مشاكل العثور على أقصر المسارات والمسارات الأطول على DAGs في الوقت الخطي، على عكس الرسوم البيانية التعسفية التي تكون فيها خوارزميات المسار الأقصر أبطأ وأطول مسار مشاكل NP-hard.
المفهوم المقابل للرسوم البيانية غير الموجهة هو الغابة، رسم بياني غير موجه بدون دورات. ينتج عن اختيار اتجاه الغابة نوعًا خاصًا من الرسم البياني غير الدوري الموجه يسمى الشجرة المتعددة. ومع ذلك، لا يتوافق كل رسم بياني غير دوري موجه مع اتجاه حواف رسم بياني لا دوري غير موجه. بعد كل شيء، كل رسم بياني غير موجه، سواء كان دوريًا أو غير دوري، له اتجاه لا دوري، وتخصيص لاتجاه لحوافه يجعله في رسم بياني لا دوري موجه. للتأكيد على أن DAGs ليست هي نفس الإصدارات الموجهة من الرسوم البيانية غير الدورية غير الموجهة، يسميها بعض المؤلفين الرسوم البيانية غير الدورية الموجهة [1] أو الرسوم البيانية غير الدورية.