2

I'm working on a problem set. The class is called 'Algorithms for Inference'. In the definition of the problem, it says

$V$ is a set of vertices. An "independent set" can be represented as a binary vector of dimension $n=|V|$ with $I=[I_i]\in \{0,1\}^{|V|}$ representing the subset of vertices $\{i \in V : I_i = 1\}$ .

I don't understand what this at all, and want to kill myself. Could someone explain this to me as he/she would explain it to a 6-year old child? Thanks.

EDIT: Now I get the basic intuition now. The definition 'Independent set' is just a custom definition in my pset, and I didn't post it in the interest of conciseness. Just one more question, what does $I=[I_i]$ mean?

user3884723
  • 85

4 Answers4

1

The definition is a little bit weird and not completely rigorous, especially the $[I_i]$ part, but here is what it means.

You want to represent a subset of the set $V$ of vertices by a binary vector of length $|V|$. For instance if $V=\{v_1,v_2,v_3\}$, you can take the vector $101$ to represent the subset $\{v_1,v_3\}$ of $V$.

The last sentence of your quotation simply says that the subset of vectors you describe correspond to the set of positions labelled $1$ in your vector.

Also don't kill yourself.

Denis
  • 6,945
  • 1
  • 21
  • 22
0

Given a set $V=\{v_1,v_2,\ldots,v_n\}$ therer are many methods to specify a subset of $V$. The obvious one is to list the elements of the subset. Another method is to loop over the vertices (which are conveniently indexed $1$ through $n$ already) and ask "Is this vertex in the subset?" and write $0$ for "no", $1$ for "yes". This gives you an $n$-tuple of binary digits, and obviously you can get the set back from this tuple.

Unfortunately, the quoted statement is really misleading as it in fact identifies the set $V$ with the set $\{1,\ldots,n\}$ whereas it can be an arbitrary set (from the context "vertices" it may be assumed finite, probably).

Hagen von Eitzen
  • 374,180
0

Lets say you have a set $V=\{1,2,\ldots,n\}$. It doesn't actually matter how the elements of $V$ are labelled, but it will be simpler to refer to them like this.

Imagine we have a subset $A\subset V$. Then some elements of $V$ are in the subset $A$, and the others are not. We could imagine associating to each number in $V$ a $1$ or a $0$, depending on whether it lies in $A$ or not.

For example, if $A=\{1,2,4\}$, then we would associate $1,2,4$ with the number $1$, but $3$ and $5,6,\ldots,n$ with the number $0$.

We could imagine arranging all of these ones and zeros into a column vector: for this choice of $A$ we would get:

$$\begin{pmatrix}1\\1\\0\\1\\0\\0\\\vdots\\0\end{pmatrix}$$

So for each subset of $A$, we get a corresponding column vector, whos coordinates are either 0 or 1. Note that $\{0,1\}^{|V|}$ represents the set of all $n$-coordinate column vectors.

You should also be aware that all of the above applies regardless of the type of subset you are looking at -- it doesn't even need to be independent (whatever that means in this context).

Peter Huxford
  • 2,561
0

I don't think it's the definition of indipendent set.

It's just setting a notation: If you have a binary vector with lenght $n=|V|$, you say that every bit corresponds to an element of $V$.

Given the vector, you consider the subset of the elements associated with 1 digits.

For example, 110110001 stands for the subset of $V$ that contains the first, second, fourth, fifth and ninth elements.

If you'd give us more detail on where you found this definition, we could help you more

Exodd
  • 10,844