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

تشاكل مخططين

معطيات : مخططين

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 و "
-OP OP-ملف:Graph isomorphism a.svg	100px-CPCP-	-OP OP-ملف:Graph isomorphism b.svg	210px-CPCP-	$f(a) = 1$ $f-OQ$ CQ- = 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. {{بوابة رياضيات}} [[ca:Isomorfisme de grafs]] [[de:Isomorphie von Graphen]] [[en:Graph isomorphism]] [[es:Isomorfismo de grafos]] [[fr:Isomorphisme de graphes]] [[hu:Gráfizomorfizmus]] [[ja:グラフ同型]] [[pl:Izomorfizm grafów]] [[vi:Phép đẳng cấu đồ thị]]

المراجع

تشاكل المخططات - ويكيبيديا، الموسوعة الحرة - ويكيبيديا - Wikipedia

التصانيف

رياضيات متقطعة نظرية المخططات

مقالات قد تهمك

تصفح الموسوعة

المقالات الأكثر قراءة