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 they are “the same” in terms of the vertices and edges connecting them, they’re just labeled or drawn differently. What you’re giving at the start of your post is just a formalization of that idea.
As an example, let’s imagine two graphs. One has the vertex set {A,B,C} and a single edge between A and B (in other words, the edge set {(A,B)}. The other has the vertex set {X,Y,Z} and a single edge between Y and Z. It should be intuitive enough that these are in some sense “the same graph” (that is, the graph with three vertices and a single edge drawn between one pair among them).
To prove it, we construct a function that maps the vertex set {A,B,C} to the vertex set {X,Y,Z} in a way that preserves edges. Specifically, we take A -> Y, B -> Z, and C -> X. (If the graphs are a directed graphs, this ends up being the only option; if they’re undirected then we could have also done A -> Z and B -> Y instead.). Let’s check to make sure that the condition in your definition is satisfied. There are six possible pairs of vertices: AB, AC, BC, BA, CA, and CB (or if we’re looking only at undirected graphs, just the first three).
So let’s check the edge correspondences:
* AB **is** in the edge set of the first graph, so their images need to be in the edge set of the second. Since A -> Y and B -> Z, we need YZ to be in the edge set of the second graph, and it is.
* AC is **not** in the edge set of the first graph. A -> Y and C -> X, and YX is not in the edge set of the second graph. Good so far.
* BC is not in the edge set of the first graph. B -> Z and C -> X, and ZX is not in the edge set of the second graph. Good.
(and so on for the other three pairs if we’re saying it’s a directed graph). They all match up, so our function is a graph isomorphism.
——
To return to your three methods:
> By labeling vertices and checking neighbors.
One way to check isomorphisms is to look at the neighbors of each vertex “before” and “after” the isomorphism. In the example above, vertex A had a single neighbor B, so the image of A needs to have a single neighbor that is the image of B. And fortunately, Y does indeed have a single neighbor Z.
> By explicitly constructing isomorphism φ.
This is what we did above.
> By using adjacency matrices.
Adjacency matrices are just a way to explicitly list out which pairs of vertices are adjacent to one another. So adjacency matrices are just a mathier way to check neighbors.
Latest Answers