When are the connected components of a directed graph an equivalence class?

69 Views Asked by At

Let $G: I \times I \to \mathbb R_{\geq 0}$ be a weighted, directed graph on a finite set of nodes $I$. Moreover, suppose that each node has an in-degree equal to its out-degree, i.e. $\sum\limits_{j \in I} G(i,j) = \sum\limits_{j \in I} G(j,i)$.

Does this imply that the connected components of $G$ (where we call a node connected to itself even if $G(i,i)=0$) are equivalence classes? I believe the answer is yes, but don't see a proof.

1

There are 1 best solutions below

2
On BEST ANSWER

Let $v$ be a node, and let $S_v$ be the set containing the node $v$ and all nodes that can be reached via any path from $v$. Clearly every out-going edge from any node in $S_v$ must connect to another node in $S_v$ by definition. From the given fact that in-degree=out-degree, those edges account for the total in-degree, and therefore there can be no edges going from any node outside $S_v$ to any node in $S_v$.

To finish off the proof, consider what happens if you have a path from $w$ to $v$. As $S_v$ cannot have any incoming edges from outside, the whole path must also lie in $S_v$, in particular $w\in S_v$. So there is also a path from $v$ to $w$.