تقنين الرسم البياني

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

في نظرية المخططات ، وهي فرع من الرياضيات، تُعرف عملية توحيد المخططات بأنها إيجاد الشكل القانوني للمخطط المعطى G. الشكل القانوني هو مخطط مُصنَّف Canon( G ) متماثل مع G ، بحيث يكون لكل مخطط متماثل مع G نفس الشكل القانوني لـ G. وبالتالي، انطلاقًا من حل مشكلة توحيد المخططات، يمكن أيضًا حل مشكلة تماثل المخططات : لاختبار ما إذا كان مخططان G و H متماثلين، يتم حساب شكليهما القانونيين Canon( G ) وCanon( H )، ثم يتم اختبار ما إذا كان هذان الشكلان القانونيان متطابقين.

الشكل الكنسي للرسم البياني مثال على ثابت الرسم البياني الكامل : لكل رسمين بيانيين متماثلين الشكل الكنسي نفسه، ولكل رسمين بيانيين غير متماثلين شكلان كنسيان مختلفان. [ 1 ] [ 2 ] وبالمقابل، يمكن استخدام أي ثابت كامل للرسوم البيانية لإنشاء شكل كنسي. [ 3 ] يمكن تعريف مجموعة رؤوس الرسم البياني ذي n رأسًا بالأعداد الصحيحة من 1 إلى n ، وباستخدام هذا التعريف، يمكن أيضًا وصف الشكل الكنسي للرسم البياني على أنه تبديل لرؤوسه. تُسمى الأشكال الكنسية للرسم البياني أيضًا بالتسميات الكنسية ، [ 4 ] ويُعرف توحيد الرسم البياني أحيانًا باسم توحيد الرسم البياني .

التعقيد الحسابي

مشكلة لم تُحل في علوم الحاسوب
هل عملية تقنين الرسم البياني مكافئة لمسألة تماثل الرسم البياني في وقت متعدد الحدود؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

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

في عام 2019، أعلن لازلو باباي عن خوارزمية ذات وقت تشغيل شبه متعدد الحدود لتقنين الرسوم البيانية، أي خوارزمية ذات وقت تشغيل2يا((سجل⁡ن)ج){\displaystyle 2^{O((\log n)^{c})}}لبعض الثوابتج>0{\displaystyle c>0}[ 5 ] على الرغم من أن وجود خوارزميات (حتمية) ذات زمن متعدد الحدود لتماثل الرسوم البيانية لا يزال يمثل مشكلة مفتوحة في نظرية التعقيد الحسابي ، فقد أفاد لازلو باباي في عام 1977 أنه باحتمالية لا تقل عن 1 − exp( − O( n ))، تُنتج خوارزمية بسيطة لتصنيف الرؤوس تصنيفًا معياريًا لرسم بياني مُختار عشوائيًا من مجموعة جميع الرسوم البيانية ذات n رأسًا بعد خطوتين فقط من التحسين. وتُنتج تعديلات طفيفة وإضافة خطوة بحث في العمق تصنيفات معيارية لمثل هذه الرسوم البيانية العشوائية المختارة عشوائيًا في زمن خطي متوقع. وتُلقي هذه النتيجة بعض الضوء على سبب الأداء الجيد للعديد من خوارزميات تماثل الرسوم البيانية المُبلغ عنها في التطبيق العملي. [ 6 ] [ 7 ] كان هذا بمثابة اختراق مهم في نظرية التعقيد الاحتمالي ، والتي أصبحت معروفة على نطاق واسع في شكلها المخطوط والتي لا تزال تُذكر على أنها "مخطوطة غير منشورة" لفترة طويلة بعد الإبلاغ عنها في ندوة.  

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

بالنسبة للأشجار، قدم ريد (1972) خوارزمية تبسيط موجزة ذات زمن متعدد الحدود تتطلب مساحة O ( n ) . [ 9 ] ابدأ بتسمية كل رأس بالسلسلة 01. بشكل تكراري، لكل رأس غير طرفي x ، قم بإزالة الصفر البادئ والواحد اللاحق من x.تسمية 's؛ ثم فرز xقم بدمج تسمية x مع تسميات جميع الأوراق المجاورة لها بالترتيب المعجمي. ثم قم بدمج هذه التسميات المرتبة، وأضف صفرًا في البداية وواحدًا في النهاية، واجعل هذا هو التسمية الجديدة لـ x ، ثم احذف الأوراق المجاورة. إذا تبقى رأسان، فقم بدمج تسمياتهما بالترتيب المعجمي.

التطبيقات

يُعدّ توحيد الرسوم البيانية جوهر العديد من خوارزميات تماثل الرسوم البيانية. ومن الأدوات الرائدة في هذا المجال Nauty. [ 10 ]

يُعدّ استخدام تقنية توحيد الرسوم البيانية في استخراج البيانات الرسومية أحد التطبيقات الشائعة ، ولا سيما في تطبيقات قواعد البيانات الكيميائية . [ 11 ]

