Graphs

A directed graph is a set of nodes (or vertices) and a set of edges (disjoint from the nodes), where each edge has an initial node and a terminal node. 

More formally, a directed graph is a quadruple (V, E, α, β), where

An undirected graph is a set of nodes (or vertices) and a set of edges (disjoint from the nodes), where each edge has two endpoints, not distinguished from each other. 

More formally, an undirected graph is a triple (V, E, δ), where

Two directed graphs (V, E, α, β) and (V', E', α', β') are isomorphic if there are bijections g:V→V' and h:E→E' such that for each eE,

α'(h(e))=g(α(e)) and β'(h(e))=g(β(e))

A loop is an edge both whose endpoints are equal. 

A graph contains multiple edges when two edges share corresponding endpoints.  If a directed graph has no multiple edges, then for it EV×V.

A graph is simple if it contains neither loops nor multiple edges. 

Informally, a partial graph is obtained by deleting some edges, and a subgraph is obtained by deleting some nodes and any edges that are their endpoints.

G'=(V', E', α', β') is a partial graph of G=(V, E, α, β) if

G' is a subgraph of G if

Valid XHTML 1.0 Strict
Valid CSS!
2010Feb24We20:58
Thomas A. Alspaugh