그래프의 정점 수와 에지 밀도의 관계

밀도가 높은 그래프와 큰 그래프를 비교하여 big-O를 계산하는 방법을 알고 싶습니다. "간단히 말해서 알고리즘"에서는 O (E)가 O (V)이고 Dense 그래프의 경우 O (E)가 O (V^2)에 더 가깝다고 말합니다. 아무도 그 파생되는 방법을 알고 있습니까?그래프의 정점 수와 에지 밀도의 관계

출처

2012-02-20 iralight

파생되지 않았습니다. 정의입니다. 자체 루프가있는 완전히 연결된 (지시 된) 그래프에서 가장자리의 수 | E | = | V | ² 그래서 조밀 한 그래프의 정의가 합리적입니다. 스파 스 그래프의 정의는 O (| E |) = O (| V |)이므로 정점 당 일정한 최대 모서리 수가 있습니다.

에지의 수가 훨씬 더 작은 경우, 예를 들어. O (lg | V |)이면 여전히 O (| V |)입니다. 하나의 "semi-sparse"클래스의 그래프를 상상할 수 있습니다. E | = O (| V | lg | V |) 또는 이와 비슷한 것이지만 실제로 개인적으로 그러한 클래스를 직접 경험하지 못했습니다.

출처

2012-02-20 16:36:33

감사합니다. 자체 루프를 잊어 버렸습니다! 지금 의미가 있습니다 :) – iralight

@iralight : 동의 해 주셔서 감사 합니다만, 자체 루프는 문제가되지 않습니다. 자체 루프가없는 완전한 무 방향성 그래프에서도 에지 수는 O (| V | ²) 인 | V | × (| V | -1)/2입니다. –

Understood ... 그냥 개념적으로 자기 루프로 V^2 인접 행렬을 완전히 채울 수 있다는 것이 나에게 의미가 있었다. 명확한 주셔서 감사합니다 – iralight

그래프가 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이 노드이고 모든 링크가 가장자리 인 인터넷입니다.

그래프가 단순하지 않은 경우 을 |V|의 모든 함수와 바인딩 할 수 없습니다.

출처

2012-02-20 16:36:45 amit

밀도가 높은 그래프의 공식을 이해하는 데 문제가 있습니다. | E | = (| V | -1) + (| V | -2) + ... + 1 <= | V | * (| V | -1) = O (| V |^2). 이것은 (x-i)와 x^2의 합을 단순화하는 몇 가지 수학 공식을 기반으로합니까? – iralight

@iralight : 예, [산술 진행의 합계]입니다 (http://en.wikipedia.org/wiki/Arithmetic_progression#Sum). 첨부 된 링크를 살펴보십시오. – amit

감사합니다. – iralight

그래프의 정점 수와 에지 밀도의 관계

답변

관련 문제