Graph (graph theory)

A graph (rarely also Count ) is in the graph theory an abstract structure representing a set of objects, together with the existing between these objects connections. The mathematical abstractions of the objects are called nodes (also corners ) of the graph. The paired connections between nodes are called edges (sometimes arcs ). The edges can be directed or undirected . Often graphs are clearly drawn by representing the nodes with points and the edges with lines.

Schematic structure of a family tree

Plan of the Vienna subway

Illustrative examples of graphs are a family tree or the subway network of a city (see illustrations). In a family tree, each node represents a member of the family and each edge is a connection between a parent and a child. In a subway network, each node represents a subway station and each edge a direct train connection between two stations.

Visualization of special graphs

digraph

In digraphs (from English directed graph , whether oriented or directed graphs called) will be held by lines marked edges by arrows, the arrow from its initial points to their end nodes. This shows that each edge of the graph can only be traversed in one direction.

Multigraph

Multigraph: Multiple edges are visualized by a weighted edge

In so-called multigraphs , two nodes can also be connected by several edges, which is not allowed in simple graphs . In addition, multigraphs may contain loops: edges that lead to the same node from which they start.

If nodes are connected by several edges, often only one edge is drawn and the number of edges between these two nodes is written as the edge weight on one edge. In the example there are 60 edges between nodes A and D . Instead of drawing all 60 edges, one edge is drawn with an edge weight of 60.

Hypergraph

In hypergraphs , an edge (also known as a hyperedge ) connects not only two, but several nodes at the same time. Hypergraphs can for example be represented by several planar graphs with indexing of the edges. Hypergraphs with few edges (so-called thin graphs ) are drawn in such a way that one draws a set of points that correspond to the nodes, and the points belonging to a hyperedge are then circled by a closed line, thus the subset of the nodes belonging to it indicates within all nodes. In the case of hypergraphs with many edges, however, this representation quickly becomes confusing. It is then less intuitive, but clearer, to represent a hypergraph as a bipartite meta-graph, with one of the two bipartition sets corresponding to the nodes of the hypergraph, the other bipartition set corresponding to the hyper-edges of the hypergraph. The edges between these two bipartition sets then symbolize the association of the nodes with the hyper-edges.

Definitions

A graph is an ordered pair , with a set of vertices ( English vertex / vertices , often also called corners ) and a set of edges ( English edge / edges , sometimes called arcs ). It is in ${\displaystyle G}$ ${\displaystyle (V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle E}$

• undirected graph without multiple edges a subset of all 2-element subsets of , ${\displaystyle V}$
• directed graph without multiple edges a subset of all pairs (i, j) thatarisefrom the Cartesian product , ${\displaystyle V\times V}$
• undirected graphs with combined multiple edges a multiset over the set of all 2-element subsets of , i.e. a function , ${\displaystyle W}$ ${\displaystyle V}$ ${\displaystyle E\colon W\to \mathbb {N} _{0}}$
• directed graphs with combined multiple edges a multiset over the Cartesian product , i.e. a function , ${\displaystyle V\times V}$ ${\displaystyle E\colon V\times V\to \mathbb {N} _{0}}$
• Directed graphs with independent multiple edges are any set, the elements of which are viewed as edges with the help of two functions that assign a source or target node to the elements (such a graph is the same as a functor , whereby the rather manageable category with two objects and two excellent arrows is) ${\displaystyle \mathrm {src} ,\mathrm {tgt} \colon E\to V}$ ${\displaystyle G\colon {\mathcal {G}}\to \mathbf {Set} }$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {G}}=\{V{\stackrel {\mathrm {src} }{\longleftarrow }}E{\stackrel {\mathrm {tgt} }{\longrightarrow }}V\}}$
• Hypergraphs are a subset of the power set of . ${\displaystyle V}$

Undirected graph without multiple edges

Directed graph without multiple edges

Undirected graph with multiple edges

Directed graph with multiple edges

