Graphique du tournoi

Question

Un tournoi est un graphe dirigé (digraphe) obtenu en assignant une direction à chaque bord dans un graphe complet non dirigé. C'est-à-dire qu'il s'agit d'un graphe orienté dans lequel chaque paire de sommets est connectée par un seul bord orienté.

La structure de données est la matrice d'adjacence.

Quel est l’algorithme permettant de déterminer si le graphique est un graphique de tournoi?

Answer 1

Il y a n ^ 2 entrées dans la matrice d'adjacence et vous avez besoin des informations contenues dans toutes les entrées pour résoudre le problème. (Vous avez besoin des 1 pour vérifier que les bords appropriés existent et des 0 pour vérifier que les arrière-bords n'existent pas.) Ainsi, comme vous devez lire au moins N ^ 2 entrées de la matrice, le problème général doit prendre au moins O (N ^ 2) fois.

En ce qui concerne les tentatives de recherche BFS: si votre parcours prend O (n ^ 2) - ce qui sera le cas, en raison de la nécessité de rechercher des arêtes dans la matrice d'adjacence - le fait que la vérification d'arrière-plan soit constante n'a aucune importance temps, l'algorithme global est toujours O (n ^ 2).

Encore une autre façon de regarder ce problème: puisque le nombre d’arêtes est égal au nombre de paires de sommets possibles, il y aura n * (n-1) / 2 arêtes, ce qui correspond à O (n ^ 2). . Votre parcours est O (V + E), qui est donc O (n + n ^ 2), et donc O (n ^ 2).

Étant donné que le meilleur temps pour cet algorithme est O (n ^ 2), vous pouvez aussi simplement parcourir la moitié supérieure droite de la matrice (au-dessus de la diagonale) et vérifier que pour chacune de ces entrées, ) il est égal à 1 ou b) son équivalent transposé est égal à 1.

Answer 2

Éditer: manque la partie où le graphique était complet.

Si M est votre matrice d'adjacence, Mt est la matrice transposée, ~ M est la matrice avec tous les "bits". inversé, et A ^ B est le x ou bit par bit entre les deux matrices.

Ensuite, la matrice est un tournoi si et seulement si:

~ (M ^ Mt) = I

Answer 3

Pour ajouter au commentaire de tonfa:

Brief : l'algorithme " pour chaque i & # 8800; j, vérifiez que l'un des (i, j) et (j, i) est exactement dans votre graphique " est asymptotiquement optimale.

Plus en détail: Lire simplement dans la matrice d’adjacence va prendre beaucoup de temps & # 937; (n ² ). Il n'y a donc aucun moyen de résoudre ce problème en un temps o (n ² ). Mais ignorons l'entrée.

Supposons que la matrice soit déjà en mémoire. Pour vous assurer que la version non dirigée de votre graphique est complète, vous devez en quelque sorte déterminer cela, pour chaque & # 8800; i & # 8800; j, au moins un des bords (i, j) et (j, i) est dans votre graphique. Comme vous n’avez que le graphe de contiguïté, cela signifie que vous devrez, à un moment donné, visiter au moins l’un des (i, j) ou (j, i) pour chaque i & # 8800; j. Il n'y a pas d'autre moyen de garantir l'exhaustivité. Cette vérification nécessitera n (n + 1) / 2 = O (n ² ) étapes.