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.
- 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.
- "The subgraphs of G which are maximal with respect to the property of being connected are called the components of G."
- Graph Density
- "The density of a graph is the ratio of the number of edges and the number of possible edges." (from igraph library documentation).