The addition “without multiple edges” is usually left out and graphs with multiple edges are called multigraphs . In addition, the attribute “undirected” is usually not used and only directed graphs are explicitly identified. Undirected graphs without multiple edges are often called plain or simple . Another name for directed graphs is Digraph (Directed Graph).

Derived names

Instead of identifying the set of nodes and edges of a graph with the symbols and , one can also define general mappings and , which map a graph onto its set of nodes or set of edges. For two graphs and denote and as well as and . ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle G_{1}=(V_{1},E_{1})}$ ${\displaystyle G_{2}=(V_{2},E_{2})}$ ${\displaystyle V(G_{1}):=V_{1}}$ ${\displaystyle E(G_{1}):=E_{1}}$ ${\displaystyle V(G_{2})=V_{2}}$ ${\displaystyle E(G_{2})=E_{2}}$

The ambiguity and is accepted in this notation, although the figures show something different from the set of nodes and edges associated with it. As a convention, it is advisable to designate sets of nodes or edges with or without an argument , or to use an argument to designate the defined images. ${\displaystyle V(G)=V}$ ${\displaystyle E(G)=E}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle E}$

Is a graph, it is said in general is node or corner of when to hear. Edges are also known as ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle V(G)}$ ${\displaystyle e\in E(G)}$

• undirected edge of if is an undirected graph. ${\displaystyle G}$ ${\displaystyle G}$
• directed edge of if is a directed graph. ${\displaystyle G}$ ${\displaystyle G}$
• Hyperedge of if is a hypergraph. ${\displaystyle G}$ ${\displaystyle G}$

In an undirected edge , and are called end nodes of . In a directed edge is referred to as a start node and the end node of . ${\displaystyle e=\lbrace v,w\rbrace }$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle e}$ ${\displaystyle e=(v,w)}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle e}$

In multigraphs, the multiplicity of denotes . If true, then one speaks of a multi- or multiple edge . ${\displaystyle E(G)(e)}$ ${\displaystyle e}$ ${\displaystyle E(G)(e)>1}$

If an edge in directed graphs has the form , one speaks of a loop . If the loop in a multigraph is also a multiple edge, one speaks of a multiple loop . Directed graphs without loops are called loopless or loop-free . ${\displaystyle e}$ ${\displaystyle (v,v)}$ ${\displaystyle e}$ ${\displaystyle G}$

The number of nodes in a graph is the number of nodes, and the number of edges is the number of edges (in multigraphs one adds up over the multiplicity of the edges). ${\displaystyle n(G)=\vert V(G)\vert }$ ${\displaystyle G}$ ${\displaystyle m(G)=\vert E(G)\vert }$

Two nodes are called adjacent if an edge connects them.

Special cases

If the edge connects two nodes in a directed graph , and the edge connects the same nodes in the opposite direction, one can consider both together as an undirected edge within the directed graph. In the case of multiple edges, the multiples of both edges must match. ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$

If there is such an opposite edge in the graph for every edge of a directed graph, then it is a symmetric graph .

A graph whose vertex set is finite is called a finite graph . In contrast to this, a graph whose vertex set is infinite is called an infinite graph . Usually one only looks at finite graphs and therefore leaves out the attribute "finite" while explicitly identifying infinite graphs .

Subgraphs, paths and cycles

A directed graph with a cycle

A directed graph with no cycle

A subgraph of a graph only contains nodes and edges that are also contained in. A subgraph induced by a node set U contains the nodes from U and all edges from G between these nodes. ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle G}$

