Is there a way to check if two graphs are isomorphic that can

>>8718562
I think this is what you're looking for
https://en.wikipedia.org/wiki/Graph_isomorphism_problem

File: a478e7e9b5e18eef41497b32cc23c44a6281c207_hq.jpg (66KB, 683x1024px) Image search: [Google]

66KB, 683x1024px

>don't really care about time complexity

Let G1 and G2 be graphs with n vertices.

1. Go over all the n! ways to name the vertices in G1 using the vertex names in G2.
2. With each iteration, check if G1 and G2 are identical after the naming.

I believe you can reduce this from O(n!) to O(2^n) if you use dynamic programming.

>>8718688
Would that be easier than generating permutation matrices?

>>8718594
shit.

File: 1461350298786.jpg (62KB, 640x960px) Image search: [Google]

62KB, 640x960px

>>8718808
It's equivalent. We can assume that G1 and G2 have the same vertex labels (v_1, v_2, ..., v_n for example), and then the renaming scheme is merely finding the correct permutation for G1.