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

داغ

اختزالها المتعدي

يمكن صياغة علاقة الوصول في الرسم البياني الموجه غير الدوري (DAG) كترتيب جزئي ≤ على رؤوس الرسم البياني. في هذا الترتيب الجزئي، يكون ترتيب رأسين u و v كالتالي: u ≤ v، وذلك عندما يوجد مسار موجه من u إلى v في الرسم البياني؛ أي عندما يكون u قادرًا على الوصول إلى v (أو عندما يكون v قابلًا للوصول من u ). ^{[ 4 ]} مع ذلك، قد تُنتج رسوم بيانية موجهة غير دورية مختلفة نفس علاقة الوصول ونفس الترتيب الجزئي. ^{[ 5 ]} على سبيل المثال، الرسم البياني الموجه غير الدوري ذو الحافتين u → v و v → w له نفس علاقة الوصول التي للرسم البياني الموجه غير الدوري ذي الحواف الثلاث u → v و v → w و u → w . ينتج كلا الرسمين البيانيين الموجهين غير الدوريين نفس الترتيب الجزئي، حيث تكون الرؤوس مرتبة كالتالي: u ≤ v ≤ w .

يُعرَّف الإغلاق المتعدي للرسم البياني الموجه غير الدوري (DAG) بأنه الرسم البياني الذي يحتوي على أكبر عدد من الحواف ويتمتع بنفس علاقة الوصول الخاصة بالرسم البياني الموجه غير الدوري. يحتوي هذا الإغلاق على حافة u → v لكل زوج من الرؤوس ( u , v ) في علاقة الوصول ≤ الخاصة بالرسم البياني الموجه غير الدوري، وبالتالي يمكن اعتباره ترجمة مباشرة لعلاقة الوصول ≤ إلى مصطلحات نظرية الرسم البياني. وينطبق أسلوب ترجمة الترتيبات الجزئية إلى رسوم بيانية موجهة غير دورية بشكل أعم: فلكل مجموعة مرتبة جزئيًا منتهية ( S , ≤) ، يكون الرسم البياني الذي يحتوي على رأس لكل عنصر من S وحافة لكل زوج من العناصر في ≤ رسمًا بيانيًا موجهًا غير دوري مغلقًا متعديًا تلقائيًا، وتكون علاقة الوصول الخاصة به هي ( S , ≤) . وبهذه الطريقة، يمكن تمثيل كل مجموعة مرتبة جزئيًا منتهية برسم بياني موجه غير دوري.

الاختزال المتعدي للرسم البياني الموجه غير الدوري (DAG) هو الرسم البياني ذو أقل عدد من الحواف والذي يتمتع بنفس علاقة الوصول للرسم البياني الموجه غير الدوري. يحتوي هذا الاختزال على حافة u → v لكل زوج من الرؤوس ( u , v ) في علاقة التغطية لعلاقة الوصول ≤ للرسم البياني الموجه غير الدوري. وهو رسم بياني فرعي من الرسم البياني الموجه غير الدوري، يتكون من حذف الحواف u → v التي يحتوي الرسم البياني الموجه غير الدوري أيضًا على مسار موجه أطول من u إلى v . ومثل الإغلاق المتعدي، فإن الاختزال المتعدي مُعرَّف بشكل فريد للرسوم البيانية الموجهة غير الدورية. في المقابل، بالنسبة للرسم البياني الموجه غير الدوري، يمكن أن يكون هناك أكثر من رسم بياني فرعي أدنى واحد له نفس علاقة الوصول. ^{[ 6 ]} تُعد الاختزالات المتعدية مفيدة في تصور الترتيبات الجزئية التي تُمثلها، لأنها تحتوي على عدد أقل من الحواف مقارنةً بالرسوم البيانية الأخرى التي تُمثل نفس الترتيبات، وبالتالي تؤدي إلى رسومات بيانية أبسط . مخطط هاس للترتيب الجزئي هو رسم للاختزال المتعدي حيث يتم إظهار اتجاه كل حافة عن طريق وضع رأس البداية للحافة في موضع أدنى من رأس النهاية. ^{[ 7 ]}

الترتيب الطوبولوجي للرسم البياني الموجه غير الدوري: كل حافة تنتقل من الجزء العلوي الأيسر (الأقدم) إلى الجزء السفلي الأيمن (الأحدث). يكون الرسم البياني الموجه غير دوري إذا وفقط إذا كان له ترتيب طوبولوجي.

بإضافة الحواف الحمراء إلى الرسم البياني الأزرق الموجه غير الدوري، ينتج رسم بياني موجه غير دوري آخر، وهو الإغلاق المتعدي للرسم البياني الأزرق. لكل حافة حمراء أو زرقاء u → v ، يمكن الوصول إلى v من u : يوجد مسار أزرق يبدأ من u وينتهي عند v .

الترتيب الطوبولوجي للرسم البياني الموجه هو ترتيب رؤوسه في تسلسل، بحيث يكون رأس بداية كل حافة في التسلسل يسبق رأس نهايتها. لا يمكن أن يحتوي الرسم البياني ذو الترتيب الطوبولوجي على أي دورات، لأن الحافة المؤدية إلى أول رأس في الدورة ستكون موجهة في الاتجاه الخاطئ. لذلك، كل رسم بياني ذو ترتيب طوبولوجي هو رسم بياني غير دوري. وعلى العكس، كل رسم بياني موجه غير دوري له ترتيب طوبولوجي واحد على الأقل. وبالتالي، يمكن استخدام وجود الترتيب الطوبولوجي كتعريف مكافئ للرسوم البيانية الموجهة غير الدورية: فهي تحديدًا الرسوم البيانية التي لها ترتيبات طوبولوجية. ^{[ 2 ]} بشكل عام، هذا الترتيب ليس فريدًا؛ فالرسم البياني الموجه غير الدوري له ترتيب طوبولوجي فريد إذا وفقط إذا كان لديه مسار موجه يحتوي على جميع الرؤوس، وفي هذه الحالة يكون الترتيب هو نفسه ترتيب ظهور الرؤوس في المسار. ^{[ 8 ]}

إن عائلة الترتيبات الطوبولوجية لـ DAG هي نفسها عائلة الامتدادات الخطية لعلاقة الوصول لـ DAG، ^{[ 9 ]} لذلك فإن أي رسمين بيانيين يمثلان نفس الترتيب الجزئي لهما نفس مجموعة الترتيبات الطوبولوجية.

درس روبنسون (1973) مسألة تعداد الرسوم البيانية الموجهة غير الدورية . ^{[ 10 ]} عدد الرسوم البيانية الموجهة غير الدورية التي تحتوي على n رأسًا مُصنَّفة، حيث n = 0، 1، 2، 3، ... (دون قيود على ترتيب ظهور هذه الأرقام في الترتيب الطوبولوجي للرسم البياني الموجه غير الدوري) هو  

1، 1، 3، 25، 543، 29281، 3781503، ... (التسلسل A003024 في OEIS ) .

يمكن حساب هذه الأرقام من خلال علاقة التكرار

${\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(nk)}a_{nk}.}$^{[ 10 ]}

افترض إريك و. وايسشتاين ، ^{[ 11 ]} وأثبت مكاي وآخرون (2004) ، أن نفس الأرقام تُستخدم لحساب المصفوفات (0,1) التي تكون جميع قيمها الذاتية أعدادًا حقيقية موجبة . البرهان تقابلي : المصفوفة A هي مصفوفة تجاور لرسم بياني موجه غير دوري (DAG) إذا وفقط إذا كانت A  + I  مصفوفة (0,1) ذات جميع قيم ذاتية موجبة، حيث I هي مصفوفة الوحدة . ولأن الرسم البياني الموجه غير الدوري لا يمكن أن يحتوي على حلقات ذاتية ، يجب أن يكون قطر مصفوفة تجاوره صفريًا، لذا فإن إضافة I تحافظ على خاصية أن جميع معاملات المصفوفة إما 0 أو 1. ^{[ 12 ]}

