مشكلة تماثل الرسوم البيانية

مشكلة تماثل الرسوم البيانية هي مشكلة حسابية تتمثل في تحديد ما إذا كان رسمان بيانيان محدودان متماثلين . ^{[ 1 ]}

لا يُعرف ما إذا كانت هذه المسألة قابلة للحل في وقت متعدد الحدود، ولا أنها من فئة NP-كاملة ، وبالتالي قد تندرج ضمن فئة التعقيد الحسابي NP-متوسطة . من المعروف أن مسألة تماثل الرسوم البيانية تقع في التسلسل الهرمي الأدنى لفئة NP ، مما يعني أنها ليست من فئة NP-كاملة إلا إذا انهار التسلسل الهرمي للوقت متعدد الحدود إلى مستواه الثاني. ^{[ 2 ]} في الوقت نفسه، يمكن حل مسألة التماثل للعديد من الفئات الخاصة من الرسوم البيانية في وقت متعدد الحدود، وفي الواقع العملي، غالبًا ما يمكن حل مسألة تماثل الرسوم البيانية بكفاءة. ^{[ 3 ] [ 4 ]}

تُعدّ هذه المسألة حالة خاصة من مسألة تماثل الرسوم البيانية الجزئية ، ^{[ 5 ]} والتي تسأل عما إذا كان الرسم البياني G يحتوي على رسم بياني جزئي متماثل مع رسم بياني آخر H ؛ ومن المعروف أن هذه المسألة من فئة NP-كاملة. كما أنها حالة خاصة من مسألة الزمرة الجزئية المخفية غير التبديلية على الزمرة المتناظرة . ^{[ 6 ]}

في مجال التعرف على الصور، تُعرف هذه المشكلة باسم مشكلة مطابقة الرسم البياني الدقيقة . ^{[ 7 ]}

في نوفمبر 2015، أعلن لازلو باباي عن خوارزمية ذات وقت شبه متعدد الحدود لجميع الرسوم البيانية، أي خوارزمية ذات وقت تشغيل${\displaystyle 2^{O((\log n)^{c})}}$لبعض الثوابت${\displaystyle c>0}$[ ^{8 ] [ 9 ] [ 10 ] [ 11 ]} في 4 يناير 2017، تراجع باباي عن ادعائه بأن زمن التنفيذ شبه متعدد الحدود، واستبدله بحد زمني شبه أسي، ^وذلك بعد أن اكتشف هارالد هيلفجوت خللاً في البرهان. وفي 9 يناير 2017، أعلن باباي عن تصحيح (نُشر كاملاً في 19 يناير) وأعاد تأكيد ادعائه بأن زمن التنفيذ شبه متعدد الحدود، مع تأكيد هيلفجوت لهذا التصحيح. ^{[ 12 ] [ 13 ]} ويدّعي هيلفجوت كذلك أنه يمكن اختيار c = 3 ، وبالتالي يكون زمن التشغيل 2 ^{O((log n ) 3 )} . ^{[ 14 ] [ 15 ]} نشر باباي "تقريرًا أوليًا" عن العمل ذي الصلة في ندوة نظرية الحوسبة لعام 2019 ، واصفًا خوارزمية شبه متعددة الحدود لتقنين الرسوم البيانية ، ^{[ 16 ]} ولكن اعتبارًا من عام 2025النسخة الكاملة من هذه الخوارزميات لا تزال غير منشورة.

قبل ذلك، كانت أفضل خوارزمية نظرية مقبولة تعود إلى باباي ولوكس (1983) ، وقد استندت إلى عمل لوكس السابق (1982) بالإضافة إلى خوارزمية العامل الفرعي لـ ف. ن. زيملياشينكو ( زيملياشينكو، كورنينكو، وتيشكيفيتش 1985 ) . يبلغ زمن تشغيل هذه الخوارزمية 2O ^{( √n log n   )} للرسوم البيانية ذات n رأسًا، وتعتمد على تصنيف المجموعات البسيطة المنتهية . وبدون نظرية التصنيف هذه، تم الحصول على حد أضعف قليلاً، وهو ^{2O (} √n ^{log 2n ) ، أولًا  للرسوم}  البيانية المنتظمة بقوة بواسطة لازلو باباي ( 1980 ) ، ثم تم توسيعه ليشمل الرسوم البيانية العامة بواسطة باباي ولوكس ( 1983) . وقد قام سبيلمان (1996) بتحسين الأس √n للرسوم البيانية المنتظمة بقوة . بالنسبة للرسوم البيانية الفائقة ذات الرتبة المحدودة، تم الحصول على حد أعلى شبه أسي يطابق حالة الرسوم البيانية بواسطة باباي وكودينوتي (2008) . 

