토너먼트 그래프

Question

토너먼트 방향 그래프(digraph)에 의해 얻어에 할당하는 방향으로 각 가장자리에 있는 지시되지 않은 완전한 그래프입니다.즉,그것은 방향 그래프에서는 모든 쌍의 정점을 연결되어 있는 단일 감독의 가장자리입니다.

데이터 구조은 인접 매트릭스입니다.

What s 는 알고리즘을 찾으면 그 대회 graph?

Answer 1

있다 n^2 항목에서의 인접성 매트릭스,그리고 당신은 필요한 정보에 있는 모든 항목의 문제를 해결합니다.(당신이 필요로 1 의하는지 확인하려면 적절한 가장자리가 존재하 0s 하는지 확인하려면 다시-가장자리가 존재하지 않습니다.) 따라서 이 자료를 읽어보에 적어도 N^2 항에서 매트릭스,전반적인 문제를 가져야 합니다 적어도 O(N^2)시간입니다.

에 대한 대금 검색을 시도한다:하는 경우 횡단 소요 O(n^2)-는 것으로 볼 필요가까지 가장자리에 인접성 matrix-그것은 중요하지 않을 경우 다시장 확인하는 일정한 시간,전체적인 알고리즘은 여전히 O(n^2).

아직에서 볼 수있는 또 다른 방법이 이 문제는:의 수 있기 때문에 가장자리와 같은 수의 가능한 한 쌍의 꼭지점이있을 것이다,n*(n-1)/2,가장자리는 O(n^2).귀하의 traversal O(V+E)에 따라서는 O(n+n^2)며,이에 따라 O(n^2).

이후 최고의 경간에 대한 이 알고리즘 O(n^2)할 수 있습니다 또한 단순히 반복을 통해 우측 상단의 절반을 매트릭스(상 대각선)및 확인에 대한 각각의 항목 중 하나)그것은 1,또는 b)의 전당은 1 입니다.

Answer 2

편집 : 그래프가 완료된 부분을 놓쳤습니다.

만약에 M 인접 매트릭스입니다. Mt 변환 된 매트릭스, ~M 모든 "비트"가 거꾸로 된 매트릭스이며 A^B 두 행렬 사이의 XOR 비트입니다.

그런 다음 매트릭스는 토너먼트 IFF입니다.

~(M^Mt) = I

Answer 3

Tonfa의 의견에 추가하려면 :

짧은: 알고리즘 "각 i ≠ j에 대한 알고리즘은 (i, j) 중 하나와 (j, i) 중 하나가 그래프에 있는지 확인하십시오.

자세한 세부 사항:인접성 매트릭스를 읽으려면 ω (n²) 시각. 따라서이 문제를 해결할 방법이 없습니다 (n²) 시각. 그러나 입력을 무시합시다.

매트릭스가 이미 메모리에 있다고 가정 해 봅시다. 그래프의 방향이없는 버전이 완료되도록하려면 어떻게 든 각 i ≠ j에 대해 최소한 하나의 가장자리 (i, j) 및 (j, i)가 그래프에 있다고 판단해야합니다. 인접 그래프 만 가지고 있으므로, 이것은 각 i ≠ j에 대해 어느 시점에서 (i, j) 또는 (j, i) 중 하나 이상을 방문해야한다는 것을 의미합니다. 완전성을 보장하는 다른 방법은 없습니다. 이것을 확인하면 n (n+1)/2 = O (n²) 단계.