Sommets, arêtes, degrés
Le vocabulaire de base des graphes, orientés ou non : sommet, arête, arc, boucle, graphe simple, ordre, taille, degré, lemme des poignées de main et suites de degrés.
- 26 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Graphe : de quoi s'agit-il ?
Voir la réponse
Ensemble de sommets et d'arêtes, chaque arête reliant deux sommets (ou un sommet à lui-même).
Il modélise tout ce qui relie des objets : villes et routes, comptes et abonnements, tâches et dépendances.
Qu'affiche ce programme, qui compte le degré de chaque sommet ?
```python
aretes = [("A","B"),("A","C"),("B","C"),("C","D"),("D","D")]
deg = {}
for u, v in aretes:
deg[u] = deg.get(u, 0) + 1
deg[v] = deg.get(v, 0) + 1
print(deg)`{'A': 2, 'B': 2, 'C': 3, 'D': 3}{'A': 2, 'B': 2, 'C': 3, 'D': 2}{'A': 2, 'B': 2, 'C': 3, 'D': 1}{'A': 2, 'B': 2, 'C': 2, 'D': 2}
Voir la réponse
{'A': 2, 'B': 2, 'C': 3, 'D': 3}La boucle D-D ne passe qu'une fois dans la boucle
for, maisuetvy valent tous deux D : D gagne 2, plus 1 pour l'arête C-D. Le degré de D est 3.Dans un graphe non orienté à m arêtes, la somme des degrés des sommets vaut ….
Voir la réponse
Dans un graphe non orienté à m arêtes, la somme des degrés des sommets vaut 2m.
Chaque arête est comptée une fois à chacune de ses deux extrémités.
Ordre et taille d'un graphe : de quoi s'agit-il ?
Voir la réponse
L'ordre est le nombre de sommets, noté n ; la taille est le nombre d'arêtes (ou d'arcs), notée m.
Les coûts des algorithmes s'écrivent avec ces deux nombres, par exemple O(n + m) pour un parcours.