الرسم البياني الضمني

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

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

يتم تعريف كل رأس من رؤوس الرسم البياني الضمني بواسطة مربع على اللوحة، وكل حافة هي حركة في جولة الفارس .

تمثيلات الأحياء

يُعدّ مفهوم الرسم البياني الضمني شائعًا في العديد من خوارزميات البحث التي تُوصف باستخدام الرسوم البيانية. في هذا السياق، يُمكن تعريف الرسم البياني الضمني على أنه مجموعة من القواعد لتحديد جميع الجيران لأي رأس مُحدد. [ 1 ] يُشابه هذا النوع من تمثيل الرسم البياني الضمني قائمة التجاور ، حيث يُتيح الوصول بسهولة إلى جيران كل رأس. على سبيل المثال، عند البحث عن حلٍّ للغز مثل مكعب روبيك ، يُمكن تعريف رسم بياني ضمني يُمثل فيه كل رأس إحدى الحالات المُمكنة للمكعب، ويُمثل كل ضلع حركة من حالة إلى أخرى. من السهل توليد جيران أي رأس من خلال تجربة جميع الحركات المُمكنة في اللغز وتحديد الحالات التي تصل إليها كل حركة؛ ومع ذلك، فإن التمثيل الضمني ضروري، لأن فضاء حالات مكعب روبيك كبير جدًا بحيث لا يسمح لأي خوارزمية بسرد جميع حالاته. [ 2 ]

في نظرية التعقيد الحسابي ، تم تعريف عدة فئات تعقيد مرتبطة بالرسوم البيانية الضمنية، والتي تُعرَّف كما سبق بقاعدة أو خوارزمية لسرد جيران رأس معين. على سبيل المثال، PPA هي فئة من المسائل التي يُعطى فيها كمدخل رسم بياني ضمني غير موجه (حيث تكون الرؤوس عبارة عن سلاسل ثنائية مكونة من n بت، مع خوارزمية زمنية متعددة الحدود لسرد جيران أي رأس) ورأس ذي درجة فردية في الرسم البياني، ويجب إيجاد رأس ثانٍ ذي درجة فردية. وفقًا لمبدأ المصافحة ، يوجد مثل هذا الرأس؛ إيجاده مشكلة في فئة NP ، ولكن المسائل التي يمكن تعريفها بهذه الطريقة قد لا تكون بالضرورة كاملة من فئة NP ، حيث أنه من غير المعروف ما إذا كانت PPA  =  NP. PPAD هي فئة مماثلة مُعرَّفة على الرسوم البيانية الموجهة الضمنية ، وقد حظيت باهتمام في نظرية الألعاب الخوارزمية لأنها تتضمن مشكلة حساب توازن ناش . [ 3 ] يمكن أيضًا استخدام مشكلة اختبار إمكانية الوصول من رأس إلى آخر في رسم بياني ضمني لتوصيف فئات التعقيد غير الحتمي المحدودة مكانيًا، بما في ذلك NL (فئة المشكلات التي يمكن توصيفها بإمكانية الوصول في الرسوم البيانية الموجهة الضمنية التي تتكون رؤوسها من سلاسل بتات O(log n ) )، و SL (الفئة المماثلة للرسوم البيانية غير الموجهة)، و PSPACE (فئة المشكلات التي يمكن توصيفها بإمكانية الوصول في الرسوم البيانية الضمنية ذات سلاسل البتات ذات الطول متعدد الحدود). في هذا السياق النظري للتعقيد، قد تمثل رؤوس الرسم البياني الضمني حالات آلة تورينج غير حتمية ، وقد تمثل الحواف انتقالات الحالة الممكنة، ولكن يمكن أيضًا استخدام الرسوم البيانية الضمنية لتمثيل العديد من أنواع البنية التوافقية الأخرى. [ 4 ] PLS ، وهي فئة تعقيد أخرى، تجسد تعقيد إيجاد الحلول المثلى المحلية في رسم بياني ضمني. [ 5 ]

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

مخططات تسمية الجوار

في سياق التمثيل الفعال للرسوم البيانية، عرّف جيه إتش مولر بنية محلية أو مخططًا لترقيم التجاور للرسم البياني G في عائلة معينة F من الرسوم البيانية، وذلك بتخصيص مُعرّف من O (log n ) بت لكل رأس من رؤوس G ، بالإضافة إلى خوارزمية (قد تعتمد على F ولكنها مستقلة عن الرسم البياني G نفسه ) تأخذ مُعرّفَي رأس كمدخلات وتحدد ما إذا كانا طرفي حافة في G أم لا . أي أن هذا النوع من التمثيل الضمني يُشابه مصفوفة التجاور : فمن السهل التحقق مما إذا كان رأسان متجاورين، ولكن إيجاد جيران أي رأس قد يتطلب المرور على جميع الرؤوس واختبار أيها جيران. [ 7 ]

