Graphs and Graph Variations

•      A graph G = (V, E)

–     V = set of vertices

–     E = set of edges = subset of V * V

–     Thus |E| = O(|V|²)  

Graph Variations

•      Variations:

A connected graph has a path from every vertex to every other

In an undirected graph:

•      Edge (u,v) = edge (v,u)

•      No self-loops

In a directed graph:

•      Edge (u,v) goes from vertex u to vertex v, notated u®v

A weighted graph associates weights with either the edges or the vertices

•      E.g., a road map: edges might be weighted w/ distance 

A multi-graph allows multiple edges between the same vertices

•      E.g., the call graph in a program (a function can get called from multiple points in another function)