Tutoriel de structure de données graphiques
Un nœud dans un graphique est appelé sommet (pluriel - sommets). Il est parfois encore appelé nœud; il peut également être appelé un point. Un lien dans un graphique est appelé bord. Il est parfois encore appelé un lien; il peut également être appelé une ligne.
Graphique avec de nombreuses fonctionnalités
Cette figure montre un graphique avec de nombreuses fonctionnalités:
Les cercles (disques) sont des sommets. Toute ligne droite ou ligne ou boucle incurvée est un bord.
Caractéristiques du graphique
Sommet
Un sommet est un objet. Ce peut être une maison; Ce peut être une personne; Il peut s'agir d'un nom abstrait; ce peut être n'importe quel objet à laquelle vous pouvez penser.
Bord
Un bord est une connexion (relation) entre deux sommets; La connexion peut être abstraite.
Boucle
Une boucle est un bord qui relie un sommet à lui-même.
Flèche
Considérez deux personnes: John et Peter. Si John prête à Peter 100 $, et si John et Peter sont des sommets, alors le bord de prêt pointera vers Peter. Si les deux partenaires oublient que Peter dû John et que Peter prête à John 100 $, alors à l'autre bout du même bord, une pointe de flèche pointera vers John. Si Peter a prêté mais 75 $ à John et pas à 100 $, alors un autre avantage relierait Peter à John. Ce deuxième bord aura sa pointe de flèche pointant vers John. Dans le deuxième cas, il y a deux arêtes, avec une pointe de flèche chacune, pointant dans des directions opposées.
Le sommet auquel un bord pointe, est un sommet de tête pour ce bord. Le sommet à partir duquel un bord quitte est un sommet de queue.
Incident
Un bord relie deux sommets. Le bord serait incident sur l'un ou l'autre sommet. Le bord n'a pas besoin d'avoir une pointe de flèche. Les deux sommets sont connus comme les points de terminaison du bord. Il est possible d'avoir un graphique où un sommet n'appartient à aucun avantage, mais qui ne sera pas pris en compte dans ce tutoriel.
Graphique non dirigée
Un bord peut être une flèche, ou il ne peut pas. Un graphique où aucun bord n'est une flèche est un graphique non dirigé. Un bord peut être représenté par une ligne droite ou une courbe ou une boucle.
Graphique dirigé
Un graphique où chaque bord est une flèche (direction) est un graphique dirigé. Un bord de flèche peut être représenté par une ligne droite avec une pointe de flèche ou une courbe avec une pointe de flèche ou une boucle avec une pointe de flèche.
L'absence de direction sur le bord d'un graphique non dirigé, signifie chaque bord du graphique non dirigé, est bidirectionnel.
Degré de sommet
Le nombre de bords incidents sur un sommet est le degré du sommet. Une boucle a deux incidences sur un sommet, donc une boucle est comptée deux fois.
Ordre d'un graphique
L'ordre d'un graphique est le nombre de sommets dans le graphique.
Multigraphe
Un multigraphe est un graphique, où pour certaines paires de sommets, il y a plus d'un bord. Un multigraphe non dirigée est un tel graphique dans lequel les bords n'ont aucune direction (ne sont pas des flèches). Un multigraphe dirigé est celui où chaque bord est une flèche, et pour des paires de sommets qui ont plus d'une flèche, un sommet est la queue de ces flèches, et l'autre sommet est la tête des mêmes flèches. Le diagramme suivant montre un multigraphe non dirigée:
Plus d'un bord (je.e. plusieurs arêtes) pour une paire de sommets sont également appelées bords parallèles.
Trembler
Un carquois est un multigraphe qui permet des boucles (une ou plusieurs boucles). Certaines multigraphes n'autorisent pas les boucles.
Graphique simple
Un graphique simple est un graphique où deux paires de sommets ont plusieurs bords. Les boucles ne sont pas autorisées dans un graphique simple.
Graphique vide
Un graphique vide est un graphique sans sommet et donc pas de bords.
Graphique mixte
Un graphique mixte est un graphique où certains bords sont des flèches, et d'autres ne le sont pas; En d'autres termes: certains bords ont des instructions, et d'autres ne sont pas dirigés.
Graphique pondéré
Il est possible d'avoir un graphique dans lequel un nombre, connu sous le nom de poids, est affecté à chaque bord. Certains arêtes ont le même nombre, mais les nombres sont généralement différents. Un tel graphique est appelé un graphique pondéré. Les chiffres pour un graphique particulier peuvent représenter des longueurs ou des coûts (prix) ou une ampleur d'une sorte, selon le problème.
Indésirable et extérieur
Le vocabulaire, l'indépendance et l'outre sont applicables à un graphique dirigé uniquement. Le graphique peut être ou non un multigraphe. Le graphique peut ou non avoir des boucles.
Le nombre de pointes de flèches connectées à un sommet est l'indépendance de ce sommet. Une flèche avec une seule pointe de flèche a une extrémité et une fin de queue. Le nombre de queues connectées à un sommet est l'extérieur de ce sommet.
Remarque: un graphique avec plusieurs bords pour la paire de sommets, où les arêtes multiples sont dans des directions opposées, n'est pas abordée dans ce tutoriel.
Représentation logicielle d'un graphique
Un graphique peut être représenté dans le logiciel de la façon dont il est dessiné sur le diagramme. Un graphique peut également être représenté dans des logiciels par une matrice mathématique (tableau bidimensionnel). L'une de ces matrices est appelée matrice d'adjacence.
Matrice d'adjacence
Une matrice d'adjacence est une matrice carrée. Les titres des lignes sont tous les sommets, écrits par ordre croissant. Les titres des colonnes sont toujours les mêmes sommets, écrits par ordre croissant. Le comptage des lignes ou des colonnes d'une matrice commence à partir de 1 et non à zéro comme avec les tableaux. Lors de l'identification d'un élément dans une matrice, le numéro de ligne est écrit avant le numéro de colonne.
Pour un graphique non dirigé, chaque entrée (élément) dans la matrice d'adjacence est le nombre de bords reliant les deux sommets correspondants. Une boucle doit être comptée deux fois. Pour un graphique dirigé, chaque entrée dans la matrice d'adjacence est soit le nombre de bords, laissant un sommet de ligne et entrant le sommet de colonne correspondant ou est le nombre de bords quittant un sommet de colonne et entrant le sommet de ligne correspondant. Le choix est celui du programmeur. Dans cette situation (les deux cas), une boucle doit toujours être comptée une fois.
Remarque: un graphique est un diagramme est une structure de données à part entière. Une matrice d'adjacence est également une structure de données à part entière.
Graphique non dirigée et matrice d'adjacence
Les diagrammes suivants montrent un graphique non dirigé et la matrice d'adjacence correspondante:
La diagonale principale d'une matrice est la diagonale du haut-gauche au bas à droite. Une matrice non dirigée est symétrique sur la diagonale principale. L'entrée matricielle pour la ligne A et la colonne C est 1, ce qui signifie qu'il y a un bord reliant le sommet A et le sommet C. L'entrée matricielle pour la ligne C et la colonne B est de 3, ce qui signifie qu'il y a 3 bords reliant le sommet C et le sommet B. Les autres entrées sont expliquées de la même manière.
La somme des entrées pour une ligne donne le nombre de bords (degré) pour le sommet correspondant. La somme des entrées de la ligne A est 2, ce qui signifie que 2 bords sont connectés au sommet A. La somme des entrées de la ligne B est de 6, ce qui signifie que 6 bords sont connectés au sommet B. Le reste des entrées est expliqué de la même manière.
Graphique réalisé et matrice d'adjacence
Les diagrammes suivants montrent un graphique dirigé et la matrice d'adjacence correspondante:
La matrice d'adjacence pour un graphique dirigé n'est pas nécessairement symétrique sur la diagonale principale. L'entrée matricielle pour la ligne A et la colonne C est 1, ce qui signifie qu'un bord laisse du sommet A au sommet C. L'entrée matricielle pour la ligne C et la colonne B est de 3, ce qui signifie que 3 bords laissent du sommet C au sommet B. Les autres entrées sont expliquées de la même manière.
La somme des entrées pour une colonne donne à l'indépendance du sommet (colonne). La somme des entrées pour une ligne donne le hors-danger pour le sommet (ligne). La somme des entrées de la colonne A est 1, ce qui signifie qu'un bord est dirigé vers le sommet A. La somme des entrées de la ligne B est 2, ce qui signifie que 2 bords laissent du sommet B. Le reste des entrées est expliqué de la même manière.
Opérations de graphiques
Une structure de données, comme un graphique, se compose d'un ensemble de valeurs de données ou d'un ensemble d'objets, plus la relation entre les objets, plus les opérations (fonctions) entre les objets. Les relations dans un graphique sont indiquées par les bords. En ce qui concerne cela, un graphique devrait avoir au moins les opérations suivantes:
adjacent (g, x, y)
G signifie graphique. Cette opération vérifie si un bord relie le sommet x et le sommet Y. La valeur et la position d'une entrée dans une matrice indiquent la connexion d'un bord (et de son type).
voisins (g, x)
Cette opération renvoie une liste de tous les sommets qui sont directement connectés au sommet x. La valeur et la position d'une entrée dans une matrice indiquent la connexion d'un bord.
retire_vertex (g, x)
Cette opération supprime un sommet, x d'un graphique. Si le sommet n'avait pas de bord, il n'y a pas de problème. Cependant, si le sommet avait des liens, les liens (bords) doivent également être supprimés. La valeur et la position d'une entrée dans une matrice indiquent la présence d'un sommet particulier. Si un sommet est supprimé, la matrice doit être réajustée.
add_vertex (g, x)
Cela ajoute un sommet, x sans ajouter d'arêtes, ou remplace un sommet qui avait des bords mais avait été supprimé. La valeur et la position d'une entrée dans une matrice indiquent la présence d'un sommet particulier. Si un sommet est ajouté, la matrice doit être réajustée.
add_edge (g, x, y)
Cette opération ajoute un nouveau bord entre le sommet x et le sommet y si le bord n'était pas là. La valeur et la position d'une entrée dans une matrice indiquent la présence d'un bord particulier. Si un bord est ajouté, la matrice doit être réajustée.
retire_edge (g, x, y)
Cette opération supprimerait le bord entre le sommet x et le sommet y si le bord était là. La valeur et la position d'une entrée dans une matrice indiquent la présence d'un bord particulier. Si un bord est supprimé, la matrice doit être réajustée.
get_vertex_value (g, x)
Cette opération renvoie la valeur, v associée au sommet, x. Pour y parvenir, vous avez besoin d'un ensemble de sous-ensembles de sous-ensembles pour les étiquettes de sommet et leurs valeurs.
set_vertex_value (g, x, v)
Cette opération donne une nouvelle valeur, V pour la valeur associée au sommet, x. Pour y parvenir, vous avez besoin d'un ensemble de sous-ensembles de sous-ensembles pour les étiquettes de sommet et leurs valeurs.
Certains graphiques associent également les valeurs à leurs bords. Ces graphiques ont besoin des opérations supplémentaires suivantes:
get_edge_value (g, x, y)
Cette opération renvoie la valeur, v associée au bord, (x, y). Pour y parvenir, vous avez besoin d'un ensemble de sous-ensembles de sous-ensembles pour les bords et leurs valeurs.
set_edge_value (g, x, y, v)
Cette opération donne une nouvelle valeur, V pour la valeur associée au bord, (x, y). Pour y parvenir, vous avez besoin d'un ensemble de sous-ensembles de sous-ensembles pour les bords et leurs valeurs.
Conclusion
Un graphique est un ensemble de sommets liés aux bords. Un graphique peut être non dirigé ou dirigé. Les bords peuvent être non directionnels ou directionnels. Des boucles peuvent être présentes ou absentes dans un graphique. Ce que vous devez apprendre ensuite, c'est défini, ensemble d'électricité et multiset lié aux graphiques. Après cela, vous devez apprendre les différents types de graphiques, tels qu'un graphique orienté, un graphique régulier, un graphique complet, un graphique bipartite, un graphique du tournoi, un graphique de réseau Flow, etc.
Chrys