هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها
يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.
يرجى مراجعة هذه المقالة وإزالة وسم المقالات غير المراجعة، ووسمها بوسوم الصيانة المُناسبة.

تشاكل المخططات

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
N write.svg
هذه مقالة جديدة غير مُراجعة. ينبغي أن يُزال هذا القالب بعد أن يُراجعها محررٌ ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المُناسبة. (يونيو 2007)
Arwikify.svg
هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أكتوبر 2015)

تشاكل مخططين[عدل]

معطيات : مخططين G=(S,A) وG'=(S',A') المطلوب : المخططين G وG' هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية f : S \rightarrow S' بحيث \forall (u,v) \in S^2, (u,v) \in A \Leftrightarrow (f(u),f(v)) \in A'

هذا وتعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟.

مثال[عدل]

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

مخطط G مخطط H تشاكل
بين G و H
Graph isomorphism a.svg Graph isomorphism b.svg  f(a) = 1

 f(b) = 6

 f(c) = 8

 f(d) = 3

 f(g) = 5

 f(h) = 2

 f(i) = 4

 f(j) = 7

تمديد المسألة[عدل]

معطيات : مخططين G=(S,A) وG'=(S',A') المطلوب : المخطط G' هل هو ضمن المخطط G ؟ أي بالمعنى الرياضي:

  •  V \subseteq V'
  •  E \subseteq E' \cap (V \times V)

و تعتبر المسألة أصعب بكثير من المسألة الأولى وهي تصنف ضمن NP_complet.