A set of sources is an open set in a topology defined by a directed set

41 Views Asked by At

Any directed graph define a topology on its set of vertices $V$. Define $\overline{A}$ as the set of vertices that can be reached from $A\subseteq V$. Prove that a set of sources is an open set in this topology.

A source is a vertex without inflows.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $S\subseteq V$ be the set of sources. We only need to show that $S^c$ is closed, or equivalently, $\overline{S^c}=S^c$.

Let $v\in\overline{S^c}$. Then the vertex $v$ can be reached by an element in $S^c$. Hence $v$ is either in $S^c$, or it has an inflow. In either case we deduce $v\in S^c$. This completes the proof.