Sci2 Manual : Appendix 2 Glossary

The following definitions are taken from:
Gross, Jonathan L., and Jay Yellen. Handbook of Graph Theory. New York: CRC, 2004

unless otherwise noted.

  • Weakly Connected
    • A directed graph is said to be weakly connected if its underlying undirected graph is connected.
  • Connected
    • An undirected graph is said to be connected "if there exists a walk between every pair of its vertices."
  • Mutually Reachable
    • "Let u and v be vertices in a digraph G. Then u and v are said to be mutually reachable in G if G contains both a directed u - v walk and a directed v - u walk. Every vertex is regarded as reachable from itself (by the trivial walk)."
  • Strongly Connected
    • "A digraph is strongly connected if every two vertices are mutually reachable.
  • Strong Component
    • "A strong component of a digraph G is a maximal strongly connected subgraph of G. Equivalently, a strong component is a subdigraph induced on a maximal set of mutually reachable vertices.
  • Component
    • "The subgraphs of G which are maximal with respect to the property of being connected are called the components of G."
  • Graph Density