Exercices graphes

Exercices

Exercice 1 *

Dessiner tous les graphes non orientés ayant exactement trois sommets.

Exercice 2 *

1. Compter le degré de chaque nœud.
2. Calculer la somme des degrés.
3. Construire la matrice d’adjacence (sur papier puis sur machine) du graphe.
4. Construire le dictionnaire d’adjacence du graphe.

Exercice 3 **

1. Le graphe est-il complet?
2. Construire la matrice d’adjacence du graphe.
3. Écrire la fonction ordre(mat: list) -> int qui renvoie l’ordre du graphe.
4. En utilisant la matrice d’adjacence, quelle stratégie mettre en place pour vérifier si un graphe est complet?
5. Écrire alors la fonction est_complet(mat:list) -> bool qui renvoie True si le graphe est complet.

Exercice 4 ***

1. Compter les degrés entrants et sortants de chaque nœud.
2. Calculer la somme des degrés.
3. Construire la matrice des successeurs du graphe.
4. Dans le cas d’un graphe dont les sommets sont numérotés de 0 à n, on peut construire une liste d’adjacences où les indices de la liste correspondent aux numéros des sommets. Construire la liste suivants des successeurs du graphe.
5. Écrire la fonction degres_sortants(liste: list, s: int) -> int qui renvoie la valeur du degré sortant de s.
6. Écrire la fonction degres_entrants(liste: list, s: int) -> int qui renvoie la valeur du degré entrant de s