Definition from wikipedia: A graph is an ordered pair G=(V,E) comprising a set V

Question

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 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?

Explanation / Answer

A graph G whose nodes are numbered is uniquely described by its adjacency matrix. Concatenating the matrix's rows yields a natural number 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 (G,|V|) and use the result as graph number.

Computing this mapping is easy, but the resulting number can be huge (?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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.