Graphs: Isomorphism
Graphs: Isomorphism
You know that part in the teen romance where the nerdy girl takes off her glasses and has someone do her make-up for the big dance? The part where everyone realizes suddenly that she looks more like a movie star than a nerd. Despite the fact that she was a movie star to begin with, no one seems to notice it in the world of the movie where she values books over lip gloss.
Right.
Isomorphic graphs are just like that overachieving movie star. Sometimes they look beautifully planar, and other times they look like they've just barely survived Hurricane Finals Week. But they're still the same by graph theory standards because each node can be matched between the two different images of the graphs. Check out these isomorphic graphs:
If you can number or letter all of the vertices in one graph and number or letter all the vertices in the other graph in the so that all the edges between nodes stay the same, you've found an isomorphic graph. In the graph above, every node's connected to every other node, but in a graph like this:
there aren't any overlapping nodes, which makes the graph planar. Contrast that with the same, isomorphic graph below.
In both graphs, A is connected to B and E, B is connected to A and D, C is connected to D and E, D is connected to B and C, and E is connected to A and C. Shapewise, though, they look like a pentagon and a star. Put them together and you've got a pentagram.
Wow, that went from zero to witchcraft in 60 seconds. Moving on…
If a graph can be made planar, then its planar and non-planar versions are, by definition, isomorphic graphs, like the planar pentagon and the non-planar star.
Easy, right?
Yeah, not so much. Just like with planarity, there aren't any cheat codes for creating isomorphic graphs or testing to see if two graphs are isomorphic. Even adjacency matrices usually can't make heads or tails of isomorphism. Do you see it?
Left-Hand Graph
| A | B | C | D | E | |
| A | 1 | 1 | |||
| B | 1 | 1 | |||
| C | 1 | 1 | |||
| D | 1 | 1 | |||
| E | 1 | 1 |
Right-Hand Graph
| A | B | C | D | E | |
| A | 1 | 1 | |||
| B | 1 | 1 | |||
| C | 1 | 1 | |||
| D | 1 | 1 | |||
| E | 1 | 1 |
Neither can a computer. Besides
• practice
• trial and error
• a full bag of cosmetics
• a wardrobe of trendy fashion that happens to fit the person you're making over
which is the kind of night computer scientists like to call "using the brute-force method," there really isn't a better way to find these things.
Better start practicing your graph cosmetology skills.