Quel type de problèmes sur les graphes est plus rapide (en termes de big-O) à résoudre en utilisant des structures de données matricielles d'incidence au lieu de matrices d'adjacence plus répandues?Matrice d'incidence au lieu de matrice d'adjacence
La complexité de l'espace des structures sont:
contiguïté: O (V^2) Incidence: O (VE)
Avec la conséquence qu'une structure d'incidence économise de l'espace s'il y a beaucoup plus de sommets que les bords.
Vous pouvez regarder la complexité temporelle de certaines opérations graphiques typiques:
Trouver tous les sommets adjacents à un sommet: Adj: O (V) Inc: O (VE)
Vérifiez si deux les sommets sont adjacents: Adj: O (1) Inc: O (E)
Compte de la valence d'un sommet: Adj: O (V) Inc: O (E)
Et ainsi de suite. Pour tout algorithme donné, vous pouvez utiliser des blocs de construction comme ci-dessus pour calculer quelle représentation vous donne une meilleure complexité globale du temps. Comme note finale, l'utilisation d'une matrice de toute sorte est extrêmement inefficace pour tous les graphes, sauf les plus denses, et je recommande de ne pas utiliser, sauf si vous avez consciemment rejeté des alternatives comme les listes d'adjacence.
J'ai des graphiques très denses, avec presque toutes les connexions. – psihodelia
N'y a-t-il pas moyen de stocker efficacement la matrice éparse? – CMCDragonkai
Personnellement, je n'ai jamais trouvé une application réelle de la représentation de la matrice d'incidence dans un concours de programmation ou un problème de recherche. Je pense que cela peut être utile pour prouver certains théorèmes ou pour certains problèmes très spéciaux. Un livre donne un exemple de «comptage du nombre d'arbres couvrant» comme un problème dans lequel cette représentation est utile. Un autre problème avec cette représentation est que cela n'a aucun sens de la stocker, car il est vraiment facile de la calculer dynamiquement (pour répondre à ce que contient la cellule) à partir de la liste des arêtes.
Cependant, cela peut sembler plus utile dans les hypergraphes, mais seulement s'il est dense.
Donc, mon opinion est - il est utile uniquement pour les travaux théoriques.
Je ne suis pas sûr qu'il soit facile de trouver une limite supérieure de calcul basée sur la représentation sous-jacente. La plus grande partie de la complexité algorithmique sera exprimée par le nombre _ d'arêtes ou de sommets, et non par la représentation sous-jacente. Toute limite inférieure sur la complexité va s'appliquer si elle est mise en œuvre sur un crayon et papier ou sur un ordinateur. Pensez-vous qu'il existe des catégories spécifiques de problèmes que vous avez en tête, alors peut-être en parler et nous pouvons essayer de le comprendre? – Gian
La matrice d'incidence est MxN et la matrice d'adjacence est NxN si N est très grand et si votre graphe est très clairsemé, vous aurez MxN