From my lecture notes, “two graphs G and G′ are isomorphic if there is a one-to-one mapping φ: V (G) → V (G′) that preserves
edge relationships i.e. uv ∈ E(G) ↔ φ(u)φ(v) ∈ E(G′)”. What does this mean by when two graphs are isomorphic? Does it mean that two such graphs are the same but the orientation is different?
The lectures notes also state that isomorphic graphs can be shown by the following:
1. By labeling vertices and checking neighbors.
2. By explicitly constructing isomorphism φ.
3. By using adjacency matrices.
I somewhat understand the first method, but I still find it confusing. How can I use these methods to show whether two graphs are isomorphic or not isomorphic?
In: 7
Two graphs are isomorphic if there is a one-to-one correspondence between their vertices such that the edges of one graph are mapped to the edges of the other graph in a way that preserves the relationship between the edges. This means that the two graphs have the same structure, but the vertices may be labeled differently.
To show that two graphs are isomorphic, you can use one of the three methods mentioned in your lecture notes:
By labeling the vertices and checking the neighbors: This means that you would assign labels to the vertices of one of the graphs, and then check if the other graph has the same structure of edges between the vertices with the same labels. If the structures are the same, then the two graphs are isomorphic.
By explicitly constructing an isomorphism: This means that you would find a one-to-one correspondence between the vertices of the two graphs, and then show that the edges of one graph are mapped to the edges of the other graph in a way that preserves the relationship between the edges.
By using adjacency matrices: An adjacency matrix is a matrix that shows which vertices are connected by edges in a graph. If two graphs are isomorphic, their adjacency matrices will be the same, so you can use the adjacency matrices to show that the two graphs are isomorphic.
Latest Answers