Связь между плотностью ребер и числом вершин графа
Я хочу понять, как вычислить big-O для плотного и разреженного графа. "Алгоритмы в двух словах" говорят, что для разреженного графа O(E) есть O(V), а для плотного графа O(E) ближе к O(V^2). Кто-нибудь знает, как это происходит?
2 ответа
Это не производное, это определение. В полностью связном (ориентированном) графе с самоциклами число ребер |E| = |V| 2, поэтому определение плотного графа разумно. Определение разреженного графа - это то, где O (|E|) = O (|V|), поэтому в каждой вершине имеется постоянное максимальное число ребер.
Обратите внимание, что если число ребер намного меньше, например, O (lg |V|), то это также O (|V|). Можно представить себе "полу разреженный" класс графов с |E| = O (|V| lg |V|) или что-то в этом роде, но я лично никогда не сталкивался с таким классом на практике.
Предполагая, что график прост - в худшем случае каждый узел может быть подключен ко всем |V|-1 другие узлы, что приводит к [в неориентированном графе:] |E| = (|V|-1) + (|V| -2) + ... + 1 <= |V| * (|V| -1) = O(|V|^2), И в ориентированном графе: |E| = |V| * (|V|-1) = O(|V|^2),
Хорошим примером плотного графа является клика, у которой есть все ребра.
Для разреженного графа - мы предполагаем, что число ребер, связанных с каждой вершиной, ограничено константой. Пусть эта константа будет k, Таким образом: |E| <= k* |V|и мы получаем |E| = O(|V|)
Хорошим примером разреженного графа является Интернет, где каждый URL является узлом, а каждая ссылка - ребром.
Обратите внимание, что если график не прост, вы не можете связать |E| с любой функцией |V|,