Types de graphiques dans la structure de données avec exemples

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 fonctionnent comme un lien entre une paire de sommets.

Les graphiques peuvent être de plusieurs types, en fonction de la position des nœuds et des arêtes. Voici quelques types de graphiques importants :

Graphique dirigé

Les bords du graphique dirigé contiennent des flèches qui indiquent la direction. La flèche détermine où le bord pointe ou se termine.

Voici un exemple de graphique dirigé.

• Nous pouvons passer du nœud A au nœud D.
• Cependant, nous ne pouvons pas passer du nœud D au nœud A car le bord 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é

Le graphique non orienté contient des arêtes sans pointeurs. Cela signifie que nous pouvons voyager vice versa entre deux sommets.

Voici un exemple simple du graphique non orienté.

Dans le graphique ci-dessus,

• On peut passer de A à B
• On peut aussi passer du B au A
• Les bords ne contiennent aucune direction.

C'est un exemple de graphe non orienté ayant un nombre fini de sommets et d'arêtes sans poids.

Graphique pondéré

Un graphique contenant des poids ou des coûts sur les bords est appelé graphique pondéré. La valeur numérique représente généralement le coût de déplacement d'un sommet à un autre sommet. Les graphiques orientés et non orientés peuvent avoir des poids sur leurs bords.

Voici un exemple de graphique pondéré (dirigé).

• De A à B, il y a un avantage, et le poids est de 5, ce qui signifie que passer de A à B nous coûtera 5.
• A pointe vers B, mais dans ce graphique, B n'a pas d'avantage direct sur A. Nous ne pouvons donc pas voyager de B à A.
• Cependant, si l’on veut passer de A à F, il existe plusieurs chemins. Les chemins sont ADF, ABF. L'ADF coûtera (10+11) ou 21.
• Ici, le chemin ABF coûtera (5+15) ou 20. Ici, nous ajoutons le poids de chaque arête du chemin.

Voici un exemple de graphique non orienté avec des pondérations :

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. C'est

• Généralement, le graphe non orienté peut avoir une 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 :

Voyager de A à D nous coûtera 17, mais voyager de D à A nous coûtera 12. Nous ne pouvons donc pas attribuer deux poids différents s'il s'agit d'un graphique non orienté.

Graphique infini

Le graphique contiendra un nombre infini d’arêtes et de nœuds. Si un graphe est infini et qu’il s’agit également d’un graphe connecté, alors il contiendra également un nombre infini d’arêtes. Ici, les bords étendus signifient que davantage de bords peuvent être connectés à ces nœuds via des bords.

Voici un exemple du graphe infini :

Graphique nul

Null Graph contient uniquement des nœuds ou des sommets mais sans arêtes. Si on donne un graphique G = (V, E), où V est les sommets et E les arêtes, il sera nul si le nombre d'arêtes E est nul.

Voici un exemple de graphique nul :

Graphique trivial

Une structure de données graphique est considérée comme triviale si un seul sommet ou nœud est présent sans arêtes.

Voici un exemple de graphique trivial :

Graphique multiple

Un graphe est appelé multigraphe lorsque plusieurs arêtes sont présentes entre deux sommets ou que le sommet a une boucle. Le terme « Boucle » dans Graph Data Structure désigne une arête pointant vers le même nœud ou sommet. Le multigraphe peut être dirigé ou non.

Voici un exemple de Multi Graph :

Il y a deux arêtes de B à A. De plus, le sommet E a une auto-boucle. Le graphique ci-dessus est un graphique orienté sans poids sur les arêtes.

Graphique complet

Un graphe est complet si chaque sommet a des arêtes dirigées ou non avec tous les autres sommets.

Supposons qu'il y ait un nombre total de sommets V et que chaque sommet ait exactement des arêtes V-1. Ensuite, ce graphique sera appelé graphique complet. Dans ce type de graphique, chaque sommet est connecté à tous les autres sommets via des arêtes.

Voici un exemple de graphique complet avec cinq sommets :

Vous pouvez 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 appelé graphe connecté si nous partons d'un nœud ou d'un sommet et parcourons tous les nœuds à partir du nœud de départ. Pour cela, il doit y avoir au moins une arête entre chaque paire de nœuds ou sommets.

Voici un exemple de graphique connecté :

Voici une explication du graphique « exemple de graphique complet » ci-dessus :

• En supposant qu'il n'y a pas d'arête entre C et F, nous ne pouvons pas voyager de A à G. Cependant, l'arête C à F nous permet de voyager vers 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 y a un ou plusieurs cycles présents dans le graphe.

Voici un exemple de graphique cyclique :

Ici, les sommets A, B et C forment un cycle.

Un graphique peut contenir plusieurs cycles.

Graphe acyclique dirigé (DAG)

Un graphique est appelé graphique acyclique dirigé ou DAG s'il n'y a pas de cycles à l'intérieur d'un graphique. DAG est important lors de l'exécution du Tri topologique ou trouver l'ordre d'exécution. DAG est également important pour créer des systèmes de planification ou analyser la dépendance des ressources, etc. Cependant, le graphique ci-dessus ne contient aucun cycle à l'intérieur.

Voici un exemple simple de graphe acyclique dirigé (DAG) :

Graphique cyclique

Le graphique du cycle n’est pas le même que le graphique cyclique. Dans Cycle Graph, chaque nœud aura exactement deux arêtes connectées, ce qui signifie que chaque nœud aura exactement deux degrés.

Voici un exemple de graphique de cycle :

Graphique bipartite

Ces sortes de Graphiques sont des types spéciaux de graphiques où les sommets sont attribués à deux ensembles.

Le graphe bipartite doit suivre la règle :

• 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 du même ensemble ne doivent former aucune arête.

Graphique d'Euler

Les structures de données graphiques sont considérées comme un graphique d'Euler si tous les sommets ont un degré pair. Le terme degré de sommets désigne le nombre d’arêtes pointant vers ou pointant depuis un sommet particulier.

Voici un exemple de graphique d'Euler :

Tous les sommets ont des degrés pairs. Les sommets A, D, E et H ont deux degrés. Ici, le nœud C a quatre degrés, ce qui est pair.

Graphique de Hamilton

Hamilton Graph est un Connect Graph, où vous pouvez visiter tous les sommets d'un sommet donné sans revisiter le même nœud ni utiliser la même arête. Ce type de graphique connecté est connu sous le nom de « graphique de Hamilton ». Le chemin que vous visitez pour vérifier si le graphique donné est le graphique de Hamilton ou non est connu sous le nom de chemin hamiltonien.

Voici un exemple graphique simple d'un Hamilton :

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 ADCHBE. Il est également possible de trouver un Hamilton Cycle. Hamilton Cycle commence et se termine au même sommet. Ainsi, le cycle de Hamilton sera ADCHBÉA.