Имея это в виду, дадим определение, которое пригодится далее в этом разделе: граф G = (V, E) называется разреженным, если |E| = O(|V|); граф G называется плотным, если |E| = O(|V|2).