Properties of Graphs
Terminology: |V| and |E| (cardinality) normally written just as V and E.
A graph with V vertices has at most V(V-1)/2 edges.
The ratio E:V can vary considerably.
- if E is closer to V2, the graph is dense
- if E is closer to V, the graph is sparse
- Example: web pages and hyperlinks, intersections and roads on street map
Knowing whether a graph is sparse or dense is important
- may affect choice of data structures to represent graph
- may affect choice of algorithms to process graph
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}