0
$\begingroup$

I am trying to find a computable, injective and bijective function $f: \mathbb{N} \to A$ where $A$ is the set of all (finite) directed graphs up to isomorphism (also with no edge repetitions). Which means $A$ is containing equivalence classes defined by isomorphism.

i.e, given a graph (class) example $[G] \in A$ where $V_G = \{1,2\}$ and $E_G = \{(1,2)\}$ then if $G'$ is defined by $V_{G'} = \{3,4\}$ and $E_{G'}=\{(3,4)\}$ then $G' \in [G]$ and also if $G''$ is defined by $V_{G''} = \{1,2\}$ and $E_{G''}=\{(2,1)\}$ then $G'' \in [G]$.

In general $G' \in [G]$ if and only if $G'$ is isomorphic to $G$.

I need it to fulfill the restrictions:

  1. If $|V_{[G]}| \leq |V_{[G']}|$ then $f^{-1}([G]) \leq f^{-1}([G'])$

  2. If $|E_{[G]}| \leq |E_{[G']}|$ then $f^{-1}([G]) \leq f^{-1}([G'])$

I think the steps should be to give order to $[G], [G']$ such that $|V_{[G]}| = |V_{[G']}|$ and $|E_{[G]}| = |E_{[G']}|$ in some natural way, find how to calculate the number of $[G'] \in A$ such that $|V_{[G]}| = |V_{[G']}|$ and $|E_{[G]}| = |E_{[G']}|$ as function of $n=|V_{[G]}|, m=|E_{[G]}|$ and then somehow find $f$. Not sure how to go about these steps, or how to find $f$ in some other way?

Thanks for any help!

$\endgroup$
0
1
$\begingroup$

Sure. Such a function exists. You have specified it. Basically, you order the equivalence classes according first to number of vertices, and second by number of edges. There are countably many graphs, so countably many equivalence classes, so they can be enumerated. When you can enumerate them, they can be put into bijective correspondence with $\mathbb{N}$.

This function is computable, by enumerating all graphs with a certain number of vertices and edges. e.g., for each $n:=1,2,3,\dots$, for each $m:=0,1,2,\dots,n^2$, for each graph containing $n$ vertices and $m$ edges, test whether it is isomorphic to any you have computed before, and use that to enumerate the graphs. Of course, this will be a particularly inefficient algorithm.

In principle there is no known polynomial-time algorithm for computing graph isomorphism, so I would not expect a polynomial-time algorithm for $f$ (but this is not a proof; and it's still possible there might exist algorithms that are relatively efficient in practice).

$\endgroup$

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.