رسم بياني لبروير-هايمرز

الموسوعة الحرة

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

بناء

يحتوي مخطط براور-هايمرز على العديد من البنى الجبرية ذات الصلة. إحدى أبسطها هي مخطط بالي المعمم من الدرجة الرابعة : يمكن تعريفه بإنشاء رأس لكل عنصر في الحقل المنتهيجيF(81){\displaystyle GF(81)}وحافة لكل عنصرين يختلفان بمقدار قوة رابعة . [ 1 ] [ 2 ]

ملكيات

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

إلى جانب كونه منتظمًا بقوة، فهو رسم بياني متعدٍ للمسافة . [ 5 ]

تاريخ

على الرغم من أن براور يكتب أن "بناء هذا الرسم البياني هو مجرد خرافة"، ويستشهد كمرجع مبكر بورقة بحثية نُشرت عام 1964 حول المربعات اللاتينية بقلم ديل إم. ميسنر، [ 1 ] إلا أنه سُمي على اسم أندريس براور وويليم إتش. هايمرز، اللذين نشرا في عام 1992 برهانًا على أنه الرسم البياني المنتظم القوي الوحيد الذي له نفس المعاملات. [ 3 ]

يُعدّ مخطط براور-هايمرز أول مخطط في عائلة لانهائية من مخططات رامانوجان، والتي تُعرَّف على أنها مخططات بالي معممة على حقول ذات خاصية ثلاثة. [ 2 ] مع3×3{\displaystyle 3\times 3}يُعدّ رسم روك ورسم الألعاب أحد ثلاثة رسوم بيانية منتظمة قوية فقط، وتكون معاييرها على الشكل التالي:((ن2+3ن-1)2،ن2(ن+3)،1،ن(ن+1)){\displaystyle {\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )}}[ 6 ]​

يجب التمييز بينه وبين مخطط سودوكو ، وهو مخطط مختلف يتكون من 20 مربعًا منتظمًا و81 رأسًا. يُشتق مخطط سودوكو من ألغاز سودوكو عن طريق إنشاء رأس لكل مربع من مربعات اللغز وربط مربعين بحافة عندما ينتميان إلى نفس الصف أو العمود أو3×3{\displaystyle 3\times 3}جزء من اللغز. يحتوي على العديد من الزمر المكونة من 9 رؤوس ويتطلب 9 ألوان في أي تلوين للرسم البياني ؛ يصف تلوين هذا الرسم البياني بـ 9 ألوان لغز سودوكو محلول. [ 7 ] [ 8 ] في المقابل، بالنسبة لرسم براور-هايمرز البياني، فإن أكبر الزمر هي المثلثات وعدد الألوان المطلوبة هو 7. [ 5 ]

مراجع

  1. 1 2 بروير، أندريس ، “الرسم البياني لبروير – هايمرز” ، أوصاف الرسوم البيانية المختلفة ، استرجاعها 2019/02/11
  2. 1 2 بوديستا، ريكاردو أ.؛ فيديلا، دينيس إي. (2018)، أطياف رسوم بالي المعممة وتطبيقاتها ، arXiv : 1812.03332
  3. 1 2 براور، أ . إي .؛ هايمرز، و. هـ. (1992)، "بنية وتفرد الرسم البياني المنتظم بقوة (81،20،1،6)"، مجموعة من المساهمات تكريمًا لجاك فان لينت، الرياضيات المتقطعة ، 106/107: 77-82 ، doi : 10.1016/0012-365X(92)90532-K ، MR 1181899 
  4. ↑ كلارك، إل إتش؛ إنترينجر، آر سي؛ مكانا، جيه إي؛ سيكلي، إل إيه (1991)، "مسائل قصوى للخصائص المحلية للرسوم البيانية" (ملف PDF) ، المجلة الأسترالية الآسيوية للتوافقية ، 4 : 25-31 ، MR 1129266 
  5. 1 2 وايسستين، إريك دبليو. “الرسم البياني لبروير – هايمرز” . عالم الرياضيات .
  6. ^ بوندارينكو، أندريه ف.؛ Radchenko، Danylo V. (2013)، “في عائلة من الرسوم البيانية المنتظمة بقوة معλ=1{\displaystyle \lambda =1}«، مجلة نظرية التوافيق ، السلسلة ب، 103 (4): 521–531 ، arXiv : 1201.0383 ، doi : 10.1016/j.jctb.2013.05.005 ، MR 3071380 ، S2CID 19220680  
  7. ^ جاجو فارغاس، خيسوس؛ هارتيلو هيرموسو، ماريا إيزابيل؛ مارتن موراليس، خورخي؛ Ucha-Enríquez، Jose Maria (2006)، “قواعد Sudokus و Gröbner: ليس فقط تحويلاً “، في Ganzha، Victor G.؛ ماير، إرنست دبليو؛ Vorozhtsov, Evgenii V. (eds.)، جبر الكمبيوتر في الحوسبة العلمية، ورشة العمل الدولية التاسعة، CASC 2006، تشيسيناو، مولدوفا، 11-15 سبتمبر 2006، وقائع ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد. 4194، سبرينغر، الصفحات 155-165 ، doi : 10.1007/11870814_13 ، hdl : 11441/23605  
  8. ↑ هيرزبرغ، أغنيس م .؛ مورتي، م. رام (2007)، "مربعات سودوكو ومتعددات الحدود اللونية" (ملف PDF) ، إشعارات الجمعية الرياضية الأمريكية ، 54 (6): 708-717 ، MR 2327972