# vectors in graph theory

I am reading from a book (Combinatorial optimization by Schrijver) and at one point I am not clear as to how his arguments follow. Consider the following:

Let $G(V,E)$ be an undirected graph and let $w:E\rightarrow R_+$. For any subset $F$ of $E$, denote $w(F)=\sum_{e\in F}w(e)$. Denote the incidence vector of $F$ in $\mathbb{R}^E$ by $\chi^F$, i.e. for any edge $e$ in $E$, $\chi^F(e)=1$ if $e\in F$ and $\chi^F(e)=0$ otherwise. Considering $w$ as a vector in in $\mathbb{R}^E$ we have $w(F)=w^T\chi^F$.

My doubts are as follows:

1. Is $E$ a vector space and $w,\chi^F$ linear transformations from $E$ to $\mathbb{R}$? Why are they referred to as vectors? Aren't they functions?
2. What does the term incidence vector mean?
3. How does it mathematically follow that $w(F)=w^T\chi^F$ ?
-

1) Functions over finite sets may be equivalently thought of as vectors in the usual sense. Fix a finite set $E$, ordered arbitrarily as $E = \{ e_1, e_2, \ldots, e_m \}$. Then the set of functions $\mathcal F = \{ f : E \to \mathbb R \}$ is a real vector space of dimension $|E| = m$. In fact, this has the standard basis $\{ \delta_e \colon E \to \mathbb R \}_{e \in E}$ given by $$\delta_e(e') = \begin{cases} 1, &e' = e, \\ 0, &e' \ne e. \end{cases}$$

Based on this idea alone, we are justified in calling a function $f : E \to \mathbb R$ a vector. After all, what are members of a vector space called, if not vectors? However, to cement the idea even more, we go a bit further. Imagine stacking up the values of the function $f$ as a column vector: $$f = \left( \begin{array}{c} f(e_1) \\ f(e_2) \\ f(e_3) \\ \vdots \\ f(e_m) \end{array} \right).$$ Then what we get is a correspondence (an isomorphism, in fact) between the function space $\mathcal F$ and the more familiar space of $m$-dimensional column vectors. This "vector notation" is often preferred over the function representation, since it is more compact. Moreover, this works seamlessly in conjunction with matrices (and matrices are obviously important in linear algebra).

2) An incidence vector $\chi^F$ is essentially the characteristic function of the set $F \subseteq E$ -- seen as a vector. The characteristic function $\chi^F$ is defined as $$\chi^F(e) = \begin{cases} 1, &e \in F, \\ 0, &e \notin F. \end{cases}$$ Correspondingly, we can write $\chi^F$ as the $m$-vector with $1$ in the $i^{th}$ position if $e_i \in F$, and $0$ otherwise.

3) Given two vectors $a$ and $b$, you might have seen the inner product between them, defined as $$a^\mathrm T b = \sum_{i=1}^m a_i b_i.$$ Unfolding this to the function representation, we can define the inner product of two functions $f, g : E \to \mathbb R$ to be $$\langle f, g \rangle = f^\mathrm T g = \sum_{e \in E} f(e) g(e).$$ In the special case when $f = w$ and $g = \chi^F$, we get $$\langle w, \chi^F \rangle = w^\mathrm T \chi^F = \sum_{e \in E} w(e) \chi^F(e) = \sum_{e \in F} w(e),$$ which is $w(F)$ by definition.

-

"Vector" is sometime thought of as a sequence of values with indexed entries. This is one such example - the index set of $\chi^F$ is $E$, the set of edges.

Now here you can think of $\chi$ as an element of $\mathbb{R}^E$ in the sense that $\chi$ is a sequence of $|E|$ real numbers (0 or 1). Actually, in mathematics the symbol $A^B$ usually means "the set of functions from B to A" and $\mathbb{R}^n$ (your basic everyday vector space) can be thought of as a space of functions from $\{1,\dots,n\}$ to $\mathbb{R}$. Such a way of thinking is quite common in mathematics.

The name "incidence vector" means that the vector $\chi^F$ describes the meetings of the edges and the elements of $F$. There is also "incidence matrix" whose rows are vertices and columns edges with 1 for every pair of edge and vertex which meet.

$w(F)=w^T\chi^F$ is easy enough to see from the definitions here: by definition of vector multiplication (the usual scalar product), $w^T\chi^F=\sum_{e\in E}w(e)\chi^F(e)$, and since $\chi^F$ is either 0 or 1, and 1 exactly on $e\in F$, we get $\sum_{e\in E}w(e)\chi^F(e)=\sum_{e\in F}w(e)=w(F)$.

-

Let vi = (#i,yi), • • • ,vn = (xn,yn) be n two-dimensional vectors, where each Xi and each y¿ is an integer whose absolute valué does not exceed 2™/2/(i00v /ñ). Show that there are two disjoint sets I,J C {1,2,..., n} such that ! > = \$ > ; • iei jeJ

-
What you have typed is not rendering properly. – Shahab Nov 19 '12 at 12:26