6
$\begingroup$

Definition from wikipedia:

A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$.

The set of all finite graphs (modulo isomorphism: we don't want nodes to have identities) is countable and could be enumerated. But what would be an efficient (low-complexity, from a programming point of view) injection from graphs to $\mathbb{N}$?

Edit: Gilles' comment indicates that it is not know whether there is a such function feasible in polynomial time. An example of an exponential-complexity function would be good enough; we can surely do better than a brute enumeration?

$\endgroup$
  • 2
    $\begingroup$ Interesting question, given that no polynomial algorithm is known for deciding graph isomorphism. $\endgroup$ – Gilles Mar 15 '12 at 20:12
  • $\begingroup$ Just a guess: As graphs can be represented by adjacency or incidence matrices it is perhaps easier to look for suitable encoding of the matrix that represents the graph. $\endgroup$ – uli Mar 15 '12 at 20:14
  • $\begingroup$ @uli: Yes but in this case the result must stable by permutation of the indexes that have been assigned to nodes. $\endgroup$ – Stéphane Gimenez Mar 15 '12 at 20:20
3
$\begingroup$

A graph $G$ whose nodes are numbered is uniquely described by its adjacency matrix. Concatenating the matrix's rows yields a natural number $\cal{G}$ in binary representation; in order to deal with leading $0$, prepend a $1$. This mapping is obviously injective. For easier decoding, you might want to use Cantor's pairing function on $(\cal{G}, |V|)$ and use the result as graph number.

Computing this mapping is easy, but the resulting number can be huge ($\approx 2^{|V|^2}$).

In the case nodes cannot be identified, the (conjectured) hardness of Graph Isomorphism (probably) prevents an efficient, real mapping from Graphs to the naturals; for now, we have to be satisfied with a mapping from graph presentations to naturals---or show considerable genius.

$\endgroup$
  • 2
    $\begingroup$ No, you are assuming that nodes have identities. $\endgroup$ – Stéphane Gimenez Mar 15 '12 at 20:23
  • 2
    $\begingroup$ @StéphaneGimenez That's right. Otherwise I would be likely to solve Graph Isomorphism, which is not known to admit a (deterministic) polynomial time solution. See here. $\endgroup$ – Raphael Mar 15 '12 at 20:34

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.