# graph

"I'll do algebra, I'll do trig, and I'll even do statistics, but graphing is where I draw the line!" – anonymous

In common usage, a graph is a plot of *x* values (the domain) against *y* values (the codomain) for a given function, *y* = *f*(*x*).
Such a graph is also known as a **function graph** or the **graph of a function**.

In graph theory, a graph is any set of dots, known as **nodes** or **vertices**, in which at least some pairs are joined by lines
known as **edges** or **arcs**. What follows
applies only to this second definition.

Often the lines on a graph are used to represent relationships between objects
(represented by dots). Depending on the application, edges may or may not
have a direction, as indicated by an arrow (see directed
graph); edges joining a node to itself may or may not be allowed, and
nodes and/or edges may be assigned weights (see 'weighted
graph' below). A **path** is a series of nodes such that each
node is adjacent to both the preceding and succeeding node. A path is considered **simple** if none of the nodes in the path is repeated. The **length** of a path is the number of edges that the path uses,
counting multiple edges multiple times. If it's possible to establish a
path from any node to any other node of a graph, the graph is said to be
a connected graph. A **circuit** or **cycle** is a path that begins and ends with the same node
and has a length at least two. A **tree** is a connected acyclic
graph, i.e., a graph without any circuits. A complete
graph is one in which every node is adjacent to every other node. An Euler path in a graph is a path that
uses each edge precisely once. If such a path exists, the graph is said
to be **traversable**. An Euler
circuit is a path that traverses each edge precisely once. A Hamilton
path in a graph is a path that visits each node once and only once;
a Hamiltonian circuit is a circuit
that visits each node once and only once. Well known problems whose solution
involves graphs and graph theory include the four-color
problem and the traveling
salesman problem.

### Complete graph

A complete graph is a connected graph in which exactly one
edge connects each pair of vertices.
A complete graph with *n* vertices, denoted *K*_{n},
has *n*(*n* - 1)/2 edges (i.e., the *n*th triangular
number), (*n*-1)! Hamilton
circuits, and a chromatic number of *n*. Every vertex in *K*_{n} has degree *n*-1;
therefore *K*_{n} has an Euler
circuit if and only if *n* is odd. In a **weighted complete
graph**, each edge has a number called a weight attached to it. Each
path then has a total weight, which is the sum of the weights of the edges
in the path.

### Connected graph

A connected graph is a graph in which a path exists between all
pairs of vertices. If the graph is also a directed graph, and there exists
a path from each vertex to every other vertex, then it is a **strongly-connected
graph**. If a connected graph is such that exactly one edge connects
each pair of vertices, then it is said to be a complete
graph.

### Directed graph

A directed graph, also known as a digraph, is a graph in which each edge is replaced by a directed edge, indicated by an arrow. A directed graph having no multiple edges or loops is called a simple directed graph. A complete graph in which each edge is bidirected is called a complete directed graph. A directed graph having no symmetric pair of directed edges (i.e., no bidirected edges) is known as an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of vertices is joined by a single edge having a unique direction) is called a tournament or tour.

### Tangled graph

A tangled graph is in 3-dimensional space, or, equivalently, a graph drawn in the plane so that when edges cross, one edge goes over the other.

### Weighted graph

A weighted graph is a graph having a weight, or number, associated
with each edge. Some algorithms require all weights to be nonnegative, integral, positive, etc. It is also known
as an **edge-weighted graph**.