st-connectivity

There is a path directed from "s" to "t" in the first graph, but not in the second.

In computer science, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.

Formally, the decision problem is given by

PATH = {⟨D, s, t⟩ | D is a directed graph with a path from vertex s to t}.
This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.