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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Interesting question, given that no polynomial algorithm is known for deciding graph isomorphism. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Mar 15, 2012 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
    Commented Mar 15, 2012 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
    Commented Mar 15, 2012 at 20:20

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ No, you are assuming that nodes have identities. $\endgroup$
    – Stéphane Gimenez
    Commented Mar 15, 2012 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
    Commented Mar 15, 2012 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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