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
Posting Komentar