تم النشر اليوم 2024/06/16 | تساوي شكل المخططات

تمديد المسألة

معطيات: مخططين G
=
(
S
,
A
)
{displaystyle G=(S,A)} و
G
′ =
( S
′ , A
′ )
{displaystyle G’=(S’,A’)}
المطلوب: المخطط
G
′ {displaystyle G’} هل هو ضمن المخطط G
{displaystyle G} ؟ أي بالمعنى الرياضي: V
⊆ V
′ {displaystyle Vsubseteq V’}
E
⊆ E
′ ∩
(
V
×
V
)
{displaystyle Esubseteq E’cap (Vtimes V)}
و تعتبر المسألة أصعب بكثير من المسألة الأولى وهي تصنف ضمن NP_complet. تساوي شكل المخططات في المشاريع الشقيقة: صور وملفات صوتية من كومنز.
بوابة رياضيات

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.

تشاكل مخططين

معطيات: مخططين 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:Srightarrow S’} بحيث ∀
(
u
,
v
)
∈ S 2
,
(
u
,
v
)
∈
A
⇔
(
f
(
u
)
,
f
(
v
)
)
∈ A
′ {displaystyle forall (u,v)in S^{2},(u,v)in ALeftrightarrow (f(u),f(v))in A’} هذا وتعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟. مثال
المخططان أدناه متشاكلان، رغم الاختلاف الكبير في طريقة رسمهما، والسبب هو وجود العلاقة الموضحة على الجانب الأيسر. مخطط G مخطط H تشاكلبين 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’}

هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية

f
:
S
→

S
′

{displaystyle f:Srightarrow S’}

بحيث

∀
(
u
,
v
)
∈

S

2

,
(
u
,
v
)
∈
A
⇔
(
f
(
u
)
,
f
(
v
)
)
∈

A
′

{displaystyle forall (u,v)in S^{2},(u,v)in ALeftrightarrow (f(u),f(v))in A’}