# 0. Basic Things to Know about Graph as a CSE Undergraduate

• Definitions and representations
• Graph traversal algorithms
  • Depth-first search
  • Breadth-first search
• Connectivity
  • Simple connectivity
  • Strong connectivity
  • Biconnectivity
  • Transitive closure
• Biconnected component algorithms
• Shortest path algorithm
  • All-pairs shortest path algorithm
  • Single-source shortest path algorithm
• Minimum spanning tree algorithm
  • Prim’s minimum spanning tree algorithm
  • Kruskal’s minimum spanning tree algorithm

# 1. Definitions

• An (undirected, simple) graph G is defined to be a pair of (V, E) , where V is a non-empty finite set of elements called vertices, and E is a finite set of unordered pairs of distinct elements of V called edges.
  • G = (V, E) = (V(G), E(G))
  • Graphs that allow loops and multiple edges are often called a general graphs.
• A (simple) digraph D is defined to be a pair (V, A), where V is a non-empty finite set of elements called vertices, and A is a finite set of ordered pairs of distinct elements of V called (directed) edges or (directed) arcs.
• A weighted graph is a graph in which a number, called the weight, is assigned to each edge.

V = \{ 1, 2, 3, 4, 5, 6 \} \\ E = \{ (1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6) \}

From Wikipedia

• A subgraph of a graph G is simply a graph, all of whose vertices belong to V(G) and all of whose edges belong to E(G).

  

# Adjacency and incidence

• Two vertices v and w of a graph G are said to be adjacent if there is an edge joining them.

• Two distinct edges of G are adjacent if they have at least one vertex in common.

• The vertices v and w are then said to be incident to such an edge.

• The degree of a vertex v of G is the number of edges incident to v.

  

# Walk, trail, circuit, path, and cycle

The definitions differ by various textbooks!!!

• A walk (or edge-sequence) is an alternating sequence of vertices and edges, starting and ending at a vertex, in which each edge is adjacent in the sequence to its two endpoints.

• The length of a walk is the number of edges in it.

• A trail is a walk in which all the edges are distinct from one another.

• A walk is closed if it starts and ends at the same vertex.

• A circuit is a trail that is closed.

• A path is a walk in which all the vertices are distinct from one another.

• A cycle is a path containing at least one edge with an exception that the first and last vertices coincide.

• An Eulerian trail is a trail that visits every edge exactly once.

• An Eulerian circuit is an Eulerian trail that starts and ends on the same vertex.

• A Hamiltonian path is a path that visits each vertex exactly once.

• A Hamiltonian cycle is a Hamiltonian path that is a cycle.

  • An Eulerian circuit exists in a connected graph G if the degree of every vertex is even, and can be found in O(|E|) time.
  • Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.