How would you verify that two graphs are the same?

Question

Suppose we want to represent molecules in terms of graphs, where each node is an atom, and each edge is a connection between atoms. What would be an algorithm to decide whether two graphs (representing molecules) are equivalent. Since molecules are being represented, each node would need an attribute defining which molecule it is (Carbon, Nitrogen, Oxygen etc).

To make it easier, suppose each graph branches off from the same root atom, Nitrogen, which we can use as the starting node of our algorithm.

eg. N-X, N-Y, N-Z. Where N is the root Nitrogen node and X,Y,Z are the rest of the graph.

Answer 1

That's the Graph Isomorphism Problem;

The graph isomorphism problem is one of few standard problems in computational complexity theory belonging to NP, but not known to belong to either of its well-known (and, if P ≠ NP, disjoint) subsets: P and NP-complete. It is one of only two, out of 12 total, problems listed in Garey & Johnson (1979) whose complexity remains unresolved, the other being integer factorization.

In other words, solving it in the general case is hard.