Simple graph

In graph theory, a simple graph (also simple graph ) is an undirected graph without multiple edges and without loops .

So a simple graph is an ordered pair , where there is a finite set of vertices and a set of edges . The set is a subset of the 2-element subsets of  , that is, each edge is a set of two nodes. ${\displaystyle (V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle V}$

A simple graph with nodes can therefore have at most edges. If all these edges are present, the graph is called a complete graph . ${\displaystyle n}$ ${\displaystyle \textstyle {n \choose 2}={\frac {n(n-1)}{2}}}$ ${\displaystyle K_{n}}$

If the edges of the graph are additionally provided with values ​​(e.g. distances), one speaks of a weighting (also evaluation) of the edges and then of an edge-weighted graph .

example

Example graph: Germany and neighboring countries

The neighborhood relationships between Germany and its neighboring countries can be modeled as a simple graph . In this example, the set includes the countries and each edge indicates that two countries are adjacent. This graph is shown in the adjacent figure, with the nodes as points and the edges as connecting lines. Note that the graph only includes the existing relationships, but the position and size of the nodes and edges are freely selected. ${\displaystyle V}$

If one considers the formal definition of the graph as a pair, then the node set 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}. {Belgium, Germany} and {Germany, Belgium} denote the same edge. ${\displaystyle (V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$

literature

• Dieter Jungnickel : Graphs, Networks and Algorithms . 3. Edition. BI Wissenschaftsverlag, 1994, ISBN 3-411-14263-4 .

• Eric W. Weisstein : Simple Graph . In: MathWorld (English).