تتضمن عائلات الرسوم البيانية ذات مخططات تسمية التجاور ما يلي:

الرسوم البيانية ذات الدرجة المحدودة
إذا كان لكل رأس في الرسم البياني G عدد d من الجيران على الأكثر ، فيمكن ترقيم رؤوس G من 1 إلى n ، ويكون مُعرِّف الرأس هو ( d + 1) - وهو عدد رؤوسه متبوعًا بعدد جيرانه. يكون رأسان متجاورين عندما يظهر العدد الأول في مُعرِّفيهما لاحقًا في مُعرِّف الرأس الآخر. وبشكل أعم، يمكن استخدام نفس المنهج لتقديم تمثيل ضمني للرسوم البيانية ذات التشعب المحدود أو الانحلال المحدود ، بما في ذلك الرسوم البيانية المستوية والرسوم البيانية في أي عائلة رسوم بيانية مغلقة جزئيًا . [ 8 ] [ 9 ]
رسوم بيانية للتقاطع
الرسم البياني الفاصل هو رسم بياني لتقاطع مجموعة من القطع المستقيمة في خط الأعداد الحقيقية . يمكن إعطاؤه نظام ترقيم مجاور، حيث تُرقّم النقاط التي تمثل نهايات القطع المستقيمة من 1 إلى 2^ n ، ويُمثّل كل رأس من رؤوس الرسم البياني برقمي نهايتي الفاصل الزمني المقابل له. باستخدام هذا التمثيل، يمكن التحقق مما إذا كان رأسان متجاورين بمقارنة الأرقام التي تمثلهما والتأكد من أن هذه الأرقام تُحدد فواصل زمنية متداخلة. ينطبق النهج نفسه على رسوم بيانية أخرى للتقاطع الهندسي، بما في ذلك رسوم بيانية ذات حدود مربعة ورسوم بيانية دائرية ، وفروع هذه الفروع مثل الرسوم البيانية الوراثية للمسافة والرسوم البيانية التكميلية . [ 8 ] [ 10 ] مع ذلك، لا يعني تمثيل الرسم البياني للتقاطع الهندسي بالضرورة وجود نظام ترقيم مجاور، لأنه قد يتطلب أكثر من عدد لوغاريتمي من البتات لتحديد كل كائن هندسي. على سبيل المثال، قد يتطلب تمثيل الرسم البياني كرسم بياني لوحدة القرص عددًا هائلاً من البتات لإحداثيات مراكز القرص. [ 11 ]
رسوم بيانية للمقارنة منخفضة الأبعاد
يحتوي مخطط المقارنة لمجموعة مرتبة جزئيًا على رأس لكل عنصر من عناصر المجموعة وحافة بين عنصرين مرتبطين بالترتيب الجزئي. يُعرَّف بُعد الترتيب الجزئي بأنه الحد الأدنى لعدد الترتيبات الخطية التي يتقاطع معها الترتيب الجزئي المُعطى. إذا كان بُعد الترتيب الجزئي محدودًا، فيمكن تعريف مخطط ترقيم التجاور لرؤوس مخطط المقارنة الخاص به عن طريق ترقيم كل رأس بموقعه في كل ترتيب خطي مُحدد، وتحديد أن رأسين متجاوران إذا كان لكل زوج من الأرقام المتناظرة في ترقيمهما نفس علاقة الترتيب. على وجه الخصوص، يسمح هذا بمخطط ترقيم التجاور لمخططات المقارنة الوترية ، والتي تنشأ من ترتيبات جزئية ذات بُعد لا يتجاوز أربعة. [ 12 ] [ 13 ]

التخمين الضمني للرسم البياني

لا تمتلك جميع عائلات الرسوم البيانية بنى محلية. بالنسبة لبعض العائلات، تُثبت حجة عدّ بسيطة عدم وجود مخططات لتسمية التجاور: إذ لا يُمكن استخدام سوى O ( n log n ) بت لتمثيل رسم بياني كامل، وبالتالي لا يُمكن أن يوجد تمثيل من هذا النوع إلا عندما يكون عدد الرسوم البيانية ذات n رأس في العائلة F المُعطاة على الأكثر 2O ( n log n ) . أما عائلات الرسوم البيانية التي تحتوي على أعداد أكبر من الرسوم البيانية، مثل الرسوم البيانية ثنائية الأجزاء أو الرسوم البيانية الخالية من المثلثات ، فلا تمتلك مخططات لتسمية التجاور. [ 8 ] [ 10 ] ومع ذلك، حتى عائلات الرسوم البيانية التي يكون فيها عدد الرسوم البيانية صغيرًا قد لا تمتلك مخططًا لتسمية التجاور. على سبيل المثال، تحتوي عائلة الرسوم البيانية ذات الحواف الأقل من الرؤوس على 2O ( n log n ) رسمًا بيانيًا من n رأسًا، ولكنها تفتقر إلى نظام ترقيم مجاور، إذ يُمكن تحويل أي رسم بياني مُعطى إلى رسم بياني أكبر ضمن هذه العائلة بإضافة رأس معزول جديد لكل حافة، دون تغيير قابلية ترقيمه. [ 7 ] [ 10 ] تساءل كانان وآخرون عما إذا كان وجود خاصية الرسم البياني الفرعي المحظور ، ووجود 2O(n log n) رسمًا بيانيًا من n رأسًا على الأكثر، كافيين معًا لضمان وجود نظام ترقيم مجاور ؛ وهو السؤال الذي أعاد سبينراد صياغته كفرضية. وقد دحضت دراسات حديثة هذه الفرضية من خلال تقديم عائلة من الرسوم البيانية ذات خاصية الرسم البياني الفرعي المحظور ومعدل نمو بطيء بما يكفي، ولكن بدون نظام ترقيم مجاور. [ 14 ] من بين عائلات الرسوم البيانية التي تفي بشروط التخمين والتي لا يوجد لها مخطط تسمية مجاور معروف، عائلة الرسوم البيانية القرصية ورسوم تقاطع القطع المستقيمة.

مخططات التسمية والرسوم البيانية العالمية المستحثة

إذا كانت عائلة الرسوم البيانية F تمتلك نظامًا لترقيم التجاور، فيمكن تمثيل الرسوم البيانية ذات n رأس في F كرسوم بيانية فرعية مستحثة لرسم بياني شامل مستحث مشترك ذي حجم متعدد الحدود، ويتكون هذا الرسم البياني من جميع مُعرّفات الرؤوس الممكنة. وعلى العكس، إذا أمكن إنشاء رسم بياني شامل مستحث من هذا النوع، فيمكن استخدام هويات رؤوسه كعلامات في نظام ترقيم التجاور. [ 8 ] في هذا التطبيق لتمثيلات الرسوم البيانية الضمنية، من المهم أن تستخدم العلامات أقل عدد ممكن من البتات، لأن عدد البتات في العلامات يُترجم مباشرةً إلى عدد الرؤوس في الرسم البياني الشامل المستحث. أظهر ألستروب وراوه أن أي شجرة لها نظام ترقيم مجاور يتكون من log₂n + O ( logₙ ) بت لكل تسمية، ومن ثمّ يترتب على ذلك أن أي رسم بياني ذي عدد شجر k له نظام ترقيم يتكون من k log₂n + O(logₙ) بت لكل تسمية، ورسم بياني شامل يتكون من n k 2 O(logₙ) رأسًا . وبالتحديد ، فإن الرسوم البيانية المستوية لها عدد شجر لا يتجاوز ثلاثة ، لذا فهي تمتلك رسومًا بيانية شاملة ذات عدد رؤوس شبه مكعب. [ 15 ] وقد حسّن جافويل ولابوريل هذا الحدّ، حيث أظهرا أن الرسوم البيانية المستوية وعائلات الرسوم البيانية المغلقة جزئيًا لها نظام ترقيم يتكون من 2 log₂n + O ( log logₙ ) بت لكل تسمية، وأن الرسوم البيانية ذات عرض الشجرة المحدود لها نظام ترقيم يتكون من log₂n + O ( log logₙ ) بت لكل تسمية. [ 16 ] تم تحسين الحد الأقصى للرسوم البيانية المستوية مرة أخرى بواسطة بونامي، وغافويل، وبيليتشوك، الذين أظهروا أن الرسوم البيانية المستوية لها نظام تسمية يتكون من (4/3+o(1))log 2 n بت لكل تسمية. [ 17 ] وأخيرًا، أظهر دوجيموفيتش وآخرون أن الرسوم البيانية المستوية لها نظام تسمية يتكون من (1+o(1))log 2 n بت لكل تسمية، مما ينتج عنه رسم بياني شامل يحتوي على n 1+o(1) رأسًا. [ 18 ]

المراوغة

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

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

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

انظر أيضاً

مراجع

  1. ↑ كورف، ريتشارد إي. (2008)، "بحث ضمني في الرسم البياني قائم على القرص ذو زمن خطي"، مجلة ACM ، 55 (6) 26: 1-40 ، doi : 10.1145/1455248.1455250 ، MR 2477486 ، S2CID 13969607  .
  2. ↑ كورف، ريتشارد إي. (2008)، "تقليل عمليات الإدخال/الإخراج للقرص في البحث بالعرض أولاً ثنائي البت" (PDF) ، وقائع المؤتمر الثالث والعشرين لجمعية الذكاء الاصطناعي الأمريكية ، الصفحات 317-324 ، يحتوي مكعب روبيك القياسي 3×3×3 على 4.3252 × 10 19 حالة، وهو كبير جدًا بحيث لا يمكن البحث فيه بشكل شامل.   
  3. ↑ باباديميتريو، كريستوس (1994)، "حول تعقيد حجة التكافؤ وغيرها من البراهين غير الفعالة للوجود" (ملف PDF) ، مجلة علوم الحاسوب والأنظمة ، 48 (3): 498-532 ، doi : 10.1016/S0022-0000(05)80063-7 ، مؤرشف من الأصل (ملف PDF) بتاريخ 2016-03-04 ، تم استرجاعه بتاريخ 2011-07-12
  4. ↑ إيمرمان، نيل (1999)، "التمرين 3.7 (كل شيء عبارة عن رسم بياني)" ، التعقيد الوصفي ، نصوص الدراسات العليا في علوم الحاسوب، سبرينغر-فيرلاغ، ص 48، ISBN  978-0-387-98600-5.
  5. ↑ ياناكاكيس، ميهاليس (2009)، "التوازنات، والنقاط الثابتة، وفئات التعقيد"، مجلة مراجعة علوم الحاسوب ، 3 (2): 71-85 ، arXiv : 0802.2831 ، doi : 10.1016/j.cosrev.2009.03.004.
  6. ↑ تشايلدز، أندرو م.؛ كليف، ريتشارد؛ ديوتو، إنريكو؛ فرحي، إدوارد؛ غوتمان، سام؛ سبيلمان، دانيال أ. (2003)، "تسريع خوارزمي أُسّي بواسطة مسار كمومي"، وقائع الندوة السنوية الخامسة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة ، نيويورك: جمعية آلات الحوسبة، ص 59-68 ، arXiv : quant-ph/0209131 ، doi : 10.1145/780542.780552 ، ISBN  1-58113-674-9، MR 2121062 ، S2CID 308884  .
  7. 1 2 مولر، جون هارولد (1988)، البنية المحلية في فئات الرسوم البيانية ، أطروحة دكتوراه، معهد جورجيا للتكنولوجيا.
  8. 1 2 3 4 كانان، سامباث؛ ناور، موني ؛ روديتش، ستيفن (1992)، "التمثيل الضمني للرسوم البيانية"، مجلة SIAM للرياضيات المتقطعة ، 5 (4): 596-603 ، doi : 10.1137/0405049 ، MR 1186827 .
  9. ↑ كروباك، ماريك؛ إبشتاين، ديفيد (1991)، "التوجيهات المستوية ذات درجة الخروج المنخفضة وضغط مصفوفات التجاور" (ملف PDF) ، علوم الحاسوب النظرية ، 86 (2): 243-266 ، doi : 10.1016/0304-3975(91)90020-3.
  10. 1 2 3 سبينراد، جيريمي ب. (2003)، "2. تمثيل الرسم البياني الضمني"، تمثيلات الرسم البياني الفعالة ، الجمعية الرياضية الأمريكية، ص 17-30 ، ISBN  0-8218-2815-0.
  11. ↑ كانغ، روس جيه؛ مولر، توبياس (2011)، تمثيلات الكرة والضرب النقطي للرسوم البيانية (ملف PDF) ، مؤرشف من الملف الأصلي (PDF) بتاريخ 16-03-2012 ، تم استرجاعه بتاريخ 12-07-2011.
  12. ↑ ما، تزي هينغ؛ سبينراد، جيريمي ب. (1991)، "الترتيبات الجزئية الخالية من الدورات ومخططات قابلية المقارنة الوترية"، الترتيب ، 8 (1): 49-61 ، doi : 10.1007/BF00385814 ، MR 1129614 ، S2CID 120479154  .
  13. ↑ كورتيس، أندرو ر.؛ إيزوريتا، كليمنتي؛ جويريس، بنسون؛ لوندبيرغ، سكوت؛ ماكونيل، روس م. (2010)، "تمثيل ضمني لرسوم بيانية للمقارنة الوترية في زمن خطي"، الرياضيات التطبيقية المنفصلة ، ​​158 (8): 869-875 ، doi : 10.1016/j.dam.2010.01.005 ، MR 2602811 .
  14. ↑ حاتمي، حامد؛ Hatami, Pooya (2022)، “The implicit graph Conjecture is false”، ندوة IEEE السنوية الثالثة والستون حول أسس علوم الكمبيوتر، FOCS 2022، Denver، CO، الولايات المتحدة الأمريكية، 31 أكتوبر - 3 نوفمبر 2022 ، IEEE، الصفحات من 1134 إلى 1137، أرخايف : 2111.13198 ، doi : 10.1109/FOCS54457.2022.00109 
  15. ↑ ألستروب، ستيفن؛ راوه، ثيس (2002)، "الرسوم البيانية الصغيرة المستحثة الشاملة وتمثيلات الرسوم البيانية الضمنية المضغوطة" (ملف PDF) ، وقائع الندوة السنوية الثالثة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب ، الصفحات 53-62 ، doi : 10.1109/SFCS.2002.1181882 ، ISBN  0-7695-1822-2، S2CID 1820524 ، مؤرشف من النسخة الأصلية (PDF) بتاريخ 27-09-2011 ، تم استرجاعه بتاريخ 13-07-2011 .
  16. ↑ أرنو، لابوريل؛ جافويل، سيريل (2007)، "تمثيل ضمني أقصر للرسوم البيانية المستوية والرسوم البيانية ذات عرض الشجرة المحدود" (ملف PDF) ، وقائع الندوة الأوروبية السنوية الخامسة عشرة حول الخوارزميات ، سلسلة محاضرات في علوم الحاسوب، المجلد 4698، الصفحات 582-593 ، doi : 10.1007/978-3-540-75520-3_52 ، ISBN   978-3-540-75519-7.
  17. ↑ بونامي، مارث؛ جافويل، سيريل؛ بيليبكزوك، ميخال (2020)، "مخططات تسمية أقصر للرسوم البيانية المستوية"، وقائع ندوة ACM-SIAM لعام 2020 حول الخوارزميات المنفصلة ، ​​الصفحات 446-462 ، arXiv : 1908.03341 ، doi : 10.1007/978-3-540-75520-3_52 .
  18. ^ دوجموفيتش، فيدا ؛ إسبيريت، لويس؛ جورت، جوينايل؛ جافويل، سيريل؛ ميسيك، بيوتر؛ مورين، بات (2020)، “وضع العلامات المجاورة للرسوم البيانية المستوية (وما بعدها)”، ندوة IEEE السنوية الحادية والستين حول أسس علوم الكمبيوتر ، الصفحات من 577 إلى 588، أرخايف : 2003.04280 ، دوى : 10.1007/978-3-540-75520-3_52 .
  19. ↑ ريفست، رونالد ل .؛ فيليمين، جان (1975)، "تعميم وبرهان حدسية أنديرا-روزنبرغ"، وقائع الندوة السابعة لجمعية آلات الحوسبة حول نظرية الحوسبة ، ألبوكيرك، نيو مكسيكو، الولايات المتحدة، الصفحات 6-11 ، CiteSeerX 10.1.1.309.7236 ، doi : 10.1145/800116.803747 ، S2CID 16220596   {{citation}}: CS1 maint: موقع الناشر مفقود ( رابط ) .
  20. ↑ كان، جيف؛ ساكس، مايكل ؛ ستورتيفانت، دين (1983)، "مقاربة طوبولوجية للتهرب"، ندوة حول أسس علوم الحاسوب ، لوس ألاميتوس، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية مهندسي الكهرباء والإلكترونيات، ص 31-33 ، doi : 10.1109/SFCS.1983.4 ، ISBN  0-8186-0508-1.
  21. ↑ بيندر، مايكل أ.؛ رون، دانا (2000)، "اختبار عدم وجود دورات في الرسوم البيانية الموجهة في وقت شبه خطي"، الأوتوماتا واللغات والبرمجة (جنيف، 2000) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1853، برلين: سبرينغر، الصفحات 809-820 ، doi : 10.1007/3-540-45022-X_68 ، ISBN   978-3-540-67715-4MR 1795937​ .