5.3 - Conception detaillée

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/15

encourage image

There's no tags or description

Looks like no tags are added yet.

16 Terms

1
New cards

Comment représente-t-on un graphe G à n sommets notés 1, 2, …, n par une matrice d'adjacence A[n, n] de booléens, comment définit-on A[i, j] selon que (i, j) est un arc de G ou non, et que peut-on dire de la matrice si le graphe est non orienté ?

knowt flashcard image


<img src="https://assets.knowt.com/user-attachments/cc8823f6-3871-4198-8298-f0278d7723bb.png" data-width="100%" style="display: block; width: 100%; margin-left: auto; margin-right: auto;" data-align="center" alt="knowt flashcard image"><p></p>
2
New cards

Comment représente-t-on un graphe G à n sommets et p arcs par une matrice d'incidence A[n, p] d'entiers, quelles valeurs prennent A[i, k] et A[j, k] pour un arc vk = (i, j) avec i ≠ j selon que le graphe est orienté ou non, quelle valeur prend A[i, k] pour une boucle vk = (i, i), et quelle valeur prend-on sinon ?


knowt flashcard image


<img src="https://assets.knowt.com/user-attachments/f4096a9a-4bcc-44bc-87e2-eb08fffd110b.png" data-width="100%" style="display: block; width: 100%; margin-left: auto; margin-right: auto;" data-align="center" alt="knowt flashcard image"><p></p>
3
New cards
Comment représente-t-on un graphe G par une liste d'adjacence, et que contient chaque élément sᵢ de la liste ls ?
G est représenté par une liste de sommets ls = < s₁, …, sₙ >. Chaque élément sᵢ de la liste ls est une liste qui contient les sommets successeurs du sommet i dans le graphe G
4
New cards
Comment représente-t-on les étiquettes d'un graphe ?
Les étiquettes sont représentées à l'aide d'un dictionnaire dont les clés sont les sommets
5
New cards
Comment représente-t-on les valeurs d'un graphe ?
Les valeurs sont représentées à l'aide d'un dictionnaire dont les clés sont des couples de sommets
6
New cards
En quoi consiste le parcours de tous les sommets d'un graphe ?
Il consiste à visiter chaque sommet du graphe une seule fois et à appliquer un même traitement en chaque sommet
7
New cards
Quels sont les deux types de parcours à partir d'un sommet s ?
Le parcours en profondeur et le parcours en largeur
8
New cards
Quel est le principe du parcours en profondeur à partir d'un sommet s ?
Le principe consiste à descendre le plus « profond » dans le graphe à partir de s, en suivant un certain ordre, avant de revenir pour prendre une autre direction
9
New cards
Quel est le principe du parcours en largeur à partir d'un sommet s ?
Le principe consiste à visiter les sommets situés à une distance 1 de s, puis ceux situés à une distance 2 de s, etc.
10
New cards
Combien de fois chaque sommet est-il visité lors d'un parcours de tous les sommets d'un graphe ?
Chaque sommet du graphe est visité une seule fois
11
New cards
Quel traitement applique-t-on en chaque sommet lors d'un parcours de tous les sommets d'un graphe ?
On applique un même traitement en chaque sommet
12
New cards
De quoi le type de parcours d'un graphe est-il fonction ?
Le type de parcours est fonction du TAD utilisé pour stocker les sommets à traiter
13
New cards
Quel TAD utilise-t-on pour un parcours en profondeur ?
Une pile (Pile ⇒ Parcours en profondeur)
14
New cards
Quel TAD utilise-t-on pour un parcours en largeur ?
Une file (File ⇒ Parcours en largeur)
15
New cards
Quelle opération faut-il souvent ajouter aux TAD utilisés pour stocker les sommets à traiter ?
Il y a souvent besoin d'ajouter l'opération estPresent
16
New cards
Quels mécanismes permettent d'éviter de boucler indéfiniment lors d'un parcours de graphe ?
Dans tous les cas, il faut un mécanisme pour éviter de boucler indéfiniment : marquer les nœuds ou lister les nœuds traités