gráfico de torneio

Question

A competição é um grafo orientado (d�rafo) obtido através da atribuição de uma direcção para cada aresta em um gráfico completo não-dirigido. Isto é, é um grafo orientado em que cada par de vértices está ligada por uma única aresta dirigida.

Estrutura de dados é matriz de adjacência.

O que é um algoritmo para encontrar se o gráfico é um gráfico torneio?

Answer 1

Existem n ^ 2 entradas na matriz de adjacência, e você precisa a informação que está em todas as entradas para resolver o problema. (Você precisa os 1s para verificar se existem as bordas apropriadas, e os 0s para verificar se os back-bordas não existe.) Assim, desde que você tem que ler pelo menos N ^ 2 entradas da matriz, o problema global deve tomar pelo menos O (N ^ 2) tempo.

Em relação BFS procurar tentativas: se a sua travessia leva O (n ^ 2) - que ele vai, devido à necessidade de olhar para cima bordas na matriz de adjacência - então não importa se o cheque de volta de ponta é constante tempo, o algoritmo geral ainda é o (n ^ 2).

No entanto, outra maneira de olhar para este problema: uma vez que o número de arestas é igual ao número de possíveis pares de vértices, haverá n * (n-1) / 2 arestas, o que é O (n ^ 2) . O seu percurso é O (V + E), o qual, assim, é O (n + n ^ 2), e, assim, é O (n ^ 2).

Desde a época mais favorável para este algoritmo é O (n ^ 2), assim como você pode simplesmente percorrer a metade superior direita da matriz (acima da diagonal) e verificar que, para cada uma dessas entradas, ou um ) é 1, ou b) sua transposta equivalente é um.

Answer 2

Edit: perdeu a parte onde o gráfico foi completa .

Se M é a sua matriz de adjacência, Mt é a matriz transposta, ~M é a matriz com todos os "bits" invertidos, e A^B é o bit XOR a pouco entre os dois matriz.

Em seguida, a matriz é uma sse torneio:

~(M^Mt) = I

Answer 3

Para adicionar ao comentário de tonfa:

Breve : O algoritmo "para cada i ? j, verifique se exatamente um dos (i, j) e (j, i) está no gráfico" é assintoticamente ótima

Mais detalhes: Apenas ler na matriz de adjacência vai levá-lo O (n ² ) tempo. Portanto, não há maneira de resolver este problema de o (n ² ) tempo. Mas vamos ignorar a entrada.

Suponha que a matriz já está em memória. Para garantir que a versão sem direção de seu gráfico estiver completo, você tem que determinar de alguma forma que, para cada i ? j, pelo menos uma das bordas (i, j) e (j, i) está em seu gráfico. Como você tem apenas o gráfico de adjacência, isto significa que você terá que em algum ponto visita pelo menos um dos (i, j) ou (j, i) para cada i ? j. Não existe outra maneira de completude garantia. Verificando isso vai levar n (n + 1) / 2 = O (N ² ) passos.