توجد عدة خوارزميات عملية متنافسة لإيجاد تماثل الرسوم البيانية، مثل تلك التي وضعها ماكاي (1981) ، وشميدت ودروفيل (1976) ، وأولمان (1976) ، وستويتشيف (2019) . ورغم أنها تبدو فعّالة على الرسوم البيانية العشوائية ، إلا أن عيبها الرئيسي هو بطء تنفيذها بشكل كبير في أسوأ الحالات . ^{[ 17 ]}

تُكافئ مسألة تماثل الرسوم البيانية حسابيًا مسألة حساب زمرة التماثل الذاتي للرسم البياني، ^{[ 18 ] [ 19 ] [ 20 ]} وهي أضعف من مسألة تماثل زمرة التبديلات ومسألة تقاطع زمرة التبديلات. بالنسبة للمسألتين الأخيرتين، حصل باباي، كانتور، ولوكس (1983) على حدود تعقيد مماثلة لتلك الخاصة بتماثل الرسوم البيانية.

يوجد عدد من الحالات الخاصة المهمة لمشكلة تماثل الرسوم البيانية لها حلول فعالة في وقت متعدد الحدود:

• الأشجار ^{[ 21 ] [ 22 ]}
• الرسوم البيانية المستوية ^{[ 23 ]} (في الواقع، تماثل الرسوم البيانية المستوية موجود في فضاء لوغاريتمي ، ^{[ 24 ]} فئة مضمنة في P )
• الرسوم البيانية الفاصلية ^{[ 25 ]}
• الرسوم البيانية للتباديل ^{[ 26 ]}
• الرسوم البيانية الدائرية ^{[ 27 ]}
• الرسوم البيانية ذات المعلمات المحدودة
  • الرسوم البيانية ذات عرض الشجرة المحدود ^{[ 28 ]}
  • الرسوم البيانية ذات الجنس المحدود ^{[ 29 ]} (الرسوم البيانية المستوية هي رسوم بيانية من الجنس 0.)
  • الرسوم البيانية ذات الدرجة المحدودة ^{[ 30 ]}
  • الرسوم البيانية ذات التعددية المحدودة للقيم الذاتية ^{[ 31 ]}
  • الرسوم البيانية القابلة للانكماش من الرتبة k (تعميم للدرجة المحدودة والجنس المحدود) ^{[ 32 ]}
  • إن التماثل الحافظ للألوان للرسوم ^{البيانية} الملونة ذات تعددية الألوان المحدودة (أي أن k رأسًا على الأكثر لها نفس اللون لـ k ثابت ) هو في الفئة NC ، وهي فئة فرعية من P. [ ^{33 ]}

بما أن مسألة تماثل الرسوم البيانية ليست معروفة بأنها مسألة كاملة من فئة NP، ولا بأنها قابلة للحل، فقد سعى الباحثون إلى فهمها بشكل أعمق من خلال تعريف فئة جديدة GI ، وهي مجموعة المسائل التي يمكن اختزالها إلى مسألة تماثل الرسوم البيانية في زمن تورينج متعدد الحدود . ^{[ 34 ]} إذا كانت مسألة تماثل الرسوم البيانية قابلة للحل في زمن متعدد الحدود، فإن GI تساوي P. من ناحية أخرى، إذا كانت المسألة كاملة من فئة NP، فإن GI تساوي NP ، وجميع المسائل في NP قابلة للحل في زمن شبه متعدد الحدود.

كما هو شائع بالنسبة لفئات التعقيد ضمن التسلسل الهرمي للوقت متعدد الحدود ، تُسمى المسألة صعبة الحل في مجموعة GI إذا كان هناك اختزال تورينج متعدد الحدود من أي مسألة في GI إلى تلك المسألة، أي أن حلًا متعدد الحدود لمسألة صعبة الحل في مجموعة GI سيؤدي إلى حل متعدد الحدود لمسألة تماثل الرسم البياني (وبالتالي جميع المسائل في GI ).${\displaystyle X}$تُسمى المسألة كاملة بالنسبة لـ GI ، أو كاملة بالنسبة لـ GI ، إذا كانت صعبة بالنسبة لـ GI وكان حلها في وقت متعدد الحدود سيؤدي إلى حل في وقت متعدد الحدود لمسألة GI${\displaystyle X}$.

تُصنَّف مسألة تماثل الرسوم البيانية ضمن كلٍّ من NP و co- AM . وتُصنَّف مسألة تماثل الرسوم البيانية (GI) ضمن فئة NP ذات التكافؤ P ، كما تُصنَّف ضمن فئة SPP الأصغر حجمًا . ^{[ 35 ]} وكونها تنتمي إلى فئة التكافؤ P يعني أن مسألة تماثل الرسوم البيانية لا تختلف صعوبةً عن تحديد ما إذا كانت آلة تورينغ غير حتمية تعمل في زمن متعدد الحدود تمتلك عددًا زوجيًا أم فرديًا من المسارات المقبولة. كما تُصنَّف مسألة تماثل الرسوم البيانية ضمن فئة ZPP ^NP ذات التكافؤ ZPP . ^{[ 36 ]} وهذا يعني أساسًا أن خوارزمية لاس فيغاس الفعالة، التي تتمتع بإمكانية الوصول إلى وسيط NP، تستطيع حل مسألة تماثل الرسوم البيانية بسهولة بالغة، بحيث لا تكتسب أي قوة إضافية من قدرتها على القيام بذلك في زمن ثابت.

قدّم مانويل بلوم وسامباث كانان ( 1995 ) أداة فحص احتمالية لبرامج التحقق من تماثل الرسوم البيانية. لنفترض أن P إجراء يُزعم أنه يعمل في زمن متعدد الحدود، ويتحقق مما إذا كان رسمان بيانيان متماثلين، ولكنه غير موثوق به. للتحقق مما إذا كان الرسمان البيانيان G و H متماثلين: 

• اسأل P عما إذا كان G و H متماثلين.
  • إذا كانت الإجابة "نعم":
    • حاول إنشاء تماثل باستخدام P كدالة فرعية. حدد رأسًا u في G ورأسًا v في H ، وعدّل الرسمين البيانيين لجعلهما مميزين (مع تغيير محلي بسيط). اسأل P عما إذا كان الرسمان البيانيان المعدلان متماثلين. إذا لم يكن كذلك، فغيّر v إلى رأس مختلف. استمر في البحث.
    • إما أن يتم العثور على التماثل (ويمكن التحقق منه)، أو أن P ستتناقض مع نفسها.
  • إذا كانت الإجابة "لا":
    • نفّذ ما يلي 100 مرة. اختر عشوائيًا الرسم البياني G أو H ، ثم بدّل مواقع رؤوسه عشوائيًا. اسأل P ما إذا كان الرسم البياني متماثلًا مع G و H. (كما هو الحال في بروتوكول AM لعدم تماثل الرسم البياني).
    • إذا فشل أي من الاختبارات، فاعتبر البرنامج P غير صالح. وإلا، فأجب بـ "لا".

هذه العملية تستغرق وقتًا متعدد الحدود، وتعطي الإجابة الصحيحة إذا كان البرنامج P برنامجًا صحيحًا لتماثل الرسوم البيانية. إذا لم يكن البرنامج P صحيحًا، ولكنه أجاب بشكل صحيح على G و H ، فسيعطي المدقق الإجابة الصحيحة، أو سيكتشف سلوكًا غير صحيح للبرنامج P. أما إذا لم يكن البرنامج P صحيحًا، وأجاب بشكل خاطئ على G و H ، فسيكتشف المدقق سلوكًا غير صحيح للبرنامج P باحتمالية عالية، أو سيعطي إجابة خاطئة باحتمالية 2 ⁻¹⁰⁰ .

والجدير بالذكر أن P يستخدم فقط كصندوق أسود.

تُستخدم الرسوم البيانية على نطاق واسع لترميز المعلومات الهيكلية في العديد من المجالات، بما في ذلك رؤية الحاسوب والتعرف على الأنماط ، وتُعد مطابقة الرسوم البيانية ، أي تحديد أوجه التشابه بينها، أداةً مهمةً في هذه المجالات. في هذه المجالات، تُعرف مشكلة تماثل الرسوم البيانية باسم المطابقة الدقيقة للرسوم البيانية. ^{[ 48 ]}

في علم المعلومات الكيميائية والكيمياء الرياضية ، يُستخدم اختبار تماثل الرسوم البيانية لتحديد مركب كيميائي ضمن قاعدة بيانات كيميائية . ^{[ 49 ]} كما يُعد اختبار تماثل الرسوم البيانية مفيدًا في الكيمياء الرياضية العضوية لإنشاء الرسوم البيانية الجزيئية وللتخليق الحاسوبي .

يُعد البحث في قواعد البيانات الكيميائية مثالاً على استخراج البيانات الرسومية ، حيث يُستخدم أسلوب توحيد الرسوم البيانية بشكل متكرر. ^{[ 50 ]} وعلى وجه الخصوص، تستخدم العديد من مُعرّفات المواد الكيميائية ، مثل SMILES و InChI ، المصممة لتوفير طريقة قياسية وسهلة القراءة لترميز المعلومات الجزيئية وتسهيل البحث عنها في قواعد البيانات وعلى الإنترنت، خطوة التوحيد في حساباتها، وهي في جوهرها توحيد الرسم البياني الذي يُمثل الجزيء. ^{[ 51 ]}

في أتمتة تصميم الإلكترونيات، يُعد تماثل الرسم البياني أساس خطوة تصميم الدوائر "التخطيط مقابل المخطط " (LVS)، وهي عملية تحقق من تطابق الدوائر الكهربائية المُمثلة بمخطط الدائرة وتخطيط الدائرة المتكاملة . ^{[ 52 ]}

• مشكلة التماثل الذاتي للرسوم البيانية
• تقنين الرسم البياني