◀ ▲ ▶Branches / Graph-theory / Proposition: Connectivity Is an Equivalence Relation - Components Are a Partition of a Graph
Proposition: Connectivity Is an Equivalence Relation - Components Are a Partition of a Graph
The connectivity of vertices of an directed or undirected graph \(G(V,E)\) is an equivalence relation "\(\leftrightarrow\)" on the set of all vertices \(V\).
In particular, the equivalence classes \(V'\in V/_\leftrightarrow\) build a partition of \(V\), and any vertex \(v\in V\) can be chosen as a representative of exactly one equivalence class \(V'\), such that the induced subgraph (respectively subdigraph) \(G[V']\) contains the vertex \(v\).
\(G[V']\) is called the component of the vertex \(v\).
Table of Contents
Proofs: 4 5 6
Propositions: 7 8
- Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition