• Define a Graph:

    • G = (V, E) by defining a pair of sets:
      1. V = a set of vertices
      2. E = a set of edges

  • Edges:

    • Each edge is defined by a pair of vertices
    • An edge connects the vertices that define it
    • In some cases, the vertices can be the same

  • Vertices:

    • Vertices also called nodes
    • Denote vertices with labels

  • Representation:

    • Represent vertices with circles, perhaps containing a label
    • Represent edges with lines between circles

  • Example:

    • V = {A,B,C,D}
    • E = {(A,B),(A,C),(A,D),(B,D),(C,D)}

  • Path:

    • sequence of vertices in which each pair of successive vertices is connected by an edge

  • Cycle:

    • a path that starts and ends on the same vertex

  • Simple path:

    • a path that does not cross itself
      • That is, no vertex is repeated (except first and last)
      • Simple paths cannot contain cycles

  • The length of a path:

    • Number of edges in the path
      • Sometimes the sum of the weights of the edges

  • The degree of a Node:

    • The degree of a node is the number of edges the node is used to define
    • In the example above:
      • Degree 2: B and C
      • Degree 3: A and D
      • A and D have odd degree, and B and C have even degree
    • Can also define in-degree and out-degree
      • In-degree: Number of edges pointing to a node
      • Out-degree: Number of edges pointing from a node