بيان موجه خال من الحلقات
التطبيقات

الجدولة
تمثيلات الرسوم البيانية غير الدورية الموجهة للطلبات الجزئية لها تطبيقات عديدة في جدولة أنظمة المهام مع قيود الترتيب. فئة مهمة من المشاكل من هذا النوع تتعلق بمجموعات الكائنات التي تحتاج إلى تحديث، مثل خلايا جدول البيانات بعد تغيير إحدى الخلايا، أو ملفات الكائن لجزء من برنامج الكمبيوتر بعد أن تم تعديل كود المصدر الخاص به. تغير. في هذا السياق، يمثل الرسم البياني التبعية رسمًا بيانيًا له رأس لكل كائن يتم تحديثه، وحافة تربط بين كائنين كلما احتاج أحدهما إلى التحديث قبل الآخر. تسمى الدورة في هذا الرسم البياني التبعية الدائرية، وهي غير مسموح بها عمومًا، لأنه لن تكون هناك طريقة لجدولة المهام المتضمنة في الدورة باستمرار. تشكل الرسوم البيانية التبعية بدون تبعيات دائرية DAGs.
على سبيل المثال، عندما تتغير خلية واحدة في جدول البيانات، من الضروري إعادة حساب قيم الخلايا الأخرى التي تعتمد بشكل مباشر أو غير مباشر على الخلية التي تم تغييرها. بالنسبة لهذه المشكلة، فإن المهام المراد جدولتها هي عمليات إعادة حساب قيم الخلايا الفردية في جدول البيانات. تنشأ التبعيات عندما يستخدم تعبير في خلية ما قيمة من خلية أخرى. في مثل هذه الحالة، يجب إعادة حساب القيمة المستخدمة قبل التعبير الذي يستخدمها. يسمح الترتيب الطوبولوجي لرسم بياني التبعية، واستخدام هذا الترتيب الطوبولوجي لجدولة تحديثات الخلية، بتحديث جدول البيانات بأكمله بتقييم واحد فقط لكل خلية. [31] تظهر مشكلات مماثلة في ترتيب المهام في ملفات makefiles الخاصة بتجميع البرامج وجدولة التعليمات لتحسين برامج الكمبيوتر منخفضة المستوى.
يتم استخدام صيغة مختلفة إلى حد ما قائمة على DAG لقيود الجدولة من خلال تقنية تقييم ومراجعة البرنامج (PERT)، وهي طريقة لإدارة المشاريع البشرية الكبيرة التي كانت أحد التطبيقات الأولى لـ DAGs. في هذه الطريقة، تمثل رؤوس DAG معالم المشروع بدلاً من المهام المحددة التي يتعين القيام بها. بدلاً من ذلك، يتم تمثيل المهمة أو النشاط بحافة DAG ، التي تربط بين معلمين يمثلان بداية المهمة وإكمالها. يتم تمييز كل حافة من هذا القبيل بتقدير لمقدار الوقت الذي سيستغرقه فريق من العمال لأداء المهمة. يمثل أطول مسار في DAG هذا المسار الحرج للمشروع ، وهو المسار الذي يتحكم في إجمالي الوقت للمشروع. يمكن جدولة المعالم الفردية وفقًا لأطوال المسارات الأطول المنتهية عند الرؤوس.
شبكات معالجة البيانات
يمكن استخدام الرسم البياني غير الدوري الموجه لتمثيل شبكة من عناصر المعالجة. في هذا التمثيل ، تدخل البيانات عنصر معالجة من خلال حوافها الواردة وتترك العنصر من خلال حوافه الصادرة.
على سبيل المثال ، في تصميم الدوائر الإلكترونية ، يمكن تمثيل الكتل المنطقية التوافقية الثابتة كنظام لا دوري من البوابات المنطقية التي تحسب وظيفة أحد المدخلات ، حيث يتم تمثيل مدخلات ومخرجات الوظيفة على أنها بتات فردية. بشكل عام ، لا يمكن استخدام مخرجات هذه الكتل كمدخلات ما لم يتم التقاطها بواسطة سجل أو عنصر حالة يحافظ على خصائصه غير الدورية. مخططات الدوائر الإلكترونية إما على الورق أو في قاعدة بيانات هي شكل من أشكال الرسوم البيانية غير الدورية الموجهة باستخدام مثيلات أو مكونات لتشكيل مرجع موجه إلى مكون المستوى الأدنى. الدوائر الإلكترونية نفسها ليست بالضرورة غير دورية أو موجهة.
تصف لغات برمجة تدفق البيانات أنظمة العمليات على تدفقات البيانات ، والوصلات بين مخرجات بعض العمليات ومدخلات البعض الآخر. يمكن أن تكون هذه اللغات ملائمة لوصف مهام معالجة البيانات المتكررة ، حيث يتم تطبيق نفس مجموعة العمليات المرتبطة دوريًا على العديد من عناصر البيانات. يمكن تنفيذها كخوارزمية متوازية يتم فيها تنفيذ كل عملية من خلال عملية متوازية بمجرد أن تصبح مجموعة أخرى من المدخلات متاحة لها.
في المترجمين ، يمكن تمثيل رمز الخط المستقيم (أي تسلسل العبارات بدون حلقات أو فروع شرطية) بواسطة DAG الذي يصف مدخلات ومخرجات كل من العمليات الحسابية التي يتم إجراؤها داخل الكود. هذا التمثيل يسمح للمترجم بأداء حذف التعابير الفرعية بكفاءة. في مستوى أعلى من تنظيم الكود ، ينص مبدأ التبعيات غير الدورية على أن التبعيات بين الوحدات أو مكونات نظام برمجيات كبير يجب أن تشكل رسمًا بيانيًا لا دوريًا موجهًا.
الهياكل السببية
الرسوم البيانية التي تمثل فيها الرؤوس أحداثًا تحدث في وقت محدد ، وحيث تكون الحواف دائمًا نقطة من قمة الزمن المبكر إلى قمة الوقت المتأخر للحافة ، تكون بالضرورة موجَّهة وغير دورية. يتبع عدم وجود دورة لأن الوقت المرتبط بالرأس يزداد دائمًا كلما اتبعت أي مسار في الرسم البياني حتى لا يمكنك أبدًا العودة إلى قمة على مسار. هذا يعكس حدسنا الطبيعي بأن السببية تعني أن الأحداث لا يمكن أن تؤثر إلا على المستقبل ، ولا تؤثر أبدًا على الماضي ، وبالتالي ليس لدينا حلقات سببية. مثال على هذا النوع من الرسم البياني غير الدوري الموجه هو تلك التي تمت مواجهتها في نهج المجموعة السببية للجاذبية الكمية على الرغم من أن الرسوم البيانية التي تم النظر فيها في هذه الحالة مكتملة بشكل عابر. في مثال محفوظات الإصدار ، يرتبط كل إصدار من البرنامج بوقت فريد ، وعادةً ما يكون الوقت الذي تم فيه حفظ الإصدار أو الالتزام به أو إصداره. بالنسبة إلى الرسوم البيانية للاقتباس ، يتم نشر المستندات في وقت واحد ويمكن أن تشير فقط إلى المستندات القديمة.
في بعض الأحيان لا ترتبط الأحداث بوقت مادي معين. شريطة أن يكون لأزواج الأحداث علاقة سببية بحتة ، أي أن الحواف تمثل العلاقات السببية بين الأحداث ، سيكون لدينا رسم بياني لا دوري موجه. على سبيل المثال ، تمثل شبكة بايز نظامًا للأحداث الاحتمالية كرؤوس في الرسم البياني غير الدوري الموجه ، حيث يمكن حساب احتمالية وقوع حدث من احتمالات أسلافها في DAG. في هذا السياق ، فإن الرسم البياني الأخلاقي لـ DAG هو الرسم البياني غير المباشر الذي تم إنشاؤه عن طريق إضافة حافة (غير موجهة) بين جميع الآباء من نفس الرأس (تسمى أحيانًا الزواج)، ثم استبدال جميع الحواف الموجهة بحواف غير موجهة. هناك نوع آخر من الرسم البياني له بنية سببية مماثلة وهو مخطط التأثير ، حيث تمثل رؤوسه إما قرارات يجب اتخاذها أو معلومات غير معروفة ، وتمثل حوافها تأثيرات سببية من رأس إلى آخر. في علم الأوبئة ، على سبيل المثال ، غالبًا ما تُستخدم هذه الرسوم البيانية لتقدير القيمة المتوقعة من الخيارات المختلفة للتدخل.
والعكس صحيح أيضا. في أي تطبيق يتم تمثيله بواسطة رسم بياني لا دوري موجه ، يوجد هيكل سببي ، إما ترتيب صريح أو وقت في المثال أو ترتيب يمكن اشتقاقه من بنية الرسم البياني. يتبع هذا لأن جميع الرسوم البيانية غير الدورية الموجهة لها ترتيب طوبولوجي ، أي أن هناك طريقة واحدة على الأقل لترتيب الرؤوس بحيث تشير جميع الحواف في نفس الاتجاه على طول هذا الترتيب.
علم الأنساب وتاريخ الإصدار
يمكن النظر إلى الأشجار العائلية على أنها رسوم بيانية غير دورية موجهة ، مع رأس لكل فرد من أفراد الأسرة وحافة لكل علاقة بين الوالدين والطفل. على الرغم من الاسم ، فإن هذه الرسوم البيانية ليست بالضرورة أشجارًا بسبب إمكانية الزواج بين الأقارب (لذا فإن الطفل له سلف مشترك من جهة الأم والأب) مما يتسبب في انهيار النسب. الرسوم البيانية للنسب الأمومي (علاقات «الأم» بين النساء) والنسب الأبوي (علاقات «الأب» بين الرجال) هي أشجار ضمن هذا الرسم البياني. نظرًا لأنه لا يمكن لأحد أن يصبح أسلافه ، فإن أشجار العائلة غير دورية.
]]
للسبب نفسه ، يحتوي تاريخ إصدار نظام التحكم في المراجعة الموزعة ، مثل Git ، بشكل عام على بنية الرسم البياني غير الدوري الموجه ، حيث يوجد رأس لكل مراجعة وحافة تربط أزواج المراجعات التي كانت مشتقة مباشرة من بعضها البعض. هذه ليست أشجارًا بشكل عام بسبب عمليات الدمج.
في العديد من الخوارزميات العشوائية في الهندسة الحسابية ، تحتفظ الخوارزمية بسجل DAG يمثل تاريخ إصدار بنية هندسية على مدار سلسلة من التغييرات في الهيكل. على سبيل المثال ، في خوارزمية تدريجية عشوائية لتثليث Delaunay ، يتغير التثليث عن طريق استبدال مثلث واحد بثلاثة مثلثات أصغر عند إضافة كل نقطة ، وعن طريق عمليات «قلب» التي تستبدل أزواج المثلثات بزوج مختلف من المثلثات. يحتوي سجل DAG لهذه الخوارزمية على رأس لكل مثلث تم إنشاؤه كجزء من الخوارزمية ، والحواف من كل مثلث إلى المثلثين أو المثلثات الثلاثة الأخرى التي تحل محله. تسمح هذه البنية بالإجابة على استعلامات موقع النقطة بكفاءة: للعثور على موقع نقطة استعلام q في تثليث Delaunay ، اتبع مسارًا في السجل DAG ، في كل خطوة ، انتقل إلى المثلث البديل الذي يحتوي على q. يجب أن يكون المثلث الأخير الذي يتم الوصول إليه في هذا المسار هو مثلث Delaunay الذي يحتوي على q.
الرسوم البيانية للاقتباس
في الرسم البياني للاقتباس ، تكون الرؤوس عبارة عن مستندات بتاريخ نشر واحد. تمثل الحواف الاقتباسات من ببليوغرافيا وثيقة ما إلى وثائق أخرى سابقة بالضرورة. يأتي المثال الكلاسيكي من الاستشهادات بين الأوراق الأكاديمية كما ورد في مقال «شبكات الأوراق العلمية» عام 1965 بقلم ديريك جيه دي سولا برايس الذي استمر في إنتاج النموذج الأول لشبكة الاستشهادات ، نموذج السعر. في هذه الحالة ، يكون عدد الاقتباسات لورقة ما هو مجرد درجة في الرأس المقابل لشبكة الاقتباس. هذا مقياس مهم في تحليل الاقتباس. تقدم أحكام المحكمة مثالاً آخر حيث يدعم القضاة استنتاجاتهم في قضية واحدة من خلال استدعاء قرارات سابقة أخرى صدرت في قضايا سابقة. يتم تقديم مثال أخير عن طريق براءات الاختراع التي يجب أن تشير إلى حالة التقنية الصناعية السابقة ، وبراءات الاختراع السابقة ذات الصلة بمطالبة البراءة الحالية. من خلال مراعاة الخصائص الخاصة للرسوم البيانية الحلقية الموجهة ، يمكن للمرء تحليل شبكات الاستشهاد بتقنيات غير متوفرة عند تحليل الرسوم البيانية العامة التي تم النظر فيها في العديد من الدراسات باستخدام تحليل الشبكة. على سبيل المثال ، يعطي الاختزال المتعدي رؤى جديدة حول توزيعات الاقتباسات الموجودة في التطبيقات المختلفة ، مع إبراز الاختلافات الواضحة في آليات إنشاء شبكات الاستشهادات في سياقات مختلفة. أسلوب آخر هو تحليل المسار الرئيسي ، والذي يتتبع روابط الاقتباس ويقترح سلاسل الاقتباس الأكثر أهمية في رسم بياني للاقتباس معين.
نموذج السعر بسيط للغاية بحيث لا يمكن أن يكون نموذجًا واقعيًا لشبكة الاستشهادات ، ولكنه بسيط بما يكفي للسماح بالحلول التحليلية لبعض خصائصها. يمكن العثور على العديد من هذه النتائج باستخدام النتائج المستمدة من النسخة غير الموجهة لنموذج السعر ، نموذج Barabási-Albert. ومع ذلك ، نظرًا لأن نموذج Price يعطي رسمًا بيانيًا لا دوريًا موجهًا ، فهو نموذج مفيد عند البحث عن الحسابات التحليلية للخصائص الفريدة للرسوم البيانية غير الدورية الموجهة. على سبيل المثال ، يتم قياس طول أطول مسار ، من العقدة رقم n المضافة إلى الشبكة إلى العقدة الأولى في الشبكة.
ضغط البيانات
يمكن أيضًا استخدام الرسوم البيانية غير الدورية الموجهة كتمثيل مضغوط لمجموعة من المتواليات. في هذا النوع من التطبيقات ، يجد المرء DAG حيث تشكل المسارات التسلسلات المحددة. عندما تشترك العديد من التسلسلات في نفس التتابعات اللاحقة ، يمكن تمثيل هذه التسلسلات اللاحقة المشتركة بجزء مشترك من DAG ، مما يسمح للتمثيل باستخدام مساحة أقل مما قد يتطلبه سرد جميع التسلسلات بشكل منفصل. على سبيل المثال ، الرسم البياني للكلمات غير الدورية الموجه عبارة عن بنية بيانات في علوم الكمبيوتر مكونة من رسم بياني لا دوري موجه بمصدر واحد ومع حواف موضحة بأحرف أو رموز ؛ تمثل المسارات من المصدر إلى الأحواض في هذا الرسم البياني مجموعة من السلاسل ، مثل الكلمات الإنجليزية. يمكن تمثيل أي مجموعة من المتتاليات كمسارات في شجرة ، من خلال تشكيل رأس شجرة لكل بادئة في التسلسل وجعل أصل إحدى هذه الرؤوس يمثل التسلسل بعنصر أقل ؛ الشجرة التي تشكلت بهذه الطريقة لمجموعة من الخيوط تسمى trie. يوفر الرسم البياني للكلمات الحلقية الموجه مساحة على مثلث من خلال السماح للمسارات بالتباعد والالتحاق مرة أخرى ، بحيث يمكن تمثيل مجموعة من الكلمات التي لها نفس اللواحق المحتملة برأس شجرة واحد.
تحدث نفس فكرة استخدام DAG لتمثيل مجموعة من المسارات في مخطط القرار الثنائي ، وهي بنية بيانات قائمة على DAG لتمثيل الوظائف الثنائية. في الرسم التخطيطي للقرار الثنائي ، تتم تسمية كل رأس غير حوضي باسم متغير ثنائي ، ويتم تسمية كل حوض وكل حافة بالرقم 0 أو 1. قيمة الوظيفة لأي تعيين حقيقة للمتغيرات هي القيمة عند تم العثور على الحوض باتباع مسار ، بدءًا من رأس المصدر الفردي ، والذي يتبع الحافة الصادرة عند كل قمة غير مغسلة للحافة الصادرة المسمى بقيمة متغير هذا الرأس. تمامًا كما يمكن عرض الرسوم البيانية للكلمات غير الدورية الموجهة باعتبارها شكلًا مضغوطًا من المحاولات ، يمكن عرض مخططات القرار الثنائي على أنها أشكال مضغوطة من أشجار القرار التي توفر مساحة من خلال السماح للمسارات بالانضمام عندما تتفق على نتائج جميع القرارات المتبقية.
تؤدي إضافة الحواف الحمراء إلى الرسم البياني غير الدوري الموجه باللون الأزرق إلى إنتاج DAG آخر ، وهو الإغلاق الانتقالي للرسم البياني الأزرق. لكل حافة حمراء أو زرقاء uv ، يمكن الوصول إلى v من u: يوجد مسار أزرق يبدأ من u وينتهي عند v.}}.
يمثل مخطط Hasse الترتيب الجزئي لتضمين المجموعة (⊆) بين المجموعات الفرعية لمجموعة من ثلاثة عناصر..
الرسم البياني غير الدوري الموجه باللون الأصفر هو تكثيف الرسم البياني الأزرق الموجه. يتم تشكيله عن طريق التعاقد مع كل مكون متصل بقوة من الرسم البياني الأزرق في رأس أصفر واحد..
مخطط PERT لمشروع يحتوي على خمسة معالم (مسماة 10-50) وست مهام (معنون A – F). هناك مساران حرجان ، ADF و BC..
شجرة عائلة سلالة البطالمة ، مع العديد من الزيجات بين الأقارب مما تسبب في انهيار النسب