SP1799 BOTTOM - The Bottom of a Graph

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], skipTags: ["script","noscript","style","textarea","code"] } }); We will use the following (standard) definitions from graph theory. Let $V$ be a nonempty and finite set, its elements being called vertices (or nodes). Let $E$ be a subset of the Cartesian product $V \\times V$, its elements being called edges. Then $G = (V, E)$ is called a directed graph. Let $n$ be a positive integer, and let $p = (e\_1, \\ldots, e\_n)$ be a sequence of length $n$ of edges $e\_i \\in E$ such that $e\_i = (v\_i, v\_{i+1})$ for a sequence of vertices ($v\_1, \\ldots, v\_{n+1}$). Then $p$ is called a path from vertex $v\_1$ to vertex $v\_{n+1}$ in $G$ and we say that $v\_{n+1}$ is reachable from $v\_1$, writing $(v\_1 \\to v\_{n+1})$. Here are some new definitions. A node $v$ in a graph $G = (V, E)$ is called a sink, if for every node $w$ in $G$ that is reachable from $v$, $v$ is also reachable from $w$. The bottom of a graph is the subset of all nodes that are sinks, i.e., $\\mathrm{bottom}(G) = \\{v \\in V \\mid \\forall w \\in V : (v \\to w) \\Rightarrow (w \\to v) \\}$. You have to calculate the bottom of certain graphs.

N/A

N/A