0
$\begingroup$

I usually link the verticles by bijection based on verticles' degree, but in cases when there are 2+ verticles with same degrees on both sides, I usually end up with no luck. Is there a better way?

To be more specific, here is my example: image

I did the following links

deg(A)=3 with deg(A')=3
deg(B)=2 with deg(E')=2
deg(C)=4 with deg(D')=4
deg(D)=2 with deg(G')=2
deg(E)=3 with deg(F')=3
deg(G)=3 with deg(B')=3
deg(F)=3 with deg(C')=3

But for e.g {A,B} exists in Graph a) but {A',E'} doesn't in b).

I wasted a lot of time by guessing wrong (these graphs are isomorphic btw, according to my book)

$\endgroup$

1 Answer 1

3
$\begingroup$

I would avoid guessing in cases where it seems like a vertex in one graph might match up with multiple vertices in another graph. Instead, start from places where the bijection is unique, and extend it from there.

In this example, $C$ is the only vertex of graph (a) with degree $4$, and $D$ is the only vertex of graph (c) with degree $4$, so a graph isomorphism $\phi$ from one to the other must have $\phi(C) = D$.

Then we look at $C$'s neighbors in (a) and try to match them up with $D$'s neighbors in (c). There's two neighbors of degree $2$, and two neighbors of degree $3$, so there's four ways to match them up:

  • Either $\phi(B) = E, \phi(D) = G$ or $\phi(B) = G, \phi(D) = E$.
  • Either $\phi(F) = A, \phi(G) = B$ or $\phi(F) = B, \phi(G) = A$.

In this case, it doesn't matter which way we choose: the set of $B$'s neighbors in (a) is the same as the set of $D$'s neighbors in (a), so they're interchangeable, and the same for $F$ and $G$.

Then we look at the remaining vertices. Say we chose $\phi(B) = E$. Then we must have $\phi(A) = F$, because we must choose a neighbor of $E$ in (c). Similarly, we get $\phi(E) = C$, completing the isomorphism.

Now we check that all the edges get mapped to edges, and because we never made guessing steps, either things work out or there is no isomorphism.

I'm not saying you can always avoid guessing, but you can minimize it. If there were no vertices with unique degree, you could look for unique substructures instead: for example, both graphs have only two triangles (triples of vertices all connected to each other), so those have to be matched up.

Sometimes you just get a place where the graphs are highly symmetric, and can't avoid guessing. But that's where actual graph isomorphism algorithms get stuck, too.

$\endgroup$
1
  • $\begingroup$ Thank you for all this! I'll try to keep this in mind next time $\endgroup$
    – bashbin
    Apr 20, 2017 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.