4 ms·
Wikipedia has a nice picture of two graphs that are isomorph: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism.
by sischoel 7y ago
Wikipedia 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