Density (graph theory)

The density or edge density of a simple graph is graph theory , a ratio that reflects the ratio of actual existing edges indicating compared to potentially possible connections. The density can assume values ​​between 1 ( complete graph ) and 0 (graph without edges).

definition

Be a simple graph. Then is called ${\displaystyle G=(V,E)}$

${\displaystyle d(G):={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}}$

the density or edge density of the graph. The density is the ratio of the number of edges of the graph to the number of edges of the complete graph with the same number of nodes. There is also the definition to get clearer results for asymptotic statements for . ${\displaystyle d(G):={\frac {2|E|}{|V|^{2}}}}$ ${\displaystyle |V|\rightarrow \infty }$

use

The density of a graph plays a role in extremal graph theory . One of the questions in this area is what density of a graph is necessary to guarantee the existence of a certain sub-graph.

literature

• Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).