subgraph
A graph made from some of another graph's vertices and edges.
In more detail
A spanning tree is a subgraph that keeps every vertex but only enough edges to connect them without cycles. Every tree drawn from a graph's edges is a subgraph of it.
Related terms
- spanning tree — A subset of a connected graph's edges that links all V vertices together with no cycles, using exactly V minus one edges.
- graph — A set of vertices (points) connected by edges (links), used to model networks such as roads, friendships or dependencies.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers