patternMinor
When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$
Viewed 0 times
thisthetagraphspossibleforwhenevendense
Problem
Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then why do even use $ |E| = \Theta (|V|^2)$?, understand that $\Theta$ is the correct(tightest) bound in asymptomatic notation. It seems to me that $|E| = \Theta (|V|^2)$ can never happen, so why do we use it?
Solution
Note that asymptotic bounds only apply to infinite sequences.
In this case, $|E| = \Theta(|V|^2)$ applies to an implicit infinite sequence of graphs $G_i=(V_i,E_i)$, meaning that there are two positive constants $c,c'$ such that, $c\cdot|V_i|^2 \leq |E_i| \leq c'\cdot|V_i|^2$ whenever $i$ is large enough.
This constraint can be satisfied. For every $i\in \mathbb N$, take $G_i$ to be the complete graph on $\{1,\ldots, i\}$. Hence, $G_i$ has exactly $i\cdot(i-1)/2$ edges. For large enough $i$, we have
$$
\frac{1}{4}i^2 \leq \frac{i\cdot(i-1)}{2} \leq \frac{1}{2}i^2
$$
So, we can say that $|E| = \Theta(|V|^2)$.
Another sequence could be constructed taking "almost complete" graphs, where we remove one edge from each complete graph $G_i$ in the previous sequence. This would still satisfy the bound.
We could even remove, say, $100*i$ edges from each $G_i$ (when possible) and still satisfy the bound. This is because we only care about $|E_i|$ growing with "quadratic speed".
In this case, $|E| = \Theta(|V|^2)$ applies to an implicit infinite sequence of graphs $G_i=(V_i,E_i)$, meaning that there are two positive constants $c,c'$ such that, $c\cdot|V_i|^2 \leq |E_i| \leq c'\cdot|V_i|^2$ whenever $i$ is large enough.
This constraint can be satisfied. For every $i\in \mathbb N$, take $G_i$ to be the complete graph on $\{1,\ldots, i\}$. Hence, $G_i$ has exactly $i\cdot(i-1)/2$ edges. For large enough $i$, we have
$$
\frac{1}{4}i^2 \leq \frac{i\cdot(i-1)}{2} \leq \frac{1}{2}i^2
$$
So, we can say that $|E| = \Theta(|V|^2)$.
Another sequence could be constructed taking "almost complete" graphs, where we remove one edge from each complete graph $G_i$ in the previous sequence. This would still satisfy the bound.
We could even remove, say, $100*i$ edges from each $G_i$ (when possible) and still satisfy the bound. This is because we only care about $|E_i|$ growing with "quadratic speed".
Context
StackExchange Computer Science Q#102829, answer score: 4
Revisions (0)
No revisions yet.