دراسة حول اختبار التماثل لفئة خاصة من البيانات

الملخص

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