3 ms·
Graphs are given as abstract sets of vertices and sets of edges (as adjacency lists or matrices). The problem is that corresponding vertices in the two graphs m
by DominikPeters 7y ago
Graphs are given as abstract sets of vertices and sets of edges (as adjacency lists or matrices). The problem is that corresponding vertices in the two graphs may not have the same label, so to solve graph isomorphism naively, one would need to try all n! possible bijections between the vertex sets (where n is the number of vertices).
- sischoel 7y agoWikipedia has a nice picture of two graphs that are isomorph: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism. It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.
- shawnz 7y agoI think pictorial representations are what is confusing the grandparent. The problem isn't about comparing two graphs that look different visually, it's about comparing two graphs which have differently named labels (but might still have the same structure). The graph isomorphism algorithm doesn't know anything about where on the page you drew the nodes, just what is connected to what
- rsp1984 7y agoThanks much for the clarification. I didn't know that one was "allowed" to change labels. It makes sense now.