def. Graph. A Graph is defined as:
- Ordered pair where
- is the set of all vertices
Types of Graphs
- Variations on:
- Directed or Undirected
- Connected or Not Connected
- Cyclical or Acyclical
- Common types:
- Tree is a connected undirected acyclical graph
- Forest is a set of trees
- Directed Graph
- Tree is a connected undirected acyclical graph
Properties of Graphs
- Degree of a vertex : number of edges that connect to
- Loop: an edge that connects a vertex to itself
- Cycle: a path that starts and ends with the same vertex
Representation of Graphs in Memory
- Adjacency Matrix
- 2D table of all nodes: Store a 1 if the edge between two nodes exists, 0 otherwise. Example
- Adjacency List
- Array of all vertices, which are also linked list that list all reachable neighbors. Example
- Complexities for the two types of representations:
Paths
- A Simple Path is one that does not repeat verticies
Special Variants
- A Metric weighted graph is where the edge weights satisfy the triangle inequality; i.e. the vertices lie on a surface, and the edges are Euler distances of the verteces