Message-ID: <1339803825.24105.1571427750110.JavaMail.confluence@wiki.cns.iu.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_24104_1131567347.1571427750109" ------=_Part_24104_1131567347.1571427750109 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Appendix 2 Glossary

Appendix 2 Glossary

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

unless otherwise noted.

=20
=20
• Weakly Connected=20
=20
• A directed graph is said to be weakly connected if its underlying undirected graph is connected.
• =20
• =20
• Connected=20
=20
• An undirected graph is said to be connected "= if there exists a walk between every pair of its vertices."
• =20
• =20
• Mutually Reachable=20
=20
• "Let u and v be vertices in a digraph G. The= n 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 vert= ex is regarded as reachable from itself (by the trivial walk)."
• =20
• =20
• Strongly Connected=20
=20
• "A digraph is strongly connected if every two= vertices are mutually reachable.
• =20
• =20
• Strong Component=20
=20
• "A strong component of a digraph G i= s a maximal strongly connected subgraph of G. Equivalently, a strong component is a subdigraph induced on a maximal= set of mutually reachable vertices.
• =20
• =20
• Component=20
=20
• "The subgraphs of G which are maximal with respect to the prop= erty of being connected are called the components= of G."
• =20
• =20
• Graph Density=20
• =20

------=_Part_24104_1131567347.1571427750109--