A sequence of pairs of different nodes in which successive nodes and in the graph are connected by an edge is called a path , sometimes also a path . If this is the only double knot, it is called a cycle or circle . A sequence of neighboring nodes in which nodes are allowed to repeat is called an edge sequence . The terms path, path, edge sequence, circle and cycle are defined differently in the literature. ${\displaystyle v_{1},\ldots ,v_{n}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$ ${\displaystyle v_{1}=v_{n}}$

Contains a directed graph does not cycle, it is called acyclic or cycle-free - that is a directed acyclic graph ( English DAG directed acyclic graph ). Such a graph can be expanded to a (finite and discrete) partial order by adding all edges that have the same starting and end nodes as paths , i.e. shortening the detours via other edges to a target node . This process is called the formation of the transitive envelope . A Hasse diagram is a directed acyclic graph in which the edges implied by the law of transitivity are omitted ( transitive reduction ).

Basic operations

When examining graph properties, it often happens that one has to apply simple operations to graphs in order to be able to write as compactly as possible and thus easier to understand. The usual operations of set theory (union, intersection, difference and complement) are particularly often applied to sets of nodes and edges of graphs, so that these are defined directly on graphs.

Are and graphs of the same type , so labeled ${\displaystyle G_{1}=(V_{1},E_{1})}$ ${\displaystyle G_{2}=(V_{2},E_{2})}$

• ${\displaystyle G_{1}+G_{2}}$ the graph that arises when one combines the set of nodes and edges,
• ${\displaystyle G_{1}-E_{2}}$the graph that results from subtracting from the set of edges and ${\displaystyle E_{2}}$ ${\displaystyle G_{1}}$
• ${\displaystyle G_{1}-V_{2}}$the graph that results from subtracting from the set of nodes and removing all edges that contain nodes from . ${\displaystyle V_{2}}$ ${\displaystyle G_{1}}$ ${\displaystyle V_{2}}$

Note the different definitions of the terms union set and difference set for sets and multisets . One also writes abbreviated

• ${\displaystyle G_{1}+E_{2}}$if is a subset of , ${\displaystyle V_{2}}$ ${\displaystyle V_{1}}$
• ${\displaystyle G_{1}+V_{2}}$if is empty or a subset of , ${\displaystyle E_{2}}$ ${\displaystyle E_{1}}$
• ${\displaystyle G_{1}+\{v,w\}}$if , ${\displaystyle G_{2}=(\{v,w\},\{\{v,w\}\})}$
• ${\displaystyle G_{1}+v}$if , ${\displaystyle G_{2}=(\{v\},\{\})}$
• ${\displaystyle G_{1}-\{v,w\}}$if and ${\displaystyle E_{2}=\{\{v,w\}\}}$
• ${\displaystyle G_{1}-v}$if . ${\displaystyle V_{2}=\{v\}}$

Edge contraction and the formation of the complement graph are further basic operations.

Remarks

Undirected graphs without multiple edges are special cases of hypergraphs. Multigraphs, in which there are no multiple edges, are not formally, but clearly equivalent to graphs without multiple edges, which is why these are also referred to as graphs without multiple edges. There is a bijective assignment between the two variants. In this sense, graphs without multiple edges are special cases of graphs with multiple edges. The situation is similar with undirected graphs, which in a certain sense are special cases of directed graphs. If a directed graph is symmetrical and loopless, it is also referred to as undirected , since there is also a simple one-to-one assignment between the two variants (see also adjacency matrix ).

Of course, undirected graphs can also be defined with loops, although the easiest way to define them is as (formal) special cases of directed graphs and omit the condition of no loops. Such graphs are rarely the subject of considerations in graph theory.

The most general type of graph are directed hypergraphs with multiple edges. Each graph type defined above can then be viewed as a special case of this. Such graphs are hardly at all the subject of considerations in graph theory, which is why they are not explained in more detail here.

If graphs are to be used as a representation of a situation, algorithms are required which are required for graph drawing . This discipline of computer science has continued to develop in recent years and provides solutions for different visualizations based on graphs.

Extensions

Graphs can be supplemented with further properties or information.

Colored graph

An extension of graphs to node-colored graphs is obtained by adding the tuple to a triple . is a mapping of into the set of natural numbers . This gives each node a clear color. ${\displaystyle G=(V,E)}$ ${\displaystyle (V,E)}$ ${\displaystyle (V,E,f)}$ ${\displaystyle f}$ ${\displaystyle V}$

Instead of the nodes, one can also color the edges in graphs without multiple edges and in hypergraphs and then speak of an edge- colored graph . To do this, the tuple is also expanded to a triple , but where (instead of ) is a mapping into the set of natural numbers . Each edge is clearly given a color. In graphs with multiple edges, this is in principle also possible, but more difficult to define, especially if multiple edges are to be assigned several different colors according to their multiplicity. ${\displaystyle (V,E)}$ ${\displaystyle (V,E,f)}$ ${\displaystyle f}$ ${\displaystyle E}$ ${\displaystyle V}$

Note that the terms “coloring” and “coloring” also have a more specific meaning in graph theory. Exactly one speaks of valid coloring , but usually leaves out the attribute “valid”.

Similarly, there are also named graphs in which nodes and / or edges have a name and assign a name to the images or the nodes or edges. The examples shown above are named graphs with nodes named with letters. This is often done with visualizations so that one can better discuss the graph. ${\displaystyle (V,E,f,g)}$ ${\displaystyle f}$ ${\displaystyle g}$

Weighted graph

Instead of vertex or edge-colored graphs, one speaks of vertex or edge-weighted graphs if the mapping is to real numbers instead of the natural numbers . Node-colored or edge-colored graphs are special cases of node-weighted or edge-weighted graphs. ${\displaystyle f}$

The name or as a weight of the node and the edge . To differentiate, one also speaks of node weight or edge weight . Such a weighting is necessary if the information about node relationships is insufficient. For example, if one understands the road network (simplified) as a graph (locations are nodes, the roads connecting locations are edges), a weighting of the edges could provide information about the distance between two locations. The edge weights of a graph can be collected in a square weight matrix , the adjacency matrix . ${\displaystyle f(v)}$ ${\displaystyle f(e)}$ ${\displaystyle v}$ ${\displaystyle e}$

Figures between graphs

Finally, mappings between graphs can also be defined. Particularly interesting are those that are compatible with the structure of the two , so-called "homomorphisms" .

To this and be graphs of the same type. A mapping is called homomorphism between and , if the following applies: ${\displaystyle G_{1}=\left(V_{1},E_{1}\right)}$ ${\displaystyle G_{2}=\left(V_{2},E_{2}\right)}$ ${\displaystyle p\colon V_{1}\to V_{2}}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

• In undirected graphs without multiple edges :
  If an edge is of , then an edge is of . ${\displaystyle \{v,w\}}$ ${\displaystyle G_{1}}$ ${\displaystyle \{p(v),p(w)\}}$ ${\displaystyle G_{2}}$
• In directed graphs without multiple edges:
  If edge is of , then edge is of . ${\displaystyle (v,w)}$ ${\displaystyle G_{1}}$ ${\displaystyle (p(v),p(w))}$ ${\displaystyle G_{2}}$
• In undirected graphs with multiple edges : d. H. two corners are connected with at most as many edges as their image corners.
  ${\displaystyle E_{1}(\{v,w\})\leq E_{2}(\{p(v),p(w)\})}$
• In a directed graph with multiple edges: .
  ${\displaystyle E_{1}(v,w)\leq E_{2}(p(v),p(w))}$
• In a directed graph with independent multiple edges: has an associated partner and for all edges applies and (be and regarded as functors is a Graphhomomorphismus just a natural transformation ).
  ${\displaystyle p}$ ${\displaystyle q\colon E_{1}\to E_{2}}$ ${\displaystyle e\in E_{1}}$ ${\displaystyle \mathrm {src} _{2}(q(e))=p(\mathrm {src} _{1}(e))}$ ${\displaystyle \mathrm {tgt} _{2}(q(e))=p(\mathrm {tgt} _{1}(e))}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$
• In hypergraphs :
  If edge is of , then edge is of . ${\displaystyle \{v_{1},\cdots ,v_{k}\}}$ ${\displaystyle G_{1}}$ ${\displaystyle \{p(v_{1}),\cdots ,p(v_{k})\}}$ ${\displaystyle G_{2}}$

The image p ( G ₁ ) is then a subgraph of G ₂ . If p is reversible and the inverse function is also a homomorphism, then p is an isomorphism of graphs.

It should be noted that the nodes have priority over the edges, in that p is specified as a function only on the node, which only has an induced effect on the edges.

Combinatorics

The number of simple undirected graphs with nodes increases rapidly with the number of nodes and is the same . So it increases exponentially to the number of edges of the complete graph . If the nodes are not numbered, i.e. isomorphic graphs are not counted, this number is roughly proportional to , because for most isomorphism classes all graphs that result from the permutation of the numbered nodes are different. The following table shows the numbers determined with the help of a computer for : ${\displaystyle n}$ ${\displaystyle 2^{\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle {\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle K_{n}}$ ${\displaystyle {\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle n!}$ ${\displaystyle n\leq 8}$

Number of simple undirected graphs
n	with numbered nodes	without numbered nodes
1	1	1
2	2	2
3	8th	4th
4th	64	11
5	1,024	34
6th	32,768	156
7th	2,097,152	1,044
8th	268.435.456	12,346

Data structures

Undirected graph	Adjacency matrix
	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}$

There are essentially two common forms for representing graphs in the computer : the adjacency matrix (also neighborhood matrix ) and the adjacency list (neighborhood list). The significance of the two representations is that practically every algorithmic solution of graph-theoretical problems makes use of at least one of the two representations. Another, but seldom used, option for displaying graphs in the computer is the incidence matrix , which is also known as the node-edge matrix.

Incidence matrices are more complex to implement and manage, but they offer a number of advantages over adjacency matrices. On the one hand, with a fixed number of edges, they always use a lot of storage space in terms of the number of nodes, which is particularly advantageous for thin graphs (i.e. graphs with few edges), while the adjacency matrix has a quadratic space requirement with regard to the number of nodes (but more compact for dense graphs, i.e. graphs with many edges). On the other hand, many graph theoretic problems can only be solved with adjacency lists in linear time . In practice, therefore, this form of representation is usually used.

See also

• Graph games
• Small world phenomenon (small world network)
• Scale-free network
• Random graph
• Band graph
• Quantity system

literature

• Thomas H. Cormen, Charles Leiserson , Ronald L. Rivest , Clifford Stein: Algorithms - An Introduction . 2nd Edition. Oldenbourg Wissenschaftsverlag, Munich 2007, ISBN 978-3-486-58262-8 , p. 531-533 .
• Reinhard Diestel : graph theory . 4th edition. Springer, Berlin a. a. 2010, ISBN 978-3-642-14911-5 ( online: 4th Electronic Edition 2010, Free preview version - first edition: 1996).
• Jürgen Ebert: Efficient graph algorithms . In: Study Texts - Computer Science . Akademische Verlags-Gesellschaft, Wiesbaden 1981, ISBN 3-400-00424-3 (also habilitation thesis at the University of Osnabrück 1982).
• Dieter Jungnickel : Graphs, Networks and Algorithms . 3rd completely revised and expanded edition. BI-Wissenschafts-Verlag, Mannheim u. a. 1994, ISBN 3-411-14263-4 ( table of contents [PDF; 1,2 MB ]).
• Manfred Nitzsche: Graphs for Beginners. Around the house of Nicholas . In: Studies . 3rd, revised and expanded edition. Vieweg + Teubner, Wiesbaden 2009, ISBN 978-3-8348-0813-4 .

Individual evidence

1. ^ Duden online: Graph, Graf, der , Bibliographisches Institut GmbH, 2013.
2. ↑ ^{a b c d} Reinhard Diestel : Graph theory . 4th edition. Springer, Berlin a. a. 2010, ISBN 978-3-642-14911-5 , pp. 1–34 ( online: 4th electronic edition 2010 - first edition: 1996).
3. ↑ Directed Graphs . In: Claude Sammut, Geoffrey I. Webb (Ed.): Encyclopedia of Machine Learning . Springer US, 2010, p. 279 , doi : 10.1007 / 978-0-387-30164-8_218 .
4. ↑ ^{a b} for directed graphs: in the same direction
5. ↑ Brigitte Werners: Basics of Operations Research . 3. Edition. Springer, Berlin Heidelberg 2013, ISBN 978-3-642-40101-5 , p. 175-209 .
6. ↑ Follow A000088 in OEIS