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.
The point of graph theory is that you’re focused on the abstraction underlying the visual representation. All you care about (for this purpose) is the vertices and what they connect to.
You don’t care about the distance between vertices, the angles between edges, etc. Just the vertices and their connections.
So if you have a list of vertices and what they connect to, then any visual representation you construct using only that information is ‘isomorphic’ to any other visual representation you could construct. That’s 1 & 2.
3 is simply another way of writing that list of vertices and what they connect to. Instead of a list of vertices and a list for each vertex, we construct a NxN matrix where each row/column value is ‘1’ if those two vertices connect and ‘0’ if they don’t. While this takes more space than our list method, it still describes what we care about and allows us to use matrix operations to explore the graph.
>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?
It means the graphs have the same structure – not just orientation – you can move the vertices around and have the edges trace different routes to the vertices they join, and the graphs are still isomorphic.
A graph is often thought of as a bunch of edges joining a bunch of vertices, but it’s really just the abstract structure: There’s a bunch of “things”, and they “connect” pairs of other “things”. The first things we call edges, and the other things we call vertices.
If you have two graphs, and you somehow find a way to label them, and then note: “look, in this graph, vertex A is connected to B, C, F and W; and in the other graph, it’s the same! And the two graphs have the same connections, no matter what label we focus on!” then you’ve proved isomorphism. Technically, you’ve explicitly constructed an isomorphism from each to a third graph, whose vertices *are* the labels, and whose edges are pairs of vertices deemed to be “connected”.
You can cut out the middle man, so to speak. Imagine these two graphs:
* “The vertices are {0,1,2,3}, and two vertices are connected only if their sum is odd.”
* “The vertices are the corners of a square ABCD, and the edges are the sides.”
Then you could construct the map φ with φ(1) = A, φ(2)=B, φ(3)=C and φ(4)=D, and then go to the trouble of proving somehow that for any numbers x and y in {0,1,2,3}, x+y is odd if and only if φ(x)φ(y) is an edge of the square.
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