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

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

قطعة من خريطة دقيقة جغرافيا لمترو الأنفاق في لندن (في الأعلى، الصورة من  (Wikimedia commons)   والصورة الأخرى في الأسفل هي قطعة من الشبكة على الخريطة الفعلية

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

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

المصدر

هنا

ترجمة : سميح سعد
تدقيق : علي خالد