تستخدم العديد من مُعرّفات المواد الكيميائية ، مثل SMILES و InChI ، خطوات التوحيد القياسي في حساباتها، وهي في جوهرها توحيد قياسي للرسم البياني الذي يُمثل الجزيء. [ 12 ] [ 13 ] [ 14 ] صُممت هذه المُعرّفات لتوفير طريقة قياسية (وأحيانًا سهلة القراءة) لترميز المعلومات الجزيئية، ولتسهيل البحث عن هذه المعلومات في قواعد البيانات وعلى الإنترنت.

انظر أيضاً

مراجع

  1. ↑ أرفيند، فيكرامان؛ داس، بيريسوار؛ كوبلر، يوهانس (2008)، "خوارزمية مساحة لوغاريتمية للتقنين الجزئي لشجرتين"، علوم الحاسوب - النظرية والتطبيقات: الندوة الدولية الثالثة لعلوم الحاسوب في روسيا، CSR 2008، موسكو، روسيا، 7-12 يونيو 2008، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد  5010، سبرينغر، برلين، الصفحات 40-51 ، doi : 10.1007/978-3-540-79709-8_8 ، ISBN  978-3-540-79708-1MR 2475148​ .
  2. 1 2 أرفيند، ف.؛ داس، بيريسوار؛ كوبلر، يوهانس (2007)، "التعقيد المكاني لتماثل الأشجار من الرتبة k "، الخوارزميات والحوسبة: الندوة الدولية الثامنة عشرة، ISAAC 2007، سينداي، اليابان، 17-19 ديسمبر 2007، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 4835، سبرينغر، برلين، الصفحات 822-833 ، doi : 10.1007/978-3-540-77120-3_71 ، ISBN   978-3-540-77118-0MR 2472661​ .
  3. ↑ غوريفيتش، يوري (1997)، "من الثوابت إلى التوحيد" (ملف PDF) ، نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية (63): 115-119 ، MR 1621595 .
  4. ↑ باباي، لازلو ؛ لوكس، يوجين (1983)، "التسمية المعيارية للرسوم البيانية"، وقائع الندوة الخامسة عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 171-183 ، doi : 10.1145/800061.808746 ، ISBN  0-89791-099-0.
  5. ↑ باباي، لازلو (23 يونيو 2019)، الشكل القانوني للرسوم البيانية في وقت شبه متعدد الحدود
  6. ↑ باباي، لازلو (1977)، حول مشكلة التشاكل ، مخطوطة غير منشورة.
  7. ↑ باباي، لازلو ؛ كوتشيرا، ل. (1979)، "التصنيف المتعارف عليه للرسوم البيانية في متوسط ​​زمني خطي"، وقائع الندوة السنوية العشرون لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب ، ص 39-46 ، doi : 10.1109/SFCS.1979.8 ، S2CID 14697933  .
  8. ↑ باباي، لازلو ؛ لوكس، إي. ( 1983)، "التسمية المعيارية للرسوم البيانية"، وقائع الندوة الخامسة عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 171-183 
  9. ↑ ريد، رونالد سي. (1972)، "ترميز أنواع مختلفة من الأشجار غير المصنفة"، نظرية الرسم البياني والحوسبة ، دار النشر الأكاديمية، نيويورك، ص 153-182 ، MR 0344150  .
  10. ↑ ماكاي، بريندان د.؛ بايبرنو، أدولفو (2014)، "مجلة الحوسبة الرمزية"، التماثل العملي للرسوم البيانية، الجزء الثاني ، المجلد 60، الصفحات 94-112 ، arXiv : 1301.1493 ، doi : 10.1016/j.jsc.2013.09.003 ، ISSN 0747-7171 ، S2CID 17930927    .
  11. ↑ كوك، ديان جيه ؛ هولدر، لورانس بي (2007)، "6.2.1. التسمية المتعارف عليها"، استخراج بيانات الرسوم البيانية ، جون وايلي وأولاده، ص 120-122 ، ISBN  978-0-470-07303-2.
  12. ↑ واينينجر، ديفيد؛ واينينجر، آرثر؛ واينينجر، جوزيف ل. (مايو 1989). "SMILES. 2. خوارزمية لتوليد ترميز SMILES فريد". مجلة المعلومات الكيميائية والنمذجة . 29 (2): 97-101 . doi : 10.1021/ci00062a008 . S2CID 6621315 . 
  13. ↑ كيلي، برايان (مايو 2003). "توحيد الرسوم البيانية" . مجلة دكتور دوب .
  14. ↑ شنايدر، نادين؛ سايل، روجر أ.؛ لاندرو، غريغوري أ. (أكتوبر 2015). "رتب ذراتك - تطبيق مفتوح المصدر لخوارزمية جديدة وقوية لتقنين الجزيئات". مجلة المعلومات الكيميائية والنمذجة . 55 (10): 2111-2120 . doi : 10.1021/acs.jcim.5b00543 . PMID 26441310 .