What is the definition of the density of a graph?

This Wikipedia link on dense graphs might contain what you're looking for.

In particular, for undirected simple graphs, the graph density is defined as $$D = \frac{2|E|}{|V|(|V| - 1)}.$$

While for directed simple graphs, the graph density is defined as $$D = \frac{|E|}{|V|(|V| - 1)},$$ where $|E|$ is the number of edges and $|V|$ is the number of vertices in the graph.

Note that the maximum number of edges is $$\frac{|V|(|V| - 1)}{2}.$$


Yeah! It's right that graph density = no of edges/total no of possible edges.

In directed graph total no of possible edges is |v|*|v-1|,
In undirected graph total no of possible edges is |v|*|v-1|/2.

for e.g. -> let's say there are 3 nodes.All possible edges in undirected graph is 1-2,2-3,1-3 where as in directed graph all edges are 1->2,2->1, 2->3,3->2,1->3,3->1.

For undirected simple graphs, the graph density is defined as D=2|E|/|V|(|V|−1). While for directed simple graphs, the graph density is defined as D=|E|/|V|(|V|−1)

Tags:

Graph Theory

Related

Differential equations: how does separation of variables really work? Sup Norm and Uniform Convergence ${\rm Aut}(G)$ is cyclic $\implies G$ is abelian Why are removable discontinuities even discontinuities at all? Evaluating $\int\frac{x^4}{x-1} \, dx$ Prove that if each row of a matrix sums to zero, then it has no inverse. Proof that there are infinitely many prime numbers $p$ such that $p-2$ is not prime. We roll a six-sided die ten times. What is the probability that the total of all ten rolls is divisible by 6? least common multiple of $\{1,2,...,n\}$ is bigger than $2^{n-1}$ Abelian group as direct product of its p-Sylow subgroups. Prove that the natural map $\alpha : \text{Hom}(X,\text{Spec} A) \rightarrow \text{Hom}(A,\Gamma(X,\mathcal{O}_X))$ is an isomorphism Developing Mathematic Intuition

Recent Posts