# Graph

Jump to: navigation, search

In one context, this is the functional value and domain: $LaTeX: \{(x, z): x \in X, \; z=f(x)\}$, where $LaTeX: f:X \rightarrow R$. In another context, this is a (maybe undirected) network. In the former context, see also epigraph and hypograph. In the latter context, the notation $LaTeX: (V,E)$ is sometimes used to mean a graph with vertex (or node) set $LaTeX: V$ and edge (or link) set $LaTeX: E$. 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 $LaTeX: K_n$. 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 $LaTeX: m$ and $LaTeX: n$ nodes, resp., is usually denoted $LaTeX: K_{mn}$.
• connected. There is a path between each pair of nodes. If the graph is directed, this divides into:
1. strongly connected - arcs must be traversed in forward direction;
2. weakly connected - arcs can be traversed in either direction.
• cycle (denoted $LaTeX: C_n$ for $LaTeX: n$ nodes). The links are $LaTeX: (1,2),(2,3), \ldots, (n-1,n), (n,1)$.
• 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. $LaTeX: (V',E')$ such that $LaTeX: V'$ is a subset of $LaTeX: V$ and $LaTeX: E'$ is a subset of $LaTeX: E$.
• tree. Connected and acyclic. One problem is finding a spanning tree that is optimal in some sense.
• undirected. No link is directed.