0
$\begingroup$

I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer:

Given the graph with the matrix representation \begin{bmatrix}0&0&1&1\\0&0&1&1\\0&1&0&1\\0&0&0&0\\\end{bmatrix} what is its shortest possible unambiguous representation over the boolean alphabet? How about over any alphabet?

Thank you :)

$\endgroup$
1
  • $\begingroup$ What do you mean by "unambiguous representation over the Boolean alphabet"? I have no idea what you mean by that. $\endgroup$ Commented Jun 1, 2020 at 16:54

1 Answer 1

1
$\begingroup$

Using the definitions from: Theoretical Computer Science: Introduction to Automata and Computability by Juraj Hromkovič.

A representation for the graph will be said to be Unambiguous if the graph can be reconstructed from that representation.

Basically, we wish to encode a general graph using boolean alphabet $\Sigma = \{0,1\}$. If we had an additional symbol $|$ in our alphabet, then we can easily encode the graph matrix as $0011|0011|0101|0000$.

But, as we dealing with only boolean symbols, we have to come up with some encoding that doesn't need the separator $|$. An easy way for doing this could be making each 5th bit special. If it is $0$ then it will mark a separator, else the next four bits are also encoding a single row of the matrix, and it won't mark a separator. If the encoding of row doesn't need additional four bits, then make the extra bits $0$. (You need few more such rules to make this encoding "unambiguous").

For example, your matrix can simply be encoded 0011 0 0011 0 0101 0 0000.

Of course, there are much better possible encodings which might utilize the presence of patterns in the matrix (like sparse matrix).

But, your question asks: Given a matrix representation of a graph, what is its shortest possible unambiguous representation over the boolean alphabet? Well, we can easily come up with a trivial encoding: the empty string $\epsilon$ represents the given graph and all other strings represent the graph as per the encoding described above.

So, the smallest unambiguous representation of the given graph matrix would be of length $0$.

This will also hold for any other alphabet.

$\endgroup$

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.