الشجرة المتعددة ، وهي رسم بياني موجه غير دوري (DAG) حيث يؤدي الرسم البياني الفرعي الذي يمكن الوصول إليه من أي رأس إلى إنشاء شجرة غير موجهة (على سبيل المثال باللون الأحمر).

الشجرة المتعددة ، وهي رسم بياني موجه غير دوري يتكون من توجيه حواف شجرة غير موجهة

الشجرة المتعددة (وتسمى أيضاً الرسم البياني غير المبهم بقوة أو شجرة المانغروف ) هي رسم بياني موجه غير دوري (DAG) يوجد فيه مسار موجه واحد على الأكثر بين أي رأسين. وبصورة مكافئة، هي رسم بياني موجه غير دوري (DAG) يكون فيه الرسم البياني الفرعي الذي يمكن الوصول إليه من أي رأس شجرة غير موجهة . ^{[ 13 ]}

الشجرة المتعددة (وتسمى أيضًا الشجرة الموجهة ) هي شجرة متعددة تتكون من خلال توجيه حواف شجرة غير موجهة. ^{[ 14 ]}

التفرع الشجري هو شجرة متعددة تتكون من خلال توجيه حواف شجرة غير موجهة بعيدًا عن رأس معين يسمى جذر التفرع الشجري.

يُعدّ الترتيب الطوبولوجي مسألةً خوارزميةً لإيجاد ترتيب طوبولوجي لرسم بياني موجه غير دوري (DAG) مُعطى. ويمكن حلّها في زمن خطي . ^{[ 15 ]} تقوم خوارزمية كان للترتيب الطوبولوجي ببناء ترتيب الرؤوس مباشرةً. إذ تحتفظ بقائمة من الرؤوس التي لا تتصل بأي حواف من رؤوس أخرى لم تُضَمَّن بعد في الترتيب الطوبولوجي المُنشأ جزئيًا؛ وتتكون هذه القائمة مبدئيًا من الرؤوس التي لا تتصل بأي حواف على الإطلاق. ثم تُضيف الخوارزمية رأسًا واحدًا من هذه القائمة بشكل متكرر إلى نهاية الترتيب الطوبولوجي المُنشأ جزئيًا، وتتحقق مما إذا كان ينبغي إضافة جيرانه إلى القائمة. وتنتهي الخوارزمية عند معالجة جميع الرؤوس بهذه الطريقة. ^{[ 16 ]} بدلاً من ذلك، يمكن بناء ترتيب طوبولوجي عن طريق عكس ترقيم ما بعد الترتيب لاجتياز الرسم البياني باستخدام خوارزمية البحث العميق أولاً . ^{[ 15 ]}

من الممكن أيضًا التحقق مما إذا كان الرسم البياني الموجه المعطى هو رسم بياني موجه غير دوري (DAG) في وقت خطي، إما عن طريق محاولة إيجاد ترتيب طوبولوجي ثم اختبار كل حافة لمعرفة ما إذا كان الترتيب الناتج صحيحًا ^{[ 17 ]} أو بدلاً من ذلك، بالنسبة لبعض خوارزميات الفرز الطوبولوجي، عن طريق التحقق من أن الخوارزمية ترتب جميع الرؤوس بنجاح دون الوقوع في حالة خطأ. ^{[ 16 ]}

يمكن تحويل أي رسم بياني غير موجه إلى رسم بياني موجه غير دوري (DAG) باختيار ترتيب كلي لرؤوسه وتوجيه كل حافة من نقطة البداية في الترتيب إلى نقطة النهاية اللاحقة. يُسمى التوجيه الناتج للحواف بالتوجيه غير الدوري . قد تؤدي ترتيبات كلية مختلفة إلى نفس التوجيه غير الدوري، لذا يمكن أن يحتوي رسم بياني ذو n رأس على أقل من n ! توجيهًا غير دوري. عدد التوجيهات غير الدورية يساوي | χ (−1) | ، حيث χ هي متعددة الحدود اللونية للرسم البياني المعطى. ^{[ 18 ]}

