2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't think it's the definition of indipendent set. $\endgroup$ – Exodd Sep 24 '14 at 7:17
  • $\begingroup$ And I don't think this is a vector unless we identify $\{0,1\}$ with $\mathbb F_2$ .... $\endgroup$ – Hagen von Eitzen Sep 24 '14 at 7:19
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ What does the square brackets in my original quotation mean? i.e., the I=[I_i] part $\endgroup$ – user3884723 Sep 24 '14 at 19:40
  • $\begingroup$ I think it means the column vector $$\begin{pmatrix}I_1\\I_2\\\vdots\\I_n\end{pmatrix}$$ $\endgroup$ – Peter Huxford Sep 24 '14 at 20:23
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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

$\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.