связь между плотностью ребер и числом вершин в графе

Question

Я хочу понять, как вычислить big-O для плотного или редкого графика. «Алгоритмы в двух словах» говорят, что для разреженного графа O (E) есть O (V), а для плотного графа O (E) ближе к O (V^2). Кто-нибудь знает, как это происходит?

Answer 1

Это не производное, это определение. В полностью подключенном (направленном) графе с автопилотами число ребер | E | = | V | ², поэтому определение плотного графа является разумным. Определение разреженного графа - это такое, где O (| E |) = O (| V |), поэтому существует постоянное максимальное количество ребер на вершину.

Обратите внимание, что если количество ребер намного меньше, т.е. O (lg | V |), то это все еще O (| V |). Можно представить себе «полурефлекторный» класс графов с | E | = O (| V | lg | V |) или что-то в этом роде, но лично я никогда не сталкивался с таким классом на практике.

Answer 2

Предполагая, что график simple - в худшем случае каждый узел может быть подключен ко всем |V|-1 другим узлам, в результате чего [в ориентировочном графике:] |E| = (|V|-1) + (|V| -2) + ... + 1 <= |V| * (|V| -1) = O(|V|^2). И в направленном графике: |E| = |V| * (|V|-1) = O(|V|^2).

Хорошим примером для плотного графа является clique - которые имеют все края.

Для разреженного графа мы предполагаем, что число ребер, связанных с каждой вершиной, ограничено константой. Пусть эта константа равна k. Таким образом: |E| <= k* |V|, и мы получаем |E| = O(|V|)

Хорошим примером для разреженного графика является интернет, где каждый URL-адрес является узлом, а каждая ссылка является ребром.

Обратите внимание, что если график не является простым, вы не можете связать |E| с любой функцией |V|.