Graph (discrete mathematics)
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related".
[1] Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.
In contrast, if an edge from a person A to a person B means that A owes money to B, then this graph is directed, because owing money is not necessarily reciprocated.
The word "graph" was first used in this sense by J. J. Sylvester in 1878 due to a direct relation between mathematics and chemical structure (what he called a chemico-graphical image).
The following are some of the more basic ways of defining graphs and related mathematical structures.
of vertices, whose elements are called edges (sometimes links or lines).
A multigraph is a generalization that allows multiple edges to have the same pair of endpoints.
[6][7] Sometimes, graphs are allowed to contain loops, which are edges that join a vertex to itself.
Sometimes infinite graphs are considered, but they are usually viewed as a special kind of binary relation, because most results on finite graphs either do not extend to the infinite case or need a rather different proof.
The order of a graph is its number |V| of vertices, usually denoted by n. The size of a graph is its number |E| of edges, typically denoted by m. However, in some contexts, such as for expressing the computational complexity of algorithms, the term size is used for the quantity |V| + |E| (otherwise, a non-empty graph could have size 0).
A graph is fully determined by its adjacency matrix A, which is an n × n square matrix, with Aij specifying the number of connections from vertex i to vertex j.
For a simple graph, Aij is either 0, indicating disconnection, or 1, indicating connection; moreover Aii = 0 because an edge in a simple graph cannot start and end at the same vertex.
Graphs with self-loops will be characterized by some or all Aii being equal to a positive integer, and multigraphs (with multiple edges between vertices) will be characterized by some or all Aij being equal to a positive integer.
Undirected graphs will have a symmetric adjacency matrix (meaning Aij = Aji).
In one restricted but very common sense of the term,[8] a directed graph is a pair G = (V, E) comprising: To avoid ambiguity, this type of object may be called precisely a directed simple graph.
In one more general sense of the term allowing multiple edges,[8] a directed graph is sometimes defined to be an ordered triple G = (V, E, ϕ) comprising: To avoid ambiguity, this type of object may be called precisely a directed multigraph.
To avoid ambiguity, these types of objects may be called precisely a directed simple graph permitting loops and a directed multigraph permitting loops (or a quiver) respectively.
The edges of a directed simple graph permitting loops G is a homogeneous relation ~ on the vertices of G that is called the adjacency relation of G. Specifically, for each edge (x, y), its endpoints x and y are said to be adjacent to one another, which is denoted x ~ y.
It is an ordered triple G = (V, E, A) for a mixed simple graph and G = (V, E, A, ϕE, ϕA) for a mixed multigraph with V, E (the undirected edges), A (the directed edges), ϕE and ϕA defined as above.
[11] Such weights might represent for example costs, lengths or capacities, depending on the problem at hand.
In an undirected graph, an unordered pair of vertices {x, y} is called connected if a path leads from x to y.
Otherwise, the ordered pair is called weakly connected if an undirected path leads from x to y after replacing all of its directed edges with undirected edges.
A bipartite graph is a simple graph in which the vertex set can be partitioned into two sets, W and X, so that no two vertices in W share a common edge and no two vertices in X share a common edge.
A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.
Two edges of a directed graph are called consecutive if the head of the first one is the tail of the second one.
Normally, the vertices of a graph, by their nature as elements of a set, are distinguishable.
(Of course, the vertices may be still distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges.)
An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices).
As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.
In geographic information systems, geometric networks are closely modeled after graphs, and borrow many concepts from graph theory to perform spatial analysis on road networks or utility grids.
