Types of Graphs

Directed vs. Undirected Graphs

Undirected Graph

• An undirected graph is a graph in which edges have no orientation.
• The edge (u, v) is identical to the edge (v, u).
• In the graph above, the nodes could represent cities and an edge could represent a bidirectional raod.

Directed Graph (Digraph)

• A directed graph or digraph is a graph in which edges have orientations.
• For example, the edge (u, v) is the edge from node u to node v.
• In the graph above, the nodes could represent people and an edge (u, v) could represent that person u bought person v a gift.

Weighted/Unweighted Graphs

Weighted Graphs

• Many graphs can have edges that contain a certain weight to represent an arbitrary value such as cost, distance, quantity, etc...
• NOTE: I will usually denote an edge of such a graph as a triplet (u, v, w) and specify whether the graph is directed or undirected.

Special Graphs

Trees

• A tree is an undirected graph with no cycles. Equivalently, it is a connected graph with N nodes and N-1 edges.