Graph theory

A drawing of a graph.

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph (discrete mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Refer to the glossary of graph theory for basic definitions in graph theory.

Definitions

Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures.

Graph

A graph with three vertices and three edges.

In one restricted but very common sense of the term,[1][2] a graph is an ordered pair G = (V, E) comprising:

  • V a set of vertices (also called nodes or points);
  • E ⊆ {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} a set of edges (also called links or lines), which are unordered pairs of vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely an undirected simple graph.

In the edge {x, y}, the vertices x and y are called the endpoints of the edge. The edge is said to join x and y and to be incident on x and on y. A vertex may exist in a graph and not belong to an edge. A loop is an edge that joins a vertex to itself. Multiple edges are two or more edges that join the same two vertices.

In one more general sense of the term allowing multiple edges,[3][4] a graph is an ordered triple G = (V, E, ϕ) comprising:

  • V a set of vertices (also called nodes or points);
  • E a set of edges (also called links or lines);
  • ϕ: E → {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} an incidence function mapping every edge to an unordered pair of vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely an undirected multigraph.

Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex x is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph) {x, x} = {x} which is not in {{x, y} | (x, y) ∈ V2 ∧ x ≠ y}. So to allow loops the definitions must be expanded. For undirected simple graphs, E ⊆ {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} should become E ⊆ {{x, y} | (x, y) ∈ V2}. For undirected multigraphs, ϕ: E → {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} should become ϕ: E → {{x, y} | (x, y) ∈ V2}. To avoid ambiguity, these types of objects may be called precisely an undirected simple graph permitting loops and an undirected multigraph permitting loops respectively.

V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case. Moreover, V is often assumed to be non-empty, but E is allowed to be the empty set. The order of a graph is |V|, its number of vertices. The size of a graph is |E|, its number of edges. The degree or valency of a vertex is the number of edges that are incident to it, where a loop is counted twice.

In an undirected simple graph of order n, the maximum degree of each vertex is n − 1 and the maximum size of the graph is n(n − 1)/2.

The edges of an undirected simple graph permitting loops G induce a symmetric 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.

Directed graph

A directed graph with three vertices and four directed edges (the double arrow represents an edge in each direction).

A directed graph or digraph is a graph in which edges have orientations.

In one restricted but very common sense of the term,[5] a directed graph is an ordered pair G = (V, E) comprising:

  • V a set of vertices (also called nodes or points);
  • E ⊆ {(x, y) | (x, y) ∈ V2xy} a set of edges (also called directed edges, directed links, directed lines, arrows or arcs) which are ordered pairs of distinct vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely a directed simple graph.

In the edge (x, y) directed from x to y, the vertices x and y are called the endpoints of the edge, x the tail of the edge and y the head of the edge. The edge (y, x) is called the inverted edge of (x, y). The edge is said to join x and y and to be incident on x and on y. A vertex may exist in a graph and not belong to an edge. A loop is an edge that joins a vertex to itself. Multiple edges are two or more edges that join the same two vertices.

In one more general sense of the term allowing multiple edges,[5] a directed graph is an ordered triple G = (V, E, ϕ) comprising:

  • V a set of vertices (also called nodes or points);
  • E a set of edges (also called directed edges, directed links, directed lines, arrows or arcs);
  • ϕ: E → {(x, y) | (x, y) ∈ V2 ∧ x ≠ y} an incidence function mapping every edge to an ordered pair of distinct vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely a directed multigraph.

Directed graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex x is the edge (for a directed simple graph) or is incident on (for a directed multigraph) (x, x) which is not in {(x, y) | (x, y) ∈ V2xy}. So to allow loops the definitions must be expanded. For directed simple graphs, E ⊆ {(x, y) | (x, y) ∈ V2 ∧ x ≠ y} should become EV2. For directed multigraphs, ϕ: E → {(x, y) | (x, y) ∈ V2 ∧ x ≠ y} should become ϕ: EV2. 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.

Other Languages
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
Esperanto: Grafeteorio
euskara: Grafo teoria
한국어: 그래프 이론
Bahasa Indonesia: Teori graf
íslenska: Netafræði
latviešu: Grafu teorija
lietuvių: Grafų teorija
Bahasa Melayu: Teori graf
монгол: Графын онол
Nederlands: Grafentheorie
日本語: グラフ理論
norsk: Grafteori
norsk nynorsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
srpskohrvatski / српскохрватски: Teorija grafova
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
吴语: 图论
粵語: 圖論
中文: 图论