يمكن تحويل أي رسم بياني موجه إلى رسم بياني موجه غير دوري (DAG) عن طريق إزالة مجموعة رؤوس التغذية الراجعة أو مجموعة أقواس التغذية الراجعة ، وهي مجموعة من الرؤوس أو الحواف (على التوالي) التي تلامس جميع الدورات. مع ذلك، فإن إيجاد أصغر مجموعة من هذا النوع يُعدّ مسألة صعبة الحل (NP-hard ). ^{[ 19 ]} كما يمكن تحويل أي رسم بياني موجه إلى رسم بياني موجه غير دوري (DAG)، يُسمى تكثيفه ، عن طريق دمج كل مكون من مكوناته المتصلة بقوة في رأس فائق واحد. ^{[ 20 ]} عندما يكون الرسم البياني غير دوري بالفعل، تكون أصغر مجموعات رؤوس التغذية الراجعة ومجموعات أقواس التغذية الراجعة فارغة ، ويكون تكثيفه هو الرسم البياني نفسه.

يمكن إنشاء الإغلاق المتعدي لرسم بياني موجه غير دوري (DAG) ذي n رأسًا و m حافة في زمن O ( mn ) باستخدام البحث بالعرض أولًا أو البحث بالعمق أولًا لاختبار إمكانية الوصول من كل رأس. ^{[ 21 ]} بدلاً من ذلك ، يمكن حله في زمن O ( nω ⁾ حيث ω  <  2.373 هو أس خوارزميات ضرب المصفوفات ؛ وهذا يُعد تحسينًا نظريًا على الحد O ( mn ) للرسوم البيانية الكثيفة . ^{[ 22 ]}

في جميع خوارزميات الإغلاق المتعدي هذه، يمكن التمييز بين أزواج الرؤوس التي يمكن الوصول إليها عبر مسار واحد على الأقل بطول اثنين أو أكثر، وأزواج الرؤوس التي لا يمكن ربطها إلا بمسار طوله واحد. يتكون الاختزال المتعدي من الحواف التي تُشكل مسارات طولها واحد، وهي المسارات الوحيدة التي تربط نقاط نهايتها. لذلك، يمكن إنشاء الاختزال المتعدي ضمن نفس الحدود الزمنية التقاربية للإغلاق المتعدي. ^{[ 23 ]}

تأخذ مسألة الإغلاق كمدخل رسمًا بيانيًا موجهًا غير دوري مُثقَّل الرؤوس، وتسعى إلى إيجاد الحد الأدنى (أو الأقصى) لوزن الإغلاق - مجموعة من الرؤوس C - بحيث لا تغادر أي حافة من C. يمكن صياغة المسألة للرسوم البيانية الموجهة دون افتراض عدم الدورية، ولكن دون مزيد من التعميم، لأنها في هذه الحالة تُكافئ المسألة نفسها على تكثيف الرسم البياني. يمكن حلها في وقت متعدد الحدود باستخدام اختزال إلى مسألة التدفق الأقصى . ^{[ 24 ]}

تصبح بعض الخوارزميات أبسط عند استخدامها على الرسوم البيانية الموجهة غير الدورية (DAGs) بدلاً من الرسوم البيانية العامة، وذلك استنادًا إلى مبدأ الترتيب الطوبولوجي. على سبيل المثال، من الممكن إيجاد أقصر المسارات وأطولها من رأس بداية مُعطى في الرسوم البيانية الموجهة غير الدورية في زمن خطي، وذلك بمعالجة الرؤوس بترتيب طوبولوجي ، وحساب طول المسار لكل رأس ليكون أقصر أو أطول طول مُمكن الحصول عليه عبر أي من حوافه الواردة. ^{[ 25 ]} في المقابل، بالنسبة للرسوم البيانية العشوائية، قد يتطلب إيجاد أقصر مسار خوارزميات أبطأ مثل خوارزمية ديكسترا أو خوارزمية بيلمان-فورد ، ^{[ 26 ]} كما أن إيجاد أطول المسارات في الرسوم البيانية العشوائية يُعدّ مسألة صعبة الحل (NP-hard) . ^{[ 27 ]}

تُستخدم تمثيلات الرسوم البيانية الموجهة غير الدورية للترتيبات الجزئية في العديد من تطبيقات جدولة أنظمة المهام ذات قيود الترتيب. ^{[ 28 ]} وتتعلق فئة مهمة من هذه المشكلات بمجموعات الكائنات التي تحتاج إلى التحديث، مثل خلايا جدول البيانات بعد تغيير إحدى هذه الخلايا، أو ملفات كائنات برنامج حاسوبي بعد تغيير شفرته المصدرية . في هذا السياق، يُعرف مخطط التبعية بأنه مخطط يحتوي على رأس لكل كائن مطلوب تحديثه، وحافة تربط بين كائنين عندما يحتاج أحدهما إلى التحديث قبل الآخر. تُسمى الدورة في هذا المخطط بالتبعية الدائرية ، وهي غير مسموح بها عمومًا، لأنه لا توجد طريقة لجدولة المهام المتضمنة في الدورة بشكل متسق. تُشكل مخططات التبعية الخالية من التبعيات الدائرية مخططات DAG. ^{[ 29 ]}

على سبيل المثال، عند تغيير قيمة خلية واحدة في جدول بيانات ، يلزم إعادة حساب قيم الخلايا الأخرى التي تعتمد بشكل مباشر أو غير مباشر على الخلية المتغيرة. في هذه الحالة، تتمثل المهام المطلوب جدولتها في إعادة حساب قيم الخلايا الفردية في جدول البيانات. تنشأ التبعيات عندما يستخدم تعبير في خلية ما قيمة من خلية أخرى. في هذه الحالة، يجب إعادة حساب القيمة المستخدمة قبل التعبير الذي يستخدمها. يسمح الترتيب الطوبولوجي لمخطط التبعية، واستخدام هذا الترتيب الطوبولوجي لجدولة تحديثات الخلايا، بتحديث جدول البيانات بالكامل بتقييم واحد فقط لكل خلية. ^{[ 30 ]} تظهر مشاكل مماثلة لترتيب المهام في ملفات التجميع البرمجية ^{[ 30 ]} وجدولة التعليمات لتحسين برامج الحاسوب منخفضة المستوى. ^{[ 31 ]}

تستخدم تقنية تقييم ومراجعة البرامج (PERT)، وهي طريقة لإدارة المشاريع البشرية الكبيرة وتُعدّ من أوائل تطبيقات الرسوم البيانية الموجهة غير الدورية (DAGs)، صياغةً مختلفةً نوعًا ما لقيود الجدولة. في هذه الطريقة، تمثل رؤوس الرسم البياني الموجه غير الدوري مراحل المشروع الرئيسية بدلًا من المهام المحددة المطلوب تنفيذها. بدلًا من ذلك، تُمثَّل المهمة أو النشاط بحافة في الرسم البياني، تربط بين مرحلتين رئيسيتين تُشيران إلى بداية المهمة ونهايتها. تُصنَّف كل حافة من هذه الحواف بتقدير للوقت الذي سيستغرقه فريق من العمال لإنجاز المهمة. يُمثل أطول مسار في هذا الرسم البياني الموجه غير الدوري المسار الحرج للمشروع، وهو المسار الذي يتحكم في إجمالي وقت المشروع. يمكن جدولة المراحل الرئيسية الفردية وفقًا لأطوال أطول المسارات التي تنتهي عند رؤوسها. ^{[ 32 ]}

يمكن استخدام الرسم البياني الموجه غير الدوري لتمثيل شبكة من عناصر المعالجة. في هذا التمثيل، تدخل البيانات إلى عنصر المعالجة من خلال حوافها الواردة وتخرج منه من خلال حوافها الصادرة.

على سبيل المثال، في تصميم الدوائر الإلكترونية، يمكن تمثيل وحدات المنطق التوافقي الثابتة كنظام غير دوري من البوابات المنطقية التي تحسب دالة لمدخل، حيث يُمثل كل من مدخل ومخرج الدالة بتات منفصلة . عمومًا، لا يمكن استخدام مخرج هذه الوحدات كمدخل إلا إذا تم التقاطه بواسطة مسجل أو عنصر حالة يحافظ على خصائصه غير الدورية. ^{[ 33 ]} تُعد مخططات الدوائر الإلكترونية، سواءً على الورق أو في قاعدة البيانات، شكلًا من أشكال الرسوم البيانية الموجهة غير الدورية، حيث تستخدم مثيلات أو مكونات لتكوين مرجع موجه إلى مكون أدنى مستوى. مع ذلك، فإن الدوائر الإلكترونية نفسها ليست بالضرورة غير دورية أو موجهة.

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

في المترجمات ، يمكن تمثيل الشيفرة الخطية (أي تسلسلات التعليمات البرمجية بدون حلقات أو فروع شرطية) بواسطة رسم بياني موجه غير دوري (DAG) يصف مدخلات ومخرجات كل عملية حسابية تُنفذ داخل الشيفرة. يُمكّن هذا التمثيل المترجم من حذف التعبيرات الفرعية المتكررة بكفاءة. ^{[ 35 ]} على مستوى أعلى من تنظيم الشيفرة، ينص مبدأ التبعيات غير الدورية على أن التبعيات بين وحدات أو مكونات نظام برمجي كبير يجب أن تُشكل رسمًا بيانيًا موجهًا غير دوري. ^{[ 36 ]}

تُعد الشبكات العصبية ذات التغذية الأمامية مثالاً آخر.

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

أحيانًا لا ترتبط الأحداث بوقتٍ فيزيائي محدد. إذا كانت أزواج الأحداث تربطها علاقة سببية بحتة، أي أن الحواف تمثل علاقات سببية بين الأحداث، فسنحصل على رسم بياني موجه غير دوري. ^{[ 37 ]} على سبيل المثال، تمثل الشبكة البايزية نظامًا من الأحداث الاحتمالية كرؤوس في رسم بياني موجه غير دوري، حيث يمكن حساب احتمالية وقوع حدث ما من احتمالات وقوع أحداث سابقة له في الرسم البياني الموجه غير الدوري. ^{[ 38 ]} في هذا السياق، يُعد الرسم البياني الأخلاقي للرسم البياني الموجه غير الدوري هو الرسم البياني غير الموجه الذي يتم إنشاؤه بإضافة حافة (غير موجهة) بين جميع آباء نفس الرأس (يُطلق عليها أحيانًا " الزواج ")، ثم استبدال جميع الحواف الموجهة بحواف غير موجهة. ^{[ 39 ]} نوع آخر من الرسوم البيانية ذات بنية سببية مماثلة هو مخطط التأثير ، حيث تمثل رؤوسه إما قرارات يجب اتخاذها أو معلومات غير معروفة، وتمثل حوافه تأثيرات سببية من رأس إلى آخر. ^{[ 40 ]} في علم الأوبئة ، على سبيل المثال، تُستخدم هذه المخططات غالبًا لتقدير القيمة المتوقعة لخيارات التدخل المختلفة. ^{[ 41 ] [ 42 ]}

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

يمكن اعتبار شجرة العائلة بمثابة رسوم بيانية موجهة غير دورية، حيث يمثل كل رأس فردًا من أفراد العائلة، ويمثل كل ضلع علاقة بين الأب والابن. ^{[ 43 ]} على الرغم من التسمية، فإن هذه الرسوم البيانية ليست بالضرورة أشجارًا، نظرًا لاحتمالية حدوث زيجات بين الأقارب (بحيث يكون للطفل سلف مشترك من جهة الأم والأب)، مما قد يؤدي إلى انهيار شجرة النسب . ^{[ 44 ]} تُعد رسوم النسب الأمومي (علاقات الأم والابنة) والنسب الأبوي (علاقات الأب والابن) أشجارًا ضمن هذا الرسم البياني. ولأنه لا يمكن لأحد أن يصبح سلفًا لنفسه، فإن شجرة العائلة غير دورية. ^{[ 45 ]}

عادةً ما يكون سجل الإصدارات لنظام تحكم في المراجعات الموزعة ، مثل Git ، على شكل رسم بياني موجه غير دوري، حيث يوجد رأس لكل مراجعة وحافة تربط أزواج المراجعات المشتقة مباشرةً من بعضها البعض. ولا تُشكل هذه الرسوم البيانية أشجارًا بشكل عام بسبب عمليات الدمج. ^{[ 46 ]}

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

في مخطط الاستشهادات، تمثل الرؤوس الوثائق ذات تاريخ النشر الواحد. أما الحواف فتمثل الاستشهادات من مراجع وثيقة ما إلى وثائق أخرى سابقة لها بالضرورة. المثال الكلاسيكي هو الاستشهادات بين الأوراق البحثية، كما ورد في مقالة "شبكات الأوراق العلمية" عام 1965 ^{[ 48 ]} لديريك ج. دي سولا برايس، الذي وضع لاحقًا أول نموذج لشبكة الاستشهادات، وهو نموذج برايس ^{[ 49 ]} . في هذه الحالة، يمثل عدد الاستشهادات بورقة بحثية درجة الدخول للرأس المقابل في شبكة الاستشهادات. وهذا مقياس مهم في تحليل الاستشهادات . تقدم الأحكام القضائية مثالًا آخر، حيث يدعم القضاة استنتاجاتهم في قضية ما بالرجوع إلى قرارات سابقة صادرة في قضايا سابقة. وأخيرًا، تقدم براءات الاختراع مثالًا آخر، إذ يجب أن تشير إلى براءات اختراع سابقة ذات صلة بمطالبة براءة الاختراع الحالية. بمراعاة الخصائص المميزة للرسوم البيانية الموجهة غير الدورية، يُمكن تحليل شبكات الاستشهاد بتقنيات غير متاحة عند تحليل الرسوم البيانية العامة التي تُعتبر موضوعًا للعديد من الدراسات التي تستخدم تحليل الشبكات . على سبيل المثال، يُقدم الاختزال المتعدي رؤى جديدة حول توزيعات الاستشهاد الموجودة في تطبيقات مختلفة، مُسلطًا الضوء على اختلافات واضحة في آليات إنشاء شبكات الاستشهاد في سياقات مختلفة. ^{[ 50 ]} ومن التقنيات الأخرى تحليل المسار الرئيسي ، الذي يتتبع روابط الاستشهاد ويقترح سلاسل الاستشهاد الأكثر أهمية في رسم بياني للاستشهاد مُعطى .

يُعدّ نموذج برايس بسيطًا للغاية بحيث لا يُمكن اعتباره نموذجًا واقعيًا لشبكة الاستشهادات، ولكنه بسيط بما يكفي للسماح بإيجاد حلول تحليلية لبعض خصائصه. يُمكن إيجاد العديد من هذه الحلول باستخدام نتائج مُستمدة من النسخة غير المُوجّهة من نموذج برايس ، وهي نموذج باراباسي-ألبرت . مع ذلك، ولأن نموذج برايس يُنتج رسمًا بيانيًا مُوجّهًا غير دوري، فهو نموذج مفيد عند البحث عن حسابات تحليلية لخصائص فريدة للرسوم البيانية المُوجّهة غير الدورية. على سبيل المثال، يتناسب طول أطول مسار، من العقدة رقم n المُضافة إلى الشبكة إلى العقدة الأولى فيها، مع ^{[ 51 ].}${\displaystyle \ln(n)}$.

يمكن استخدام الرسوم البيانية الموجهة غير الدورية كتمثيل مُختصر لمجموعة من المتتاليات. في هذا النوع من التطبيقات، نجد رسمًا بيانيًا موجهًا غير دوري (DAG) تُشكّل مساراته المتتاليات المُعطاة. عندما تشترك العديد من المتتاليات في نفس المتتاليات الفرعية، يُمكن تمثيل هذه المتتاليات الفرعية المشتركة بجزء مشترك من الرسم البياني الموجه غير الدوري، مما يسمح باستخدام مساحة أقل من تلك اللازمة لسرد جميع المتتاليات بشكل منفصل. على سبيل المثال، يُعد الرسم البياني الموجه غير الدوري للكلمات بنية بيانات في علوم الحاسوب تتكون من رسم بياني موجه غير دوري بمصدر واحد وحواف مُصنّفة بأحرف أو رموز؛ تُمثل المسارات من المصدر إلى الوجهات في هذا الرسم البياني مجموعة من السلاسل النصية ، مثل الكلمات الإنجليزية. ^{[ 52 ]} يُمكن تمثيل أي مجموعة من المتتاليات كمسارات في شجرة، وذلك بتكوين رأس شجرة لكل بادئة من المتتالية وجعل الأصل لأحد هذه الرؤوس يُمثل المتتالية التي تحتوي على عنصر أقل؛ تُسمى الشجرة المُشكّلة بهذه الطريقة لمجموعة من السلاسل النصية "شجرة ثلاثية" (Trie ).

وبالمثل، يمكن اعتبار شجرة البحث الثنائية بمثابة رسم بياني موجه غير دوري (DAG) ذي جذر، حيث تمثل المسارات ترتيبات مرتبة للمفاتيح، على الرغم من أنها تفتقر إلى ضغط دمج المسارات الموجود في الرسوم البيانية الموجهة غير الدورية الأكثر تعقيدًا. ^{[ 53 ]} يوفر الرسم البياني الموجه غير الدوري للكلمات مساحةً مقارنةً بشجرة البحث من خلال السماح للمسارات بالتباعد وإعادة الاتصال، بحيث يمكن تمثيل مجموعة من الكلمات ذات اللواحق الممكنة نفسها برأس شجرة واحد. ^{[ 54 ]}

تُستخدم الفكرة نفسها المتمثلة في استخدام الرسم البياني الموجه غير الدوري (DAG) لتمثيل مجموعة من المسارات في مخطط القرار الثنائي ، ^{[ 55 ] [ 56 ]} وهو بنية بيانات قائمة على الرسم البياني الموجه غير الدوري لتمثيل الدوال الثنائية. في مخطط القرار الثنائي، يُسمى كل رأس غير مصب باسم متغير ثنائي، ويُسمى كل مصب وكل حافة بالرقم 0 أو 1. قيمة الدالة لأي تعيين منطقي للمتغيرات هي القيمة عند المصب التي يتم العثور عليها باتباع مسار، بدءًا من رأس المصدر الوحيد، والذي يتبع عند كل رأس غير مصب الحافة الخارجة التي تحمل قيمة متغير ذلك الرأس. وكما يمكن اعتبار الرسوم البيانية الموجهة غير الدورية للكلمات شكلاً مضغوطًا من أشجار القرار ، يمكن اعتبار مخططات القرار الثنائية أشكالاً مضغوطة من أشجار القرار التي توفر المساحة من خلال السماح للمسارات بالالتحام مرة أخرى عندما تتفق على نتائج جميع القرارات المتبقية. ^{[ 57 ]}