Graph (mathematics)#Simple graph

A simple graph (also directed graph ) is in graph theory an undirected graph without multiple edges and without loops.

A simple graph is thus an ordered pair, where is a finite set of nodes and a set of edges is. The amount is subset of the subsets of 2, that is, each edge is a set of two nodes.

A simple graph with nodes can therefore have at most edges. They are all edge exists, the graph is referred to as the complete graph.

If the edges of the graph are additionally provided with values ​​(eg distances), one speaks of a weight (including evaluation ) of the edges and then by an edge-weighted graph.

Example

The neighborhood relations between Germany and its neighbors can be modeled as a simple graph. In this example, the amount includes the countries and each edge represents that two countries are adjacent. In the adjacent figure, this graph is presented, in which the nodes are drawn as points and edges as connecting lines. Note that the graph only includes the existing relationships, whereas the position and size of the nodes and edges are chosen freely.

Looking at the formal definition of the graph as a pair then the set of nodes is given by the set { Belgium, Denmark, Germany, France, Luxembourg, Netherlands, Austria, Poland, Switzerland, Czech Republic }. Examples of edges in the set are { Belgium, Germany }, { Austria, Switzerland } and { Germany, Poland }. This call { Belgium, Germany } and { Germany, Belgium } the same edge.