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

في نظرية المخططات ، يُعرَّف التشاكل بين المخططين G و H بأنه تقابل بين مجموعتي رؤوس G و H

${\displaystyle f\colon V(G)\to V(H)}$

بحيث يكون أي رأسين u و v من G متجاورين في G إذا وفقط إذا${\displaystyle f(u)}$و${\displaystyle f(v)}$تكون متجاورة في H. يوصف هذا النوع من التقابل عادةً بأنه "تقابل يحافظ على الحواف"، وفقًا للمفهوم العام للتماثل الذي يعتبر تقابلًا يحافظ على البنية.

إذا وُجد تماثل بين رسمين بيانيين، فإن الرسمين البيانيين يُطلق عليهما اسم متماثلين ، ويُرمز لهما غالبًا بـ${\displaystyle G\simeq H}$في الحالة التي يكون فيها التشاكل عبارة عن إسقاط للرسم البياني على نفسه، أي عندما يكون G و H رسمًا بيانيًا واحدًا ونفس الرسم البياني، يُطلق على التشاكل اسم التشاكل الذاتي لـ G.

تماثل الرسوم البيانية هو علاقة تكافؤ بين الرسوم البيانية، وبذلك يقسم فئة جميع الرسوم البيانية إلى فئات تكافؤ . تُسمى مجموعة الرسوم البيانية المتماثلة فئة تماثل الرسوم البيانية. يُعدّ سؤال إمكانية تحديد تماثل الرسوم البيانية في وقت متعدد الحدود مشكلة رئيسية لم تُحل بعد في علوم الحاسوب، وتُعرف باسم مشكلة تماثل الرسوم البيانية . ^{[ 1 ] [ 2 ]}

الرسمان البيانيان الموضحان أدناه متماثلان، على الرغم من اختلاف شكل رسوماتهما .

الرسم البياني G	الرسم البياني H	تماثل بين G و H
		f ( a ) = 1 f ( b ) = 6 f ( c ) = 8 f ( d ) = 3 f ( g ) = 5 f ( h ) = 2 f ( i ) = 4 f ( j ) = 7

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

يُجسّد المفهوم الرسمي لـ"التماثل"، مثل "تماثل الرسوم البيانية"، المفهوم غير الرسمي القائل بأن بعض الكائنات لها "نفس البنية" إذا تم تجاهل الفروق الفردية للمكونات "الذرية" للكائنات المعنية. عندما تكون فردية المكونات "الذرية" (الرؤوس والحواف، بالنسبة للرسوم البيانية) مهمة للتمثيل الصحيح لما تُمثله الرسوم البيانية، يتم تحسين النموذج بفرض قيود إضافية على البنية، وتُستخدم كائنات رياضية أخرى: الرسوم البيانية الموجهة ، والرسوم البيانية المُصنفة ، والرسوم البيانية الملونة ، والأشجار الجذرية ، وما إلى ذلك. يمكن أيضًا تعريف علاقة التماثل لجميع هذه التعميمات للرسوم البيانية: يجب أن يحافظ تقابل التماثل على عناصر البنية التي تُحدد نوع الكائن المعني: الأقواس ، والتصنيفات، وألوان الرؤوس/الحواف، وجذر الشجرة الجذرية، وما إلى ذلك.

يُمكّننا مفهوم "تماثل الرسوم البيانية" من التمييز بين خصائص الرسوم البيانية المتأصلة في بنيتها نفسها، والخصائص المرتبطة بتمثيلاتها: رسومات الرسوم البيانية ، وهياكل البيانات الخاصة بها ، وتسمياتها ، وما إلى ذلك. على سبيل المثال، إذا كان للرسم البياني دورة واحدة فقط ، فإن جميع الرسوم البيانية في فئة تماثله تحتوي أيضًا على دورة واحدة فقط. من ناحية أخرى، في الحالة الشائعة عندما تكون رؤوس الرسم البياني ممثلة بالأعداد الصحيحة 1، 2، ...، N ، فإن التعبير

${\displaystyle \sum _{v\in V(G)}v\cdot {\text{deg }}v}$

قد يختلف الأمر بالنسبة لرسمين بيانيين متماثلين.

تنص نظرية ويتني لتماثل الرسوم البيانية ، ^{[ 6 ]} التي وضعها هاسلر ويتني ، على أن رسمين بيانيين متصلين يكونان متماثلين إذا وفقط إذا _كانت رسومهما الخطية متماثلة، باستثناء حالة واحدة: الرسم البياني الكامل ذو الرؤوس الثلاثة K3 ، والرسم البياني _{الثنائي} الكامل _K1,3 ، فهما ليسا متماثلين ولكن كلاهما يشتركان في الرسم الخطي K3 . ويمكن تعميم نظرية ويتني على الرسوم البيانية الفائقة . ^{[ 7 ]}

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

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

تُعدّ مسألة تماثل الرسوم البيانية إحدى المسائل القياسية القليلة في نظرية التعقيد الحسابي التي تنتمي إلى مجموعة NP ، ولكن من غير المعروف انتماؤها إلى أيٍّ من مجموعتيها الفرعيتين المعروفتين (واللتين تكونان منفصلتين إذا كانت P  ≠  NP ): P و NP-complete . وهي واحدة من مسألتين فقط، من أصل 12 مسألة مذكورة في كتاب غاري وجونسون (1979)، لم يُحَلّ تعقيدهما بعد، والمسألة الأخرى هي تحليل الأعداد الصحيحة إلى عواملها الأولية . ومع ذلك، من المعروف أنه إذا كانت المسألة NP-complete، فإن التسلسل الهرمي متعدد الحدود ينهار إلى مستوى محدود. ^{[ 8 ]}

في نوفمبر 2015، ادعى لازلو باباي ، عالم الرياضيات وعلوم الحاسوب بجامعة شيكاغو، أنه أثبت إمكانية حل مسألة تماثل الرسوم البيانية في زمن شبه متعدد الحدود . ^{[ 9 ] [ 10 ]} ونشر نسخًا أولية من هذه النتائج في وقائع ندوة نظرية الحوسبة لعام 2016 ، ^{[ 11 ]} والمؤتمر الدولي للرياضيات لعام 2018. ^{[ 12 ]} في يناير 2017، تراجع باباي لفترة وجيزة عن ادعائه بزمن شبه متعدد الحدود، وذكر بدلًا منه حدًا زمنيًا دون أُسّي . ثم أعاد تأكيد ادعائه الأصلي بعد خمسة أيام. ^{[ 13 ]} اعتبارًا من عام 2024لم يتم نشر النسخة الكاملة من ورقة باباي البحثية في المجلة حتى الآن.

من المعروف أن تعميمها، مشكلة تماثل الرسم البياني الفرعي ، هي مشكلة كاملة من فئة NP.

تتمثل المجالات الرئيسية للبحث في هذه المشكلة في تصميم الخوارزميات السريعة والتحقيقات النظرية لتعقيدها الحسابي ، سواء للمشكلة العامة أو لفئات خاصة من الرسوم البيانية.

يمكن استخدام اختبار تماثل الرسوم البيانية لـ Weisfeiler Leman لاختبار تماثل الرسوم البيانية بطريقة استدلالية. ^{[ 14 ]} إذا فشل الاختبار، فمن المؤكد أن الرسمين البيانيين المدخلين غير متماثلين. أما إذا نجح الاختبار، فقد يكون الرسمان البيانيان متماثلين أو غير متماثلين. توجد تعميمات لخوارزمية الاختبار تضمن اكتشاف التماثلات، إلا أن وقت تشغيلها يتزايد بشكل أُسّي.

من الخوارزميات المعروفة الأخرى لإيجاد تماثل الرسوم البيانية خوارزمية vf2، التي طورها كورديلا وآخرون عام 2001. ^{[ 15 ]} تُعدّ خوارزمية vf2 خوارزمية بحث في العمق أولًا، تسعى إلى بناء تماثل بين رسمين بيانيين تدريجيًا. وتستخدم مجموعة من قواعد الجدوى لتقليص مساحة البحث، مما يسمح لها بالتعامل بكفاءة مع الرسوم البيانية التي تحتوي على آلاف العقد. وقد استُخدمت خوارزمية vf2 على نطاق واسع في تطبيقات متنوعة، مثل التعرف على الأنماط، ورؤية الحاسوب، والمعلوماتية الحيوية. ورغم أن تعقيدها الزمني في أسوأ الحالات يكون أُسّيًا، إلا أنها تُحقق أداءً جيدًا عمليًا مع أنواع عديدة من الرسوم البيانية.

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

• غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية (  الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 0519066 . OCLC 247570676 .​