adplus-dvertising

Introduction et représentations de graphes

Introduction et représentations de graphes

Un graphe est une structure de données non linéaire constituée de nœuds et d'arêtes. Les nœuds sont parfois appelés sommets et les arêtes sont des lignes ou des arcs reliant deux nœuds quelconques du graphe. Plus formellement, un graphe peut être défini comme:

Un graphe G est représenté par un couple (S, A) S est un ensemble fini et A une relation binaire sur S. L’ensemble S est l’ensemble des sommets de G et A est l’ensemble des arcs de G.

Il existe deux types de graphes :

  • graphe orienté : les relations sont orientées et on parle d’arc. Un arc est représenté par un couple de sommets ordonnés.
  • Graphe non orienté: les relations ne sont pas orientées et on parle alors d’arêtes.Une arête est représentée par une paire de sommets non ordonnés.

Vocabulaire

  • Une boucle est un arc qui relie un sommet à lui-même. Dans un graphe non orienté les boucles sont interdites et chaque arête est donc constituée de deux sommets distincts.
  • Degré d’un sommet : Dans un graphe non orienté, le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes.
  • Degré sortant d’un sommet : Dans un graphe orienté, le degré sortant d’un sommet est le nombre d’arcs qui en partent,
  • Degré rentrant d’un sommet : le degré entrant est le nombre d’arcs qui y arrivent et le degré est la somme du degré entrant et du degré sortant.
  • Chemin : Dans un graphe orienté G = (S,A), un chemin de longueur k d’un sommet u à un sommet v est une séquence (u0,u1,..., ukde sommets telle que u = u0, v = uk et (ui-1, uiappartient à A pour tout i. Un chemin est élémentaire si ses sommets sont tous distincts.
  • Circuit : Dans un graphe orienté G=(S,A), un chemin (u0,u1, .... ,ukforme un circuit si u0 =uk et si le chemin contient au moins un arc. Ce circuit est élémentaire si les sommets u1, ..., uk sont distincts. Une boucle est un circuit de longueur 1.
  • Cycle : Dans le cas non orienté, un chemin v0v1, v1v2, ..., vk−1vk est un cycle si v0 = vk et si une arête n'apparait pas deux fois avec une orientation différente. Par exemple v0v1, v1v0 n'est pas un cycle dans le cas non orienté. Ce cycle est élémentaire si les sommets u1, ..., uk sont distincts. Un graphe sans cycle est dit acyclique.
  • Graphe connexe : Un graphe non orienté est connexe si chaque paire de sommets est reliée par une chaîne. Les composantes connexes d’un graphe sont les classes d’équivalence de sommets induites par la relation « est accessible à partir de ».

  • Graphe fortement connexe : Un graphe orienté est fortement connexe si pour tout couple de sommets x, y il existe un chemin reliant x à y.
    Remarque : la définition implique que si x et y sont deux sommets d’un graphe fortement connexe, alors il existe un chemin de x à y et un chemin de y à x.

Les graphes sont utilisés pour résoudre de nombreux problèmes de la vie réelle. Les graphes sont utilisés pour représenter les réseaux. Les réseaux peuvent inclure des chemins dans une ville ou un réseau téléphonique ou un réseau de circuits. Les graphes sont également utilisés dans les réseaux sociaux tels que linkedIn et Facebook. Par exemple, sur Facebook, chaque personne est représentée par un sommet (ou nœud). Chaque nœud est une structure et contient des informations telles que l’identité de la personne, le nom, email, les paramètres régionaux, etc.

Représentations

Voici les deux représentations les plus couramment utilisées pour représenter un graphe.

  • Matrice d'adjacence
  • Liste d'adjacence

Matrice d'adjacence

La matrice d'adjacence est un tableau 2D de taille (V x V) V est le nombre de sommets d'un graphe.
Si le tableau 2D est adj[][], une cellule adj[i][j]=1 indique qu’il existe une arête du sommet i au sommet j.
La matrice d'adjacence pour le graphe non orienté est toujours symétrique.
La matrice d'adjacence est également utilisée pour représenter des graphes pondérés. Si adj[i][j]=w, il existe alors une arête allant du sommet i au sommet avec un poids w.

Avantages :

La représentation est plus facile à mettre en œuvre et à maintenir. Supprimer une arête prend un temps O(1). Des requêtes comme s’il existe une arête allant du sommet «u» au sommet «v» sont efficaces et peuvent être effectuées en O(1).

Inconvénients :
Consomme plus D'espace O(V2). Même si le graphe est clairsemé(contient moins d'arêtes), il consomme le même espace. 
Ajouter un sommet a un temps O(V2).

Liste d'adjacence

Un tableau de listes est utilisé. La taille du tableau est égale au nombre de Sommets. Si le tableau est tab[]. Une cellule tab[i] représente la liste des sommets adjacents au ième sommet. Cette représentation peut également être utilisé pour représenter un graphe pondéré. Les poids des arêtes peuvent être représentés sous forme de listes de paires.

Avantages :

Vous ne stockez que les nœuds connectés dans une liste liée ou un vecteur. Cela se traduit par une utilisation beaucoup plus faible de la mémoire, car vous ne stockez que les nœuds existants dans le graphique. Cela fonctionne bien dans tous les types de graphes, qu'ils soient denses ou clairsemé, car l'utilisation maximale de l'espace est toujours inférieure à O(N2).

Inconvénients :
des requêtes telles que l'existence d'une arête du sommet u au sommet v ne sont pas efficaces et peuvent être effectuées avec O (V).

Conclusion

La liste d'adjacence est beaucoup plus efficace pour le stockage du graphe, en particulier les graphes clairsemés, lorsqu'il y a beaucoup moins d'arêtes que de nœuds.
En termes de temps d'accès, la matrice d'adjacence est beaucoup plus efficace pour trouver les relations dans un graphe.

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.