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.
Graph theory
Graph theory is the study of graphs, either for their own sake, or as models of such diverse things as groups (in pure mathematics) or computer networks.
Types of graph
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 Kn, has n(n – 1)/2 edges (i.e., the nth triangular number), (n – 1)! Hamilton circuits, and a chromatic number of n. Every vertex in Kn has degree n – 1; therefore Kn 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.
