Qu'est-ce que l'étiquetage dans un graphe, et que dit le cours sur l'étiquetage des sommets pour les TAD Graphe ?
Un graphe étiqueté est un graphe où une information est associée à chaque sommet. Les TAD Graphe diffèrent selon l'étiquetage ou non des sommets
2
New cards
Qu'est-ce que la valuation dans un graphe, et que dit le cours sur la valuation des arcs pour les TAD Graphe ?
Un graphe valué est un graphe où une valuation est associée à chaque arc. Les TAD Graphe diffèrent selon la valuation ou non des arcs
3
New cards
Qu'est-ce que l'orientation dans un graphe, et que dit le cours sur l'orientation des arcs pour les TAD Graphe ?
Un graphe est non orienté lorsque (i, j) = (j, i), et orienté lorsque (i, j) ≠ (j, i). Les TAD Graphe diffèrent selon l'orientation ou non des arcs
4
New cards
Existe-t-il un seul TAD Graphe, et combien de TAD Graphe sont possibles en tout ?
Il n'y a pas un TAD Graphe mais des TAD Graphe, en fonction de l'étiquetage ou non des sommets, de la valuation ou non des arcs et de l'orientation ou non des arcs. Il y a donc en tout 8 TAD Graphe possibles
5
New cards
Lire les TAD graphe orienté et non orienté
diapo 9 et 10
6
New cards
Comment adapte-t-on le TAD Graphe pour un besoin de graphe non orienté simple (pas d'étiquette, pas de valuation) dont les sommets sont identifiés par des naturels non nuls, et quelles opérations est-il interdit d'utiliser ?
On adapte le TAD en écrivant Graphe<Sommet=NaturelNonNul> ou Graphe<NaturelNonNul>. Il est interdit d'utiliser les opérations obtenir/fixer Etiquettes/Valeurs
7
New cards
Comment adapte-t-on le TAD Graphe pour un besoin de graphe non orienté dont les sommets sont identifiés par des naturels non nuls et dont les arcs ont des valeurs de type réel, et quelles opérations est-il interdit d'utiliser ?
On adapte le TAD en écrivant Graphe<Sommet=NaturelNonNul,Valeur=Reel> ou Graphe<NaturelNonNul,Reel>. Il est interdit d'utiliser les opérations obtenir/fixer Etiquettes