Struktur Diskrit : Isomorfisme dalam Graf - Hallo sahabat duniaschools, Pada Artikel yang anda baca kali ini dengan judul Struktur Diskrit : Isomorfisme dalam Graf, kami telah mempersiapkan artikel ini dengan baik untuk anda baca dan ambil informasi didalamnya. mudah-mudahan isi postingan Artikel Struktur Diskrit, yang kami tulis ini dapat anda pahami. baiklah, selamat membaca.

Judul : Struktur Diskrit : Isomorfisme dalam Graf
link : Struktur Diskrit : Isomorfisme dalam Graf

Struktur Diskrit : Isomorfisme dalam Graf

Struktur Diskrit : Isomorfisme dalam Graf

Isomorphism of Graphs

Is it possible to draw two graphs in the same way ?

Do the graphs have the same structure when we ignore the identities of their vertices ?

Different compounds can have the same molecular formula but can differ in structure. Such compounds can be represented by graphs that cannot be drawn in the same way. The graphs representing previously known compounds can be used to determine whether a supposedly new compound has been studied before.

Two simple graphs G1 = ( V1, E1 ) and G2 = ( V2, E2 ) are isomorphic if : 

• There is a one-to-one and onto function (bijection) f from V1 and V2 
• With the property that a and b are adjacent in G1 if and only if f (a) and f (b) are adjacent to G2, for all a and b in V1.

f is called an isomorphism.

When G1 and G2 are isomorphic, there is one-to-one correspondence between vertices of the two graphs that preserves the adjacency relationship. Isomorphism of simple graphs is an equivalence relation. There are n! possible one-to-one correspondence between the vertex sets of two simple graphs with n vertices. 

Example 1

G and H are isomorphic

f (u1) = v1, f (u2) = v4, f (u3) = v3, and f (u4) = v2 is a one to-one correspondence between V and W.

CONDITIONS TIPS

For Two simple graphs G1 = (V1, E1) and G2 = (V2, E2) to be isomorphic 

• |V1| = |V2| 
• |E1| = |E2| 
• The corresponding vertices in G1 and G2, will have the same degree. 
• A bijection f : V1 → V2 should preserve the adjacency relationship: 
• If (a, b) is an edge in E1 then {f (a), f (b)} must be an edge in E2. 
• If (f(a), f(b)) is an edge in E2 then {a, b} must be an edge in E1. 

The three ones were Isomorphism Invariant.

Example 2

The graphs G1 and G2 are isomorphic since : 

• |V1| = |V2|= 4 and |E1| = |E2| = 5 
• Function f with f (a) = u, f (b) = v, f (c) = w, and f (d) = x, is bijection. 
• deg (a) = deg (f (a)) = 2, deg (b) = deg (f (b)) = 3, deg (c) = deg (f (c)) = 3, deg (a) = deg (f (d)) = 2.

Adjacency relationship : 

Example 3

The graphs G1 and G2 are not isomorphic since: 

|V1| = |V2|= 8 and |E1| = |E2| = 10 

BUT 

deg (a) = 2, in G1.

a must correspond to either t, u, x, or y in G2 since deg (t) = deg (u) = deg (x) = deg (y) = 2 . However, each of these four vertices is adjacent to another vertex of degree 2 which is not true for a. (a adjacent with to another vertex of degree 3)

Isomorphism of Graphs by adjacency matrix

For Two simple graphs G1 = (V1, E1) and G2 = (V2, E2) to be isomorphic

the adjacency matrix of G1

is the same as 

the adjacency matrix of G2, with rows and column are labeled by the images of corresponding vertices in G1

Example 4

The graphs G1 and G2 are isomorphic since:

• |V1| = |V2|= 4 and |E1| = |E2| = 5 
• Function f with f (a) = u, f (b) = v, f (c) = w, and f (d) = x, is bijection. 
• The adjacency matrix of G1 and the one of G2 with rows and column are labeled by the images of corresponding vertices in G1 are the same.

Sumber

Slide Strukdis : Isomorphism

http://informatika.unpar.ac.id/

Demikianlah Artikel Struktur Diskrit : Isomorfisme dalam Graf

Sekianlah artikel Struktur Diskrit : Isomorfisme dalam Graf kali ini, mudah-mudahan bisa memberi manfaat untuk anda semua. baiklah, sampai jumpa di postingan artikel lainnya.

Anda sekarang membaca artikel Struktur Diskrit : Isomorfisme dalam Graf dengan alamat link https://duniaschools.blogspot.com/2019/09/struktur-diskrit-isomorfisme-dalam-graf.html