Mengapa kita melakukan isomorfisme, automorfisme, dan homomorfisme?

Apa perbedaan utama antara ketiga istilah isomorfisma, automorfisme, dan homomorfisme dalam bahasa awam sederhana dan mengapa kita melakukan isomorfisme, automorfisme, dan homomorfisme?

Isomorfisme memformalkan gagasan grafik yang sama . Misalnya pada gambar ini Anda melihat tiga grafik isomorfik

$G_1$$G_2$$f:V(G_1) \mapsto V(G_2)$

Tidak sulit untuk menemukan penambangan seperti itu untuk setiap pasangan grafik pada gambar.

$G_1 = G_2$

$f$$G$$v$$u$$u$$v$

$G$$u,v \in V(G)$$f:V(G) \mapsto V(G)$$f(u) = v.$

dan seperti yang Anda lihat grafik "terlihat" cukup simetris. Itulah tepatnya karena ia memiliki "banyak" automorfisme dari tipe yang dijelaskan.

Homomorfisme grafik biasanya tidak dipelajari oleh orang awam dan lebih atau kurang dari tujuan teoritis. Misalnya mereka terkait erat dengan gagasan pewarnaan verteks. Lihat juga Hadwiger Dugaan

$h:G\rightarrow G'$$G=(V,E)$$G'=(V',E')$$e=(u,v) \in E$$(h(u),h(v))\in E'$

Sekarang grafik isomorfisma adalah homomorfisme bijective, yang berarti kebalikannya juga homomorfisme. Jika dua grafik isomorfik, maka mereka pada dasarnya adalah grafik yang sama, hanya dengan relabelling dari simpul. Masalah menentukan apakah dua grafik isomorfik satu sama lain adalah masalah penting dalam teori kompleksitas.

Akhirnya automorfisme adalah isomorfisme dari grafik ke dirinya sendiri.