Graph Theory Primer

Basic concepts & examples in an academic style

Graphs and Variants: A graph is a set of nodes. Some pairs of nodes are connected by edges. A graph is directed if its edges are oriented. Directed edges are called arcs. A graph is weighted if its nodes or edges have numeric weights on them. A graph is called a multigraph if a pair of nodes may be connected by multiple edges.

Underlying a directed graph is an undirected graph obtained by stripping away the directions of the arcs and removing any duplicate edges that might result.