I'm having a hard time understanding the explicit definition and was hoping someone could help me make a connection between the theory of isomorphism and the way it's actually applied (ex. how can we tell if two graphs are isomorphic)?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Two graphs are isomorphic if and only if when someone puts you on one of them and you can walk around however you like, you can't tell which one they put you on.
Another way of expressing the same thing is that two graphs are isomorphic if they're essentially the same and differ at most in the labelling of the vertices.
There is one easy way to do this.
Suppose we were to label the graph by $1,2,\dots,n$.
Now take another graph.
This method checks the structural similarity between graphs using the simplest building blocks, the edges.
This takes $n!/2$ permutations on average and hence is inefficient.