connected graph
connected graph A graph in which there is a path joining each pair of vertices, the graph being undirected. It is always possible to travel in a connected graph between one vertex and any other; no vertex is isolated. If a graph is not connected it will consist of several components, each of which is connected; such a graph is said to be disconnected.
If a graph G has e edges, v vertices, and p components, the rank of G, written ρ(G), is defined to be v – p
The nullity of G, written μ(G), is e – v + p Thus ρ(G) + μ(G) = e
With reference to a directed graph, a weakly connected graph is one in which the direction of each edge must be removed before the graph can be connected in the manner described above. If however there is a directed path between each pair of vertices u and v and another directed path from v back to u, the directed graph is strongly connected.
More formally, let G be a directed graph with vertices V and edges E. The set V can be partitioned into equivalence classes V1, V2,… under the relation that vertices u and v are equivalent iff there is a path from u to v and another from v to u. Let E1, E2,… be the sets of edges connecting vertices within V1, V2,… Then each of the graphs Gi with vertices Vi and edges Ei is a strongly connected component of G. A strongly connected graph has precisely one strongly connected component.
The process of replacing each of the strongly connected components of a directed graph by a single vertex is known as condensation.
If a graph G has e edges, v vertices, and p components, the rank of G, written ρ(G), is defined to be v – p
The nullity of G, written μ(G), is e – v + p Thus ρ(G) + μ(G) = e
With reference to a directed graph, a weakly connected graph is one in which the direction of each edge must be removed before the graph can be connected in the manner described above. If however there is a directed path between each pair of vertices u and v and another directed path from v back to u, the directed graph is strongly connected.
More formally, let G be a directed graph with vertices V and edges E. The set V can be partitioned into equivalence classes V1, V2,… under the relation that vertices u and v are equivalent iff there is a path from u to v and another from v to u. Let E1, E2,… be the sets of edges connecting vertices within V1, V2,… Then each of the graphs Gi with vertices Vi and edges Ei is a strongly connected component of G. A strongly connected graph has precisely one strongly connected component.
The process of replacing each of the strongly connected components of a directed graph by a single vertex is known as condensation.
More From encyclopedia.com
connect , con·nect / kəˈnekt/ • v. [tr.] (often be connected) bring together or into contact so that a real or notional link is established: the electrodes wer… Connective , connective A logical device used for the construction of more complex statements or expressions from simpler statements or expressions. Examples in e… V , V, v [Called ‘vee’]. The 22nd LETTER of the Roman ALPHABET as used for English. It originated, along with F, U, W, Y, in the Phoenician consonant sym… Chichimec , Chichimec •beck, bedeck, check, cheque, Chiang Kai-shek, crosscheck, Czech, deck, dreck, exec, fleck, heck, hitech, keck, lek, neck, peck, Québec, re… Analog Circuit , V The letter used by the CCITT to categorize standards relating to data communications over telephone (analog) circuits; the number following the let… Mahavira , Mahāvīra
MAHĀVĪRA . Among the numerous philosophers and religious teachers who preached in eastern India during the sixth century bce was the Jina ("…
You Might Also Like
NEARBY TERMS
connected graph