مشكلة المرافق الثلاثة

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

رسم تخطيطي لمسألة المرافق الثلاثة على مستوى ثنائي الأبعاد. جميع الخطوط متصلة، لكن اثنين منها يتقاطعان.
عرضان لمخطط المنفعة، المعروف أيضًا باسم مخطط تومسن أوك3،3{\displaystyle K_{3,3}}

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

يمكن صياغة هذا اللغز كمشكلة في نظرية الرسم البياني الطوبولوجية من خلال التساؤل عما إذا كان الرسم البياني الثنائي الكاملك3،3{\displaystyle K_{3,3}}للرسم البياني، الذي تمثل رؤوسه المنازل والمرافق، وتمثل حوافه روابطها، تمثيل بياني في المستوى. وتتوافق استحالة حل اللغز مع حقيقة أنك3،3{\displaystyle K_{3,3}}ليس رسمًا بيانيًا مستويًا . توجد براهين متعددة على استحالة ذلك، وهي تشكل جزءًا من برهان نظرية كوراتوفسكي التي تميز الرسوم البيانية المستوية برسمين بيانيين فرعيين ممنوعين، أحدهما هوك3،3{\displaystyle K_{3,3}}.

تُعرف المسألة العامة المتمثلة في تقليل عدد التقاطعات في رسومات الرسوم البيانية الثنائية الكاملة باسم مسألة مصنع الطوب لتوران .ك3،3{\displaystyle K_{3,3}}الحد الأدنى لعدد المعابر هو واحد.

ك3،3{\displaystyle K_{3,3}}هو رسم بياني بستة رؤوس وتسعة أضلاع، ويُشار إليه غالبًا باسم رسم بياني للمنفعة في سياق هذه المسألة. [ 1 ] كما يُعرف أيضًا باسم رسم تومسن البياني نسبةً إلى الكيميائي يوليوس تومسن من القرن التاسع عشر . وهو رسم بياني مُغطى جيدًا ، وأصغر رسم بياني مكعب خالٍ من المثلثات ، وأصغر رسم بياني غير مستوٍ ذي صلابة دنيا .

تاريخ

يقدم كولمان (1979) مراجعة لتاريخ مسألة المرافق الثلاثة . ويذكر أن معظم المراجع المنشورة حول هذه المسألة تصفها بأنها "قديمة جدًا". [ 2 ] في أقدم منشور عثر عليه كولمان، أطلق هنري دوديني ( 1917 ) عليها اسم "الماء والغاز والكهرباء". ومع ذلك، يذكر دوديني أن المسألة "قديمة قدم التاريخ... أقدم بكثير من الإضاءة الكهربائية ، أو حتى الغاز ". [ 3 ] وقد نشر دوديني اللغز نفسه سابقًا في مجلة ستراند عام 1913. [ 4 ] ويُنسب ادعاء آخر للأسبقية إلى سام لويد ، الذي اقتبس ابنه في سيرة ذاتية نُشرت بعد وفاته أنه نشر المسألة عام 1900. [ 5 ] 

تتضمن نسخة مبكرة أخرى من المسألة ربط ثلاثة منازل بثلاثة آبار. [ 6 ] وهي تُصاغ بشكل مشابه للغز آخر (وقابل للحل) يتضمن أيضًا ثلاثة منازل وثلاث نوافير، حيث تلامس جميع النوافير الثلاثة ومنزل واحد جدارًا مستطيلًا؛ ويتضمن اللغز مرة أخرى إنشاء وصلات غير متقاطعة، ولكن فقط بين ثلاثة أزواج محددة من المنازل والآبار أو النوافير، كما هو الحال في ألغاز الربط العددي الحديثة . [ 7 ] وبالمثل، يتضمن لغز لويد "الجيران المتخاصمون" ربط ثلاثة منازل بثلاث بوابات عبر ثلاثة مسارات غير متقاطعة (بدلاً من تسعة كما في مسألة المرافق)؛ ويقع منزل واحد والبوابات الثلاث على جدار فناء مستطيل، يحتوي على المنزلين الآخرين بداخله. [ 8 ]

بالإضافة إلى مسألة المرافق الثلاثة، الرسم البيانيك3،3{\displaystyle K_{3,3}}يظهر هذا المفهوم في منشورات أواخر القرن التاسع عشر وأوائل القرن العشرين، سواء في الدراسات المبكرة للصلابة الهيكلية [ 9 ] [ 10 ] أو في نظرية الرسم البياني الكيميائي ، حيث اقترحه يوليوس تومسن عام 1886 لبنية البنزين التي كانت آنذاك غير مؤكدة . [ 11 ] تكريمًا لعمل تومسن،ك3،3{\displaystyle K_{3,3}}يُطلق عليه أحيانًا اسم رسم تومسن البياني. [ 12 ]

إفادة

يمكن صياغة مسألة المرافق الثلاثة على النحو التالي:

لنفترض أن ثلاثة منازل تحتاج إلى توصيل كل منها بشركات المياه والغاز والكهرباء، بخط منفصل من كل منزل إلى كل شركة. هل توجد طريقة لإجراء جميع التوصيلات التسعة دون أن تتقاطع أي من الخطوط؟

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

بعبارات أكثر رسمية في نظرية الرسم البياني ، تسأل المشكلة عما إذا كان الرسم البياني الثنائي الكاملك3،3{\displaystyle K_{3,3}}هو رسم بياني مستوٍ . يحتوي هذا الرسم البياني على ستة رؤوس موزعة على مجموعتين فرعيتين من ثلاثة رؤوس: رأس واحد لكل منزل، ورأس واحد لكل مرفق. وله تسعة أضلاع، ضلع واحد لكل اقتران بين منزل ومرفق، أو بشكل أكثر تجريدًا، ضلع واحد لكل زوج من رأس في مجموعة فرعية ورأس في المجموعة الفرعية الأخرى. الرسوم البيانية المستوية هي الرسوم البيانية التي يمكن رسمها دون تقاطعات في المستوى، وإذا أمكن إيجاد رسم كهذا، فإنه سيحل لغز المرافق الثلاثة. [ 13 ] [ 14 ]

حلول الألغاز

عدم قابلية الحل

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

كما هو معتاد (على مستوى ثنائي الأبعاد مسطح)، فإن حل لغز المنفعة هو "لا": لا توجد طريقة لإنشاء جميع الاتصالات التسعة دون أن تتقاطع أي من الخطوط مع بعضها البعض. بعبارة أخرى، الرسم البيانيك3،3{\displaystyle K_{3,3}}ليس مستوياً. وقد ذكر كازيميرز كوراتوفسكي في عام 1930 أنك3،3{\displaystyle K_{3,3}}غير مستوية، [ 15 ] ومن ثمّ يترتب على ذلك أن المسألة ليس لها حل. ومع ذلك، يذكر كولمان (1979) أنه "من المثير للاهتمام أن كوراتوفسكي لم ينشر برهانًا مفصلاً على أن [ك3،3{\displaystyle K_{3,3}}[ ] غير مستوٍ. [ 2 ]

أحد الأدلة على استحالة إيجاد تضمين مستوٍ لـك3،3{\displaystyle K_{3,3}}يستخدم تحليل حالة يتضمن نظرية منحنى جوردان . [ 16 ] في هذا الحل، يتم فحص الاحتمالات المختلفة لمواقع الرؤوس بالنسبة للدورات الرباعية للرسم البياني، ويُبين أنها جميعًا لا تتوافق مع التضمين المستوي. [ 17 ]

بدلاً من ذلك، من الممكن إثبات أن أي رسم بياني ثنائي الأجزاء مستوٍ بدون جسور معV{\displaystyle V}الرؤوس وهـ{\displaystyle E}الحواف لهاهـ≤2V-4{\displaystyle E\leq 2V-4}من خلال الجمع بين صيغة أويلرV-هـ+F=2{\displaystyle V-E+F=2}(أينF{\displaystyle F}يمثل عدد أوجه التمثيل المستوي، مع ملاحظة أن عدد الأوجه لا يتجاوز نصف عدد الحواف (يجب أن تتناوب الرؤوس المحيطة بكل وجه بين المنازل والمرافق، لذا يحتوي كل وجه على أربعة حواف على الأقل، وتنتمي كل حافة إلى وجهين فقط). في الرسم البياني للمرافق،هـ=9{\displaystyle E=9}و2V-4=8{\displaystyle 2V-4=8}لذا، في الرسم البياني للمنفعة، من غير الصحيح أنهـ≤2V-4{\displaystyle E\leq 2V-4}ولأنها لا تحقق هذه المتباينة، فلا يمكن أن يكون الرسم البياني للمنفعة مستوياً. [ 18 ]

تغيير القواعد

محلول على شريط موبيوس
الحل على سطح حلقي
يسمح تصميم التورس بوجود ما يصل إلى 4 مرافق و 4 منازل

ك3،3{\displaystyle K_{3,3}}هو رسم بياني حلقي ، مما يعني أنه يمكن تضمينه دون تقاطعات على سطح حلقي ، وهو سطح من النوع الأول. [ 19 ] تحل هذه التضمينات نسخًا من اللغز حيث تُرسَم المنازل والشركات على كوب قهوة أو سطح مشابه بدلًا من سطح مستوٍ. [ 20 ] بل إن هناك حرية إضافية كافية على السطح الحلقي لحل نسخة من اللغز بأربعة منازل وأربعة مرافق. [ 21 ] [ 5 ] وبالمثل، إذا عُرض لغز المرافق الثلاثة على ورقة من مادة شفافة، فيمكن حله بعد لف الورقة ولصقها لتشكيل شريط موبيوس . [ 22 ]

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

خصائص الرسم البياني للمنفعة

وبعيدًا عن معضلة المنفعة، فإن الرسم البياني نفسهك3،3{\displaystyle K_{3,3}}يظهر في العديد من السياقات الرياضية الأخرى، بما في ذلك نظرية الصلابة ، وتصنيف الأقفاص والرسوم البيانية المغطاة جيدًا ، ودراسة أعداد تقاطع الرسوم البيانية ، ونظرية قواطع الرسوم البيانية .

صلابة

الرسم البياني للمنفعةك3،3{\displaystyle K_{3,3}}هو رسم بياني لامان ، ما يعني أنه بالنسبة لجميع مواضع رؤوسه تقريبًا في المستوى، لا توجد طريقة لتحريك رؤوسه باستمرار مع الحفاظ على جميع أطوال الحواف، إلا من خلال حركة صلبة للمستوى بأكمله، ولا توجد أي من الرسوم البيانية الفرعية الممتدة له تتمتع بنفس خاصية الصلابة . وهو أصغر مثال على رسم بياني لامان غير مستوٍ. [ 23 ] على الرغم من كونه رسمًا بيانيًا صلبًا بشكل طفيف، إلا أنه يحتوي على تضمينات غير صلبة مع مواضع خاصة لرؤوسه. [ 9 ] [ 24 ] بالنسبة لتضمينات المواضع العامة، فإن معادلة متعددة الحدود التي تصف جميع المواضع الممكنة ذات أطوال الحواف المتساوية لها الدرجة 16، ما يعني أنه بشكل عام يمكن أن يكون هناك 16 موضعًا على الأكثر بنفس الأطوال. من الممكن إيجاد أنظمة لأطوال الحواف حيث يصف ما يصل إلى ثمانية من حلول هذه المعادلة مواضع قابلة للتحقيق. [ 24 ]

خصائص أخرى لنظرية الرسم البياني

ك3،3{\displaystyle K_{3,3}}هو رسم بياني خالٍ من المثلثات ، حيث يمتلك كل رأس فيه ثلاثة جيران بالضبط ( رسم بياني مكعب ). وهو أصغر هذه الرسوم البيانية. لذا، فهو القفص (3،4) ، وهو أصغر رسم بياني له ثلاثة جيران لكل رأس، ويبلغ طول أقصر دورة فيه أربعة. [ 25 ]

كغيرها من الرسوم البيانية الثنائية الكاملة ، تُعتبر هذه الرسمة البيانية مُغطاة جيدًا ، أي أن جميع المجموعات المستقلة القصوى لها نفس الحجم. في هذه الرسمة البيانية، المجموعتان المستقلتان الأقصىتان الوحيدتان هما جانبا التقسيم الثنائي، وهما متساويتان في الحجم.ك3،3{\displaystyle K_{3,3}}[ 26 ] هو واحد من سبعة رسوم بيانية فقط منتظمة من الدرجة 3 ومتصلة من الدرجة 3 ومغطاة جيدًا.

التعميمات

رسم لـك3،3{\displaystyle K_{3,3}}مع معبر واحد

من أهم خصائص الرسوم البيانية المستوية، نظرية كوراتوفسكي التي تنص على أن الرسوم البيانية المستوية هي بالضبط الرسوم البيانية التي لا تحتوي على أي منهماك3،3{\displaystyle K_{3,3}}ولا الرسم البياني الكاملك5{\displaystyle K_{5}}كتقسيم فرعي، ونظرية فاغنر التي تنص على أن الرسوم البيانية المستوية هي بالضبط الرسوم البيانية التي لا تحتوي على أي منهماك3،3{\displaystyle K_{3,3}}ولاك5{\displaystyle K_{5}}كطالب ثانوي ، استخدم وعمّم عدم استواء السطحك3،3{\displaystyle K_{3,3}}[ 27 ]​

تطرح مسألة " مصنع الطوب " التي طرحها بال توران، بشكل أعم، صيغةً لحساب الحد الأدنى لعدد التقاطعات في رسم بياني ثنائي الأجزاء كامل.كأ،ب{\displaystyle K_{a,b}}من حيث عدد الرؤوسأ{\displaystyle a}وب{\displaystyle b}على جانبي التقسيم الثنائي. الرسم البياني للمنفعةك3،3{\displaystyle K_{3,3}}يمكن رسمها بتقاطع واحد فقط، ولكن ليس بدون أي تقاطعات، لذا فإن عدد تقاطعاتها هو واحد. [ 5 ] [ 28 ]

مراجع

  1. ↑ غريس، ديفيد ؛ شنايدر، فريد ب. (1993)، "الفصل 19: نظرية الرسوم البيانية"، مدخل منطقي للرياضيات المتقطعة ، نيويورك: سبرينغر، ص 423-460 ، doi : 10.1007/978-1-4757-3837-7 ، ISBN  978-1-4419-2835-1، S2CID 206657798 انظر الصفحة 437: "ك3،3{\displaystyle K_{3,3}}يُعرف باسم " مخطط المنفعة ".
  2. 1 2 كولمان، ديفيد (1979)، "مشكلة المنافع"، مجلة الرياضيات ، 52 (5): 299-302 ، doi : 10.1080/0025570X.1979.11976807 ، JSTOR 2689782 
  3. 1 2 دوديني، هنري (1917)، "المسألة 251 - الماء والغاز والكهرباء" ، تسليات في الرياضيات ، المجلد 100، توماس نيلسون، ص 73، Bibcode : 1917Natur.100..302 ، doi : 10.1038/100302a0 ، S2CID 10245524   الحل الوارد في الصفحتين 200-201 يتضمن تمرير خط عبر أحد المنازل الأخرى.
  4. ↑ دوديني، هنري (1913)، "ألغاز محيرة، مع بعض الألغاز السهلة للمبتدئين" ، مجلة ستراند ، المجلد 46، ص 110  
  5. 1 2 3 بينيك، لويل ؛ ويلسون، روبن (2010)، "التاريخ المبكر لمسألة مصنع الطوب"، مجلة الرياضيات الذكية ، 32 (2): 41-48 ، doi : 10.1007/s00283-009-9120-4 ، MR 2657999 ، S2CID 122588849  
  6. ↑ "لغز" ، الزراعة الناجحة ، المجلد 13، صفحة 50، 1914  ; "لغز البئر والمنزل" ، مجلة رفيق الشباب ، المجلد 90، العدد 2، صفحة 392، 1916   .
  7. ↑ "32. لغز النافورة" ، كتاب الساحر الخاص، أو فن الشعوذة بأكمله ، نيويورك: ديك وفيتزجيرالد، 1857، ص 276 
  8. ↑ لويد، سام (1959)، "82: الجيران المشاكسون" ، في غاردنر، مارتن (محرر)، الألغاز الرياضية لسام لويد ، دار دوفر للنشر، ص 79، ISBN  9780486204987{{citation}}: CS1 maint: ignored ISBN errors ( link )
  9. 1 2 ديكسون، أ.س. (1899)، "حول بعض الأطر القابلة للتشكيل" ، رسول الرياضيات ، 29 : 1-21 ، JFM 30.0622.02 
  10. ^ Henneberg، L. (1908)، “Die graphische Statik der starren Körper” ، Encyklopädie der Mathematischen Wissenschaften ، المجلد. 4، ص 345 – 434  انظر على وجه الخصوص الصفحة  403 .
  11. ^ تومسن، يوليوس (يوليو ١٨٨٦)، “Die Covenant des Benzols” (PDF) ، Berichte der Deutschen Chemischen Gesellschaft ، 19 (2): 2944–2950 ، دوى : 10.1002/cber.188601902285
  12. ↑ بولوباس، بيلا (1998)، نظرية الرسم البياني الحديثة ، نصوص الدراسات العليا في الرياضيات، المجلد 184، سبرينغر-فيرلاغ، نيويورك، ص 23، doi : 10.1007/978-1-4612-0619-4 ، ISBN   0-387-98488-7MR 1633290​ 
  13. 1 2 هاراري، فرانك (1960)، "بعض الجوانب التاريخية والبديهية لنظرية الرسم البياني"، مجلة SIAM ، 2 (2): 123-131 ، Bibcode : 1960SIAMR...2..123H ، doi : 10.1137/1002023 ، MR 0111698 
  14. 1 2 بونا، ميكلوس (2011)، جولة في علم التوافيق: مقدمة في التعداد ونظرية الرسم البياني ، وورلد ساينتيفيك، ص 275-277 ، ISBN  9789814335232تُقدّم بونا اللغز (على شكل ثلاثة منازل متصلة بثلاثة آبار) في الصفحة  275، وتكتب في الصفحة  277 أنه "يُعادل مشكلة الرسم"ك3،3{\displaystyle K_{3,3}}على سطح مستوٍ بدون تقاطعات".
  15. ^ كوراتوفسكي ، كازيميرز (1930) ، “Sur le problème des courbes gauches en topologie” (PDF) ، Fundamenta Mathematicae (بالفرنسية)، 15 : 271–283 ، دوى : 10.4064 / fm-15-1-271-283
  16. ↑ آيرز، دبليو إل (1938)، "بعض الجوانب الأولية لعلم الطوبولوجيا"، المجلة الرياضية الأمريكية الشهرية ، 45 (2): 88-92 ، doi : 10.1080/00029890.1938.11990773 ، JSTOR 2304276 ، MR 1524194  
  17. ↑ ترودو، ريتشارد ج. (1993)، مقدمة في نظرية الرسم البياني ، كتب دوفر في الرياضيات، نيويورك: منشورات دوفر، الصفحات 68-70 ، ISBN  978-0-486-67870-2
  18. ↑ كابراف، جاي (2001)، الروابط: الجسر الهندسي بين الفن والعلم ، سلسلة كي آند إي حول العقد وكل شيء، المجلد 25، وورلد ساينتيفيك، ص 128، ISBN   9789810245863
  19. ↑ هاراري، ف. (1964)، "نتائج حديثة في نظرية الرسم البياني الطوبولوجية"، مجلة أكتا ماتيماتيكا ، 15 ( 3-4 ): 405-411 ، doi : 10.1007/BF01897149 ، hdl : 2027.42/41775 ، MR 0166775 ، S2CID 123170864  انظر الصفحة 409.
  20. ↑ باركر، مات (2015)، أشياء يمكن صنعها وفعلها في البعد الرابع: رحلة عالم رياضيات عبر الأعداد النرجسية، وخوارزميات المواعدة المثلى، ونوعين على الأقل من اللانهاية، والمزيد ، نيويورك: فارار، ستراوس وجيرو، الصفحات 180-181 ، 191-192 ، ISBN  978-0-374-53563-6MR 3753642​ 
  21. ↑ أوبيرن، تي إتش (21 ديسمبر 1961)، "ألغاز ومفارقات عيد الميلاد، 51: للأولاد والرجال والأبطال" ، مجلة نيو ساينتست ، المجلد 12، العدد 266، الصفحات 751-753   
  22. ↑ لارسن، موغنس إسروم (1994)، "سوء فهم متاهاتي المعقدة قد يجعلني بائسًا"، في غاي، ريتشارد ك .؛ وودرو، روبرت إي. (محرران)، وقائع مؤتمر يوجين سترينز التذكاري حول الرياضيات الترفيهية وتاريخها، الذي عُقد في جامعة كالجاري، كالجاري، ألبرتا، أغسطس 1986 ، MAA Spectrum، واشنطن العاصمة: الجمعية الرياضية الأمريكية، الصفحات 289-293 ، ISBN  0-88385-516-XMR 1303141​ انظر الشكل 7، صفحة 292 .
  23. ↑ سترينو، إيليانا (2005)، "التثليثات الزائفة، والصلابة، وتخطيط الحركة"، الهندسة المنفصلة والحسابية ، 34 (4): 587-635 ، doi : 10.1007/s00454-005-1184-0 ، MR 2173930 ، S2CID 25281202  انظر الصفحة 600: "ليست كل الرسوم البيانية الصلبة الدنيا بشكل عام لها تضمينات على شكل تثليثات زائفة، لأن ليس جميعها رسوم بيانية مستوية. أصغر مثال هوك3،3{\displaystyle K_{3,3}}".
  24. 1 2 والتر، د.؛ هاستي، م. ل. (2007)، "حول وصلة تساعية القضبان، وتكويناتها الممكنة، وشروط الحركة المتناقضة" (ملف PDF) ، في ميرليه، جان بيير؛ داهان، مارك (محرران)، المؤتمر العالمي الثاني عشر لعلم الآليات والآلات (IFToMM 2007) ، الاتحاد الدولي لتعزيز علم الآليات والآلات
  25. ↑ توت، دبليو تي (1947)، "عائلة من الرسوم البيانية المكعبة"، وقائع الجمعية الفلسفية في كامبريدج ، 43 (4): 459-474 ، رمز Bibcode : 1947PCPS...43..459T ، doi : 10.1017/s0305004100023720 ، MR 0021678 ، S2CID 123505185  
  26. ↑ كامبل، إس آر؛ إلينغهام، إم إن ؛ رويل، غوردون إف. (1993)، "توصيف الرسوم البيانية المكعبة المغطاة جيدًا"، مجلة الرياضيات التوافقية والحوسبة التوافقية ، 13 : 193-212 ، MR 1220613 
  27. ↑ ليتل، تشارلز إتش سي (1976)، "نظرية حول الرسوم البيانية المستوية"، في كاس، لويس آر إيه؛ واليس، والتر دي (محرران)، الرياضيات التوافقية 4: وقائع المؤتمر الأسترالي الرابع الذي عُقد في جامعة أديلايد في الفترة من 27 إلى 29 أغسطس 1975 ، سلسلة محاضرات في الرياضيات، المجلد 560، سبرينغر، الصفحات 136-141 ، doi : 10.1007/BFb0097375 ، ISBN   978-3-540-08053-4، MR 0427121 
  28. ↑ باتش، يانوس ؛ شارير، ميشا ( 2009)، "5.1 التقاطعات - مشكلة مصنع الطوب"، الهندسة التوافقية وتطبيقاتها الخوارزمية: محاضرات ألكالا ، الدراسات والبحوث الرياضية، المجلد 152، الجمعية الرياضية الأمريكية ، الصفحات 126-127