graphs (10.1-10.3)

• vertex set


  {v1, v2, v3, v4}
• graph


  defined as a set of vertices and a set of edges that connect the vertices
• edge set


  {{v2, v3}, {v3, v4}, {v4, v4}, {v1, v4}}
• incident


  when a vertex v is an endpoint of edge e
• adjacent


  whenever there is an edge between two vertices
• simplegraph


  no loops, and no parallel edges
• complete graph


  a simple graph that has exactly one edge connecting each pair of distinct vertices

  
• adjacency matrix


  a representation of a graph
• undirected graph


  the adjacency matrix is symmetric

  
• walk


  a sequence of alternating adjacent vertices and edges of a graph G
• path


  a walk where no vertex is repeated
• circuit


  a walk that begins and ends at the same vertex, may repeat verticies/edges
• cycle


  is a circuit in which no vertex is repeated, except for the first/last vertex, and has at least 3 edges
• degree of a vertex


  the number of edges that are incident on the vertex
• total degree of a graph


  the sum of the degree of all vertices
• in-degree


  $deg^+$$(v)$the number of edges that are incoming to the vertex
• out-degree


  $deg^-(v)$the number of edges that are coming out of the vertex
• Eulerian circuit


  a circuit that contains every vertex and every edge of G
• Hamiltonian Cycle


  a cycle that includes every vertex of G exactly once
• directed acyclic graph (DAG)


  a graph that is directed and has no cycles