من ويكيبيديا، الموسوعة الحرة
تشاكل مخططين معطيات : مخططين
G
=
(
S
,
A
)
{\displaystyle G=(S,A)}
G
′
=
(
S
′
,
A
′
)
{\displaystyle G'=(S',A')}
G
{\displaystyle G}
G
′
{\displaystyle G'}
f
:
S
→
S
′
{\displaystyle f:S\rightarrow S'}
∀
(
u
,
v
)
∈
S
2
,
(
u
,
v
)
∈
A
⇔
(
f
(
u
)
,
f
(
v
)
)
∈
A
′
{\displaystyle \forall (u,v)\in S^{2},(u,v)\in A\Leftrightarrow (f(u),f(v))\in A'}
هذا وتعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟.
مثال المخططان أدناه متشاكلان، رغم الاختلاف الكبير في طريقة رسمهما، والسبب هو وجود العلاقة الموضحة على الجانب الأيسر.
مخطط G
مخطط H
تشاكل
f
(
a
)
=
1
{\displaystyle f(a)=1}
f
(
b
)
=
6
{\displaystyle f(b)=6}
f
(
c
)
=
8
{\displaystyle f(c)=8}
f
(
d
)
=
3
{\displaystyle f(d)=3}
f
(
g
)
=
5
{\displaystyle f(g)=5}
f
(
h
)
=
2
{\displaystyle f(h)=2}
f
(
i
)
=
4
{\displaystyle f(i)=4}
f
(
j
)
=
7
{\displaystyle f(j)=7}
تمديد المسألة معطيات : مخططين
G
=
(
S
,
A
)
{\displaystyle G=(S,A)}
G
′
=
(
S
′
,
A
′
)
{\displaystyle G'=(S',A')}
G
′
{\displaystyle G'}
المخطط
G
{\displaystyle G}
V
⊆
V
′
{\displaystyle V\subseteq V'}
E
⊆
E
′
∩
(
V
×
V
)
{\displaystyle E\subseteq E'\cap (V\times V)}
و تعتبر المسألة أصعب بكثير من المسألة الأولى وهي تصنف ضمن NP_complet.
