Graph Data Structures: Connectedness, Density, and Trees
Classified in Computers
Written on in
English with a size of 41.84 KB
Connected and Disconnected Graphs
A graph is connected if any two vertices of the graph are connected by a path. Conversely, a graph is disconnected if at least two vertices are not connected by a path.
If a graph G is disconnected, then every maximal connected subgraph of G is called a connected component of graph G.
Dense and Sparse Graphs
A dense graph is a graph in which the number of edges is close to the maximal possible number of edges.
A sparse graph is a graph in which the number of edges is close to the minimal possible number of edges. A sparse graph can be a disconnected graph.
Key Characteristics and Comparison
- Informally, a graph with relatively few edges is sparse, and a graph with many edges is dense.
- Sparse graphs are sparsely connected