recategorized by
433 views
1 votes
1 votes

Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose rows are indexed by the vertices of $G$ and the columns by the edges of $G$. The entry $m_{v, e}$ is defined as follows.

$$ m_{v, e}= \begin{cases}-1 & \text { if } e=(v, w) \text { for some vertex } w, \\ +1 & \text { if } e=(u, v) \text { for some vertex } u, \\ 0 & \text { otherwise. }\end{cases} $$

Suppose every vertex of $G$ is reachable from a special source vertex of $G$. Then, what is the rank of $M?$ 

  1. $m-1$
  2. $m-n+1$
  3. $\lceil m / 2\rceil$
  4. $n-1$
  5. $\lceil n / 2\rceil$
recategorized by

1 Answer

0 votes
0 votes

The rank of the incidence matrix is $(n-1)$, where $n$ is the number of nodes of the graph. So, the answer is option D. $n-1$

Answer:

Related questions

4 votes
4 votes
2 answers
3