Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

A graph is defined as it always is. A set of edges that connect nodes by their IDs. We can use this arrow notation for convenience. Imagine you have a graph: a->b b->c c->d d->b

Is that the same as this graph? a'->b' b'->c' c'->a' d'->a'

You can sort the edges alphabetically in the first graph. Then you could take the second graphs labels, and figure out if there is a way to "relabel" it, so when you sort those edges alphabetically, you can the same result.

There are |V|! possible ways to relabel |V| vertices. Other algorithms are better than "try everything", but this shows why it's not trivial. Like a puzzle, you can put the pieces into place, and everything looks right, but then when you get to the end you realize one piece doesn't fit. Does that mean it's not-isomorphic? or maybe you just need to re-arrange the pieces differently? That's why the complexity is so high.



Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: