Indiscrete mathematics, particularly ingraph theory, agraph is a structure consisting of aset of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions calledvertices (also callednodes orpoints) and each of the related pairs of vertices is called anedge (also calledlink orline).[1] Typically, a graph is depicted indiagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.
The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any personA can shake hands with a personB only ifB also shakes hands withA. In contrast, if an edge from a personA to a personB means thatA owes money toB, then this graph is directed, because owing money is not necessarily reciprocated.
Graphs are the basic subject studied by graph theory. The word "graph" was first used in this sense byJ. J. Sylvester in 1878 due to a direct relation between mathematics andchemical structure (what he called a chemico-graphical image).[2][3]
Agraph (sometimes called anundirected graph to distinguish it from adirected graph, or asimple graph to distinguish it from amultigraph)[4][5] is apairG = (V,E), whereV is a set whose elements are calledvertices (singular: vertex), andE is a set of unordered pairs of vertices, whose elements are callededges (sometimeslinks orlines).
The verticesu andv of an edge{u,v} are called the edge'sendpoints. The edge is said tojoinu andv and to beincident on them. A vertex may belong to no edge, in which case it is not joined to any other vertex and is calledisolated. When an edge exists, the verticesu andv are calledadjacent.
Amultigraph is a generalization that allows multiple edges to have the same pair of endpoints. In some texts, multigraphs are simply called graphs.[6][7]
Sometimes, graphs are allowed to containloops, which are edges that join a vertex to itself. To allow loops, the pairs of vertices inE must be allowed to have the same node twice. Such generalized graphs are calledgraphs with loops or simplygraphs when it is clear from the context that loops are allowed.
Generally, the vertex setV is taken to be finite (which implies that the edge setE is also finite). Sometimesinfinite graphs are considered, but they are usually viewed as a special kind ofbinary relation, because most results on finite graphs either do not extend to the infinite case or need a rather different proof.
Anempty graph is a graph that has anempty set of vertices (and thus an empty set of edges). Theorder of a graph is its number|V| of vertices, usually denoted byn. Thesize of a graph is its number|E| of edges, typically denoted bym. However, in some contexts, such as for expressing thecomputational complexity of algorithms, the termsize is used for the quantity|V| + |E| (otherwise, a non-empty graph could have size 0). Thedegree orvalency of a vertex is the number of edges that are incident to it; for graphs with loops, a loop is counted twice.
In a graph of ordern, the maximum degree of each vertex isn − 1 (orn + 1 if loops are allowed, because a loop contributes 2 to the degree), and the maximum number of edges isn(n − 1)/2 (orn(n + 1)/2 if loops are allowed).
The edges of a graph define asymmetric relation on the vertices, called theadjacency relation. Specifically, two verticesx andy areadjacent if{x,y} is an edge. A graph is fully determined by itsadjacency matrixA, which is ann ×n square matrix, withAij specifying the number of connections from vertexi to vertexj. For a simple graph,Aij is either 0, indicating disconnection, or 1, indicating connection; moreoverAii = 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 allAii being equal to a positive integer, and multigraphs (with multiple edges between vertices) will be characterized by some or allAij being equal to a positive integer. Undirected graphs will have asymmetric adjacency matrix (meaningAij =Aji).
E, aset ofedges (also calleddirected edges,directed links,directed lines,arrows, orarcs), which areordered pairs of distinct vertices:.
To avoid ambiguity, this type of object may be called precisely adirected simple graph.
In the edge(x,y) directed fromx toy, the verticesx andy are called theendpoints of the edge,x thetail of the edge andy thehead of the edge. The edge is said tojoinx andy and to beincident onx and ony. A vertex may exist in a graph and not belong to an edge. The edge(y,x) is called theinverted edge of(x,y).Multiple edges, not allowed under the definition above, are two or more edges with both the same tail and the same head.
In one more general sense of the term allowing multiple edges,[8] a directed graph is sometimes defined to be an ordered tripleG = (V,E,ϕ) comprising:
E, aset ofedges (also calleddirected edges,directed links,directed lines,arrows orarcs);
ϕ, anincidence function mapping every edge to anordered pair of vertices (that is, an edge is associated with two distinct vertices):.
To avoid ambiguity, this type of object may be called precisely adirected multigraph.
Aloop is an edge that joins a vertex to itself. Directed graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex to itself is the edge (for a directed simple graph) or is incident on (for a directed multigraph) which is not in. So to allow loops the definitions must be expanded. For directed simple graphs, the definition of should be modified to. For directed multigraphs, the definition of should be modified to. To avoid ambiguity, these types of objects may be called precisely adirected simple graph permitting loops and adirected multigraph permitting loops (or aquiver) respectively.
The edges of a directed simple graph permitting loopsG is ahomogeneous relation ~ on the vertices ofG that is called theadjacency relation ofG. Specifically, for each edge(x,y), its endpointsx andy are said to beadjacent to one another, which is denotedx ~y.
A mixed graph with three vertices, two directed edges, and an undirected edge.
Amixed graph is a graph in which some edges may be directed and some may be undirected. It is an ordered tripleG = (V,E,A) for amixed simple graph andG = (V,E,A,ϕE,ϕA) for amixed multigraph withV,E (the undirected edges),A (the directed edges),ϕE andϕA defined as above. Directed and undirected graphs are special cases.
A weighted graph with ten vertices and twelve edges
Aweighted graph or anetwork[9][10] is a graph in which a number (the weight) is assigned to each edge.[11] Such weights might represent for example costs, lengths or capacities, depending on the problem at hand. Such graphs arise in many contexts, for example inshortest path problems such as thetraveling salesman problem.
One definition of anoriented graph is that it is a directed graph in which at most one of(x,y) and(y,x) may be edges of the graph. That is, it is a directed graph that can be formed as anorientation of an undirected (simple) graph.
Some authors use "oriented graph" to mean the same as "directed graph". Some authors use "oriented graph" to mean any orientation of a given undirected graph or multigraph.
Aregular graph is a graph in which each vertex has the same number of neighbours, i.e., every vertex has the same degree. A regular graph with vertices of degreek is called ak‑regular graph or regular graph of degreek.
In an undirected graph, an unordered pair of vertices{x,y} is calledconnected if a path leads fromx toy. Otherwise, the unordered pair is calleddisconnected.
Aconnected graph is an undirected graph in which every unordered pair of vertices in the graph is connected. Otherwise, it is called adisconnected graph.
In a directed graph, an ordered pair of vertices(x,y) is calledstrongly connected if a directed path leads fromx toy. Otherwise, the ordered pair is calledweakly connected if an undirected path leads fromx toy after replacing all of its directed edges with undirected edges. Otherwise, the ordered pair is calleddisconnected.
Astrongly connected graph is a directed graph in which every ordered pair of vertices in the graph is strongly connected. Otherwise, it is called aweakly connected graph if every ordered pair of vertices in the graph is weakly connected. Otherwise it is called adisconnected graph.
Ak-vertex-connected graph ork-edge-connected graph is a graph in which no set ofk − 1 vertices (respectively, edges) exists that, when removed, disconnects the graph. Ak-vertex-connected graph is often called simply ak-connected graph.
Abipartite graph is a simple graph in which the vertex set can bepartitioned into two sets,W andX, so that no two vertices inW share a common edge and no two vertices inX share a common edge. Alternatively, it is a graph with achromatic number of 2.
In acomplete bipartite graph, the vertex set is the union of two disjoint sets,W andX, so that every vertex inW is adjacent to every vertex inX but there are no edges withinW orX.
Apath graph orlinear graph of ordern ≥ 2 is a graph in which the vertices can be listed in an orderv1,v2, …,vn such that the edges are the{vi,vi+1} wherei = 1, 2, …,n − 1. Path graphs can be characterized as connected graphs in which the degree of all but two vertices is 2 and the degree of the two remaining vertices is 1. If a path graph occurs as asubgraph of another graph, it is apath in that graph.
Acycle graph orcircular graph of ordern ≥ 3 is a graph in which the vertices can be listed in an orderv1,v2, …,vn such that the edges are the{vi,vi+1} wherei = 1, 2, …,n − 1, plus the edge{vn,v1}. Cycle graphs can be characterized as connected graphs in which the degree of all vertices is 2. If a cycle graph occurs as a subgraph of another graph, it is a cycle or circuit in that graph.
Atree is an undirected graph in which any twovertices are connected byexactly onepath, or equivalently aconnectedacyclic undirected graph.
Aforest is an undirected graph in which any two vertices are connected byat most one path, or equivalently an acyclic undirected graph, or equivalently adisjoint union of trees.
Two vertices of a graph are calledadjacent if they share a common edge. Two vertices of a directed graph are calledconsecutive if the head of the first one is the tail of the second one. Similarly, two vertices are calledadjacent if they share a common edge (consecutive if the first one is the tail and the second one is the head of an edge), in which case the common edge is said tojoin the two vertices. An edge and a vertex on that edge are calledincident.
The graph with only one vertex and no edges is called thetrivial graph. A graph with only vertices and no edges is known as anedgeless graph. The graph with no vertices and no edges is sometimes called thenull graph orempty graph, but the terminology is not consistent and not all mathematicians allow this object.
Normally, the vertices of a graph, by their nature as elements of a set, are distinguishable. This kind of graph may be calledvertex-labeled. However, for many questions it is better to treat vertices as indistinguishable. (Of course, the vertices may be still distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges.) The same remarks apply to edges, so graphs with labeled edges are callededge-labeled. Graphs with labels attached to edges or vertices are more generally designated aslabeled. Consequently, graphs in which vertices are indistinguishable and edges are indistinguishable are calledunlabeled. (In the literature, the termlabeled may apply to other kinds of labeling, besides that which serves only to distinguish different vertices or edges.)
Thecategory of directed multigraphs permitting loops is thecomma category Set ↓D whereD: Set → Set is thefunctor taking a sets tos ×s.
In ahypergraph, an edge can join any positive number of vertices.
An undirected graph can be seen as asimplicial 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.
^Trudeau, Richard J. (1993).Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19.ISBN978-0-486-67870-2.Archived from the original on 5 May 2019. Retrieved8 August 2012.A graph is an object consisting of two sets called itsvertex set and itsedge set.
J. J. Sylvester (February 7, 1878)"Chemistry and algebra",Archived 2023-02-04 at theWayback MachineNature,17 : 284.doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by agraph precisely identical with a Kekuléan diagram or chemicograph."
^Strang, Gilbert (2005),Linear Algebra and Its Applications (4th ed.), Brooks Cole,ISBN978-0-03-010567-8
^Lewis, John (2013),Java Software Structures (4th ed.), Pearson, p. 405,ISBN978-0-13-325012-1
^Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991).Foundations of Discrete Mathematics (International student ed.). Boston: PWS-KENT Pub. Co. p. 463.ISBN978-0-53492-373-0.Aweighted graph is a graph in which a numberw(e), called itsweight, is assigned to each edgee.
