[prev] 21 [next]

Graph Terminology (cont)

Undirected graph
  • edge(u,v) = edge(v,u),   no self-loops   (i.e. no edge(v,v))
Directed graph
  • edge(u,v) ≠ edge(v,u),   can have self-loops   (i.e. edge(v,v))

    Example:

    [Diagram:Pic/ud-graphs.png]

Weighted graph
  • each edge has an associated value (weight)
  • e.g. road map   (weights on edges are distances between cities)
Other types of graphs …

Multi-graph

  • allow multiple edges between two vertices
  • e.g. function call graph   (f() calls g() in several places)