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
      • In directed graph, strongly connected means following direction; weakly connected means ignoring direction.
    • Cyclical or Acyclical
  • Common types:

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

  1. Adjacency Matrix
    1. 2D table of all nodes: Store a 1 if the edge between two nodes exists, 0 otherwise. Example
  2. Adjacency List
    1. 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