Types de graphiques dans la structure de données avec exemples
Sarah Chen
⚡ Résumé intelligent
En structure de données, les graphes sont des ensembles non linéaires de sommets et d'arêtes classés en familles telles que les graphes orientés, non orientés, pondérés, cycliques, acycliques, complets, connexes, bipartites, eulériens et hamiltoniens, en fonction de leur structure.
Un graphe est une structure de données non linéaire composée de sommets et d'arêtes. Les sommets contiennent les informations ou les données, et les arêtes servent de lien entre deux sommets.
Il existe plusieurs types de graphes, selon la position des nœuds et des arêtes. Voici quelques types importants de graphes :
Graphique dirigé
Les arêtes d'un graphe orienté contiennent des flèches indiquant leur direction. La flèche détermine la destination ou le point d'arrivée de l'arête. Voici un exemple de graphe orienté.
Graphique dirigé
- Nous pouvons passer du nœud A au nœud D.
- Cependant, nous ne pouvons pas aller du nœud D au nœud A, car l'arête pointe de A vers D.
- Comme le graphique n'a pas de poids, voyager du sommet A à D coûtera le même prix que voyager de D à F.
Graphe non orienté
Un graphe non orienté contient des arêtes sans pointeur. Cela signifie qu'on peut se déplacer dans les deux sens entre deux sommets. Voici un exemple simple de graphe non orienté.
Graphe non orienté
Dans le graphique ci-dessus,
- Nous pouvons passer de A à B.
- Nous pouvons également passer de B à A.
- Les bords ne contiennent aucune direction.
Il s'agit d'un exemple de graphe non orienté possédant un nombre fini de sommets et d'arêtes sans poids.
Graphique pondéré
Un graphe dont les arêtes sont pondérées est appelé graphe pondéré. La valeur numérique représente généralement le coût du déplacement d'un sommet à un autre. Les graphes orientés et non orientés peuvent avoir des arêtes pondérées. Voici un exemple de graphe pondéré (orienté).
Graphique dirigé avec poids
- De A à B, il y a un bord, et le poids est de 5, ce qui signifie que le déplacement de A à B nous coûtera 5.
- A pointe vers B, mais dans ce graphe, B n'a pas d'arête directe vers A. On ne peut donc pas se déplacer de B à A.
- Cependant, pour aller de A à F, plusieurs chemins sont possibles : ADF et ABF. Le chemin ADF coûte (10 + 11), soit 21.
- Ici, le chemin ABF coûtera (5+15) ou 20. Ici, nous additionnons le poids de chaque arête du chemin.
Voici un exemple de graphe non orienté avec des poids :
Graphique non orienté avec poids
Ici, le bord a du poids mais aucune direction. Cela signifie donc que voyager du sommet A à D coûtera 10 et vice versa.
Graphique bidirectionnel
Les graphes bidirectionnels et non orientés ont une propriété commune. À savoir :
- En général, un graphe non orienté peut avoir une seule arête entre deux sommets.
Par exemple :
- Ici, passer de A à D ou de D à A coûtera 10.
- Dans un graphe bidirectionnel, nous pouvons avoir deux arêtes entre deux sommets.
Voici un exemple:
Graphique bidirectionnel
Le trajet de A à D nous coûtera 17, mais le trajet de D à A nous coûtera 12. Par conséquent, nous ne pouvons pas attribuer deux poids différents s'il s'agit d'un graphe non orienté.
Graphique infini
Le graphe contient un nombre infini d'arêtes et de nœuds. Si un graphe est infini et connexe, il contient également un nombre infini d'arêtes. Ici, les arêtes étendues signifient que d'autres arêtes peuvent être connectées à ces nœuds. Voici un exemple de graphe infini :
Graphique infini
Graphique nul
Un graphe nul ne contient que des nœuds (ou sommets), sans aucune arête. Si l'on considère un graphe G = (V, E), où V représente les sommets et E les arêtes, il sera nul si le nombre d'arêtes E est égal à zéro. Voici un exemple de graphe nul :
Graphique nul
Graphique trivial
Une structure de données de type graphe est considérée comme triviale si elle ne comporte qu'un seul sommet (ou nœud) et aucune arête. Voici un exemple de graphe trivial :
Graphique multiple
Un graphe est appelé multigraphe lorsqu'il existe plusieurs arêtes entre deux sommets, ou lorsqu'un sommet forme une boucle. Dans le contexte des structures de données graphiques, une boucle désigne une arête pointant vers un même nœud ou sommet. Un multigraphe peut être orienté ou non orienté. Voici un exemple de multigraphe :
Il existe deux arêtes de B vers A. De plus, le sommet E forme une boucle. Le graphe ci-dessus est un graphe orienté sans poids sur les arêtes.
Graphique complet
Un graphe est complet si chaque sommet est relié à tous les autres sommets par des arêtes orientées ou non. Supposons qu'il y ait V sommets et que chaque sommet possède exactement V-1 arêtes. Ce graphe est alors appelé un graphe complet. Dans ce type de graphe, chaque sommet est relié à tous les autres sommets par des arêtes. Voici un exemple de graphe complet à cinq sommets :
On peut voir sur l'image que le nombre total de nœuds est de cinq, et que tous les nœuds ont exactement quatre arêtes.
Graphique connecté
Un graphe est dit connexe si, en partant d'un nœud (ou sommet), on peut atteindre tous les autres nœuds. Pour cela, il doit exister au moins une arête entre chaque paire de nœuds (ou sommets). Voici un exemple de graphe connexe :
Voici quelques explications concernant le graphe connexe ci-dessus :
- S'il n'existe aucune arête entre C et F, on ne peut pas aller de A à G. Cependant, l'arête reliant C à F permet d'atteindre n'importe quel nœud à partir d'un nœud donné.
- Un graphique complet est un graphique connecté car nous pouvons passer d'un nœud à n'importe quel autre nœud dans le graphique donné.
Graphique cyclique
Un graphe est dit cyclique s'il contient un ou plusieurs cycles. Voici un exemple de graphe cyclique :
Ici, les sommets A, B et C forment un cycle. Un graphe peut contenir plusieurs cycles.
Graphe acyclique dirigé (DAG)
Un graphe est appelé graphe orienté acyclique (DAG) s'il ne contient aucun cycle. La notion de DAG est importante lors de la réalisation de… Tri topologique ou pour déterminer l'ordre d'exécution. Les graphes acycliques orientés (DAG) sont également importants pour la création de systèmes d'ordonnancement ou l'analyse des dépendances des ressources, etc. Cependant, le graphe ci-dessus ne contient aucun cycle. Voici un exemple simple de graphe acyclique orienté (DAG) :
Graphique cyclique
Un graphe cyclique est différent d'un graphe circulaire. Dans un graphe cyclique, chaque nœud possède exactement deux arêtes, donc exactement deux degrés. Voici un exemple de graphe cyclique :
Graphique bipartite
Ces sortes de Graphiques Les graphes bipartis sont des types particuliers de graphes où les sommets sont associés à deux ensembles. Un graphe biparti doit respecter la règle suivante :
- Les deux ensembles de sommets doivent être distincts, ce qui signifie que tous les sommets doivent être divisés en deux groupes ou ensembles.
- Les sommets appartenant au même ensemble ne doivent pas former d'arêtes.
Graphique d'Euler
Une structure de données de type graphe est considérée comme un graphe eulérien si tous ses sommets ont un degré pair. Le degré d'un sommet correspond au nombre d'arêtes qui y convergent ou en émergent. Voici un exemple de graphe eulérien :
Tous les sommets ont un degré pair. Les sommets A, D, E et H ont un degré de deux. Le nœud C a un degré de quatre, qui est pair.
Graphique de Hamilton
Un graphe hamiltonien est un graphe connexe, c'est-à-dire un graphe où l'on peut atteindre tous les sommets à partir d'un sommet donné sans repasser par le même nœud ni emprunter la même arête. Ce type de graphe connexe est appelé « graphe hamiltonien ». Le chemin permettant de vérifier si un graphe donné est un graphe hamiltonien est appelé chemin hamiltonien. Voici un exemple simple de graphe hamiltonien :
Dans cette image, nous pouvons visiter tous les sommets de n'importe quel nœud du graphique ci-dessus. L'un des chemins peut être ADCHBEIl est également possible de trouver un cycle hamiltonien. Un cycle hamiltonien commence et se termine au même sommet. Donc, le cycle hamiltonien sera : ADCHBEA.
