النظام ما قبل الطوبولوجي
في مجال علوم الحاسوب ، يُعرف الترتيب ما قبل الطوبولوجي للرسم البياني الموجه بأنه ترتيب خطي لرؤوسه بحيث إذا كان هناك مسار موجه من الرأس u إلى الرأس v وكان v يسبق u في الترتيب، فإنه يوجد أيضًا مسار موجه من الرأس v إلى الرأس u . [ 1 ] [ 2 ]
إذا كان الرسم البياني رسمًا بيانيًا موجهًا غير دوري (DAG)، فإن الترتيبات الطوبولوجية هي ترتيبات ما قبل الطوبولوجية والعكس صحيح. [ 1 ] في الحالات الأخرى، أي ترتيب ما قبل الطوبولوجي يعطي ترتيبًا جزئيًا .
مراجع
- 1 2 شريجفر، ألكسندر (10-12-2002). التحسين التوافقي: متعددات السطوح والكفاءة . سبرينغر ساينس آند بيزنس ميديا. ص 89. ISBN 9783540443896.
- ↑ سيدجويك، روبرت ؛ واين، كيفن (26-09-2016). "الرسوم البيانية الموجهة" . الخوارزميات، الطبعة الرابعة . تم الاسترجاع في 06-09-2017 .
فئات :
- خوارزميات الرسوم البيانية
- خوارزميات الفرز
- الرسوم البيانية الموجهة