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
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.
Latest Answers