Child pages
• Appendix 2 Glossary
Go to start of banner

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

• No labels