edited by
263 views
0 votes
0 votes

For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the following conditions:

  • $\left ( i, j \right ) \in R \Rightarrow i < j$;
  • $i <j \Rightarrow \left [ ((i, j) \in R)  \text{ or } (\exists k:(i, k) \in R \wedge (k, j)\in R)\right ]$.

For example, $\left \{ (1, 2),(2, 3) \right \}$ is a $2$- spanner for $\left \{ 1, 2, 3 \right \}$, and

$$\text{R}_{1} = \left \{ (1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5), (4, 6), (4, 7), (5, 6), (6, 7) \right \}$$

is a $2$- spanner for $\text{S} = \left \{ 1, \ldots,7 \right \}$. There are other $2$-spanners for $\text{S}$, of course. $\text{R}_{2} =\left \{ \left ( i, j \right ) \mid i, j\in \left \{ 1,\ldots,7 \right \}, i < j \right \}$ is an example. But $\text{R}_{1}$ is of size $10$, while $\text{R}_{2}$ is of size $21$. We would like to find $2$-spanners that are as small as possible.

  1. Suppose you are given $2$-spanners $\text{R}_{1}$ and $\text{R}_{2}$ for $\left \{ 1,\ldots,7 \right \}$ and $\left \{ 9,\ldots,15 \right \}$ respectively, each of size $10$. Use them to construct a $2$-spanner $\text{R}$ for $\left \{ 1,\ldots,15 \right \}$. Try to get $\text{R}$ of size $34$.
  2. Generalize the above construction to show that any set $\text{S}$ of size $2^{k} – 1$ (for $k > 2)$ has a $2$-spanner of size $(k – 2) 2^{k} + 2$.
edited by

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
1
admin asked Jul 22, 2022
328 views
A Muller automaton is defined as a tuple $\text{M} = (\text{Q}, \text{I}, \Sigma, \rightarrow, \text{T})$ where:$\text{Q}$ is a finite set of states;$\text{I} \subseteq \...