# Graph

### From Glossary

In one context, this is the
functional value and domain: , where
. In another context, this is a (maybe undirected)
network. In the former
context, see also epigraph and hypograph. In the latter
context, the notation is sometimes used to mean a graph with
*vertex* (or *node*) set and *edge* (or
*link*) set . We say an edge is *incident* with the two
nodes that define it, and those two nodes are called the
*endpoints* of the edge. The endpoints are said to be
*adjacent* nodes.

An edge whose endpoints are the same node is called a
*loop*. Two edges with the same endpoints are called
*parallel*. A graph is *simple* if it has no loops or
parallel edges. Otherwise, it is called a *multigraph*. The
*degree* of a node is the number of edges incident to it
(counting a loop twice). If two edges have a common endpoint, they
are said to be *adjacent*. A *path* is a sequence of
edges that are successively adjacent. (If the graph is simple, a
path can also be represented by the associated sequence of
nodes.)

When the edge is *directed* (or *oriented*), it is
called an *arc*. When all edges are directed, the graph is
called a *directed graph*, or *digraph*. With additional
properties (e.g., arc weights), this is a network. A path in a digraph
can traverse its arcs in either the *forward* or
*backward* direction. If all arcs are forward, it is a
*directed path*, or *dipath*.

Here are some special graphs of interest (not exhaustive).

*bipartite*. nodes decompose into 2 sets such that every link has its endpoints in opposite sets. This applies, for example, to the standard transportation problem, where there are sources in one set and destinations in the other.*complete*. There is a link between each pair of nodes. A complete graph on n nodes is usually denoted . In the case of a bipartite graph, the term*bicomplete*is used to mean all possible links are there: between all pairs of nodes in the two sets. A bicomplete graph on sets with and nodes, resp., is usually denoted .*connected*. There is a path between each pair of nodes. If the graph is directed, this divides into:*strongly connected*- arcs must be traversed in forward direction;*weakly connected*- arcs can be traversed in either direction.

*cycle*(denoted for nodes). The links are .*planar*. The graph can be drawn in a plane (2D) such that no two links cross (they meet only at incident nodes). This has special properties in multi-commodity flows and shortest paths.*subgraph*. such that is a subset of and is a subset of .*tree*. Connected and acyclic. One problem is finding a spanning tree that is optimal in some sense.*undirected*. No link is directed.