Exercices corrigés — Théorie des graphes (mathématiques appliquées (ECG 1re année))

35 exercices avec corrigé rédigé, du plus simple au plus exigeant.

Degrés et formule d'Euler

• Une liste de degrés impossible
• La matrice de $K_4$
• Deux sommets ont toujours le même degré
• Un graphe régulier, et un compte impossible Exercice d'entraînement
• Combien d'arêtes au maximum ? Exercice d'entraînement
• Dans un tournoi, quelqu'un gagne beaucoup Exercice d'entraînement

Matrice d'adjacence

• Ce que dit un coefficient diagonal
• Le graphe complémentaire
• Tout lire sur la matrice Exercice d'entraînement
• Renuméroter les sommets Exercice d'entraînement
• La matrice d'un graphe orienté Exercice supplémentaire
• Lire une matrice non symétrique Exercice supplémentaire
• Le carré de la matrice d'une chaîne Exercice supplémentaire

Puissances et comptage des chemins

• Compter les chaînes par les puissances
• Symétrie des puissances
• Graphe biparti et chaînes impaires
• Les triangles se lisent sur $A^3$

Connexité

• Assez d'arêtes force la connexité
• Deux morceaux, des zéros qui persistent
• Un graphe connexe a au moins $n-1$ arêtes
• Deux morceaux qu'aucune puissance ne relie Exercice d'entraînement
• Un graphe ou son complémentaire est connexe Exercice d'entraînement

Analyse de réseaux, en Python

• La distance par les puissances
• Compter les morceaux d'un graphe
• Degré et intermédiarité, sur le graphe du cours

Chemins et puissances de la matrice

• Les voisins communs se lisent sur $A^2$ Exercice d'entraînement
• Compter toutes les chaînes de longueur $d$ Exercice d'entraînement
• Le cycle à quatre sommets Exercice d'entraînement

Graphes en Python

• Degrés et formule d'Euler, en Python Exercice d'entraînement
• Une marche au hasard sur un graphe Exercice d'entraînement

Vocabulaire et degrés

• Des arêtes aux degrés Exercice supplémentaire
• Le graphe complet à six sommets Exercice supplémentaire
• Retrouver le nombre d'arêtes Exercice supplémentaire

Chemins et connexité

• Connexe ou non ? Exercice supplémentaire
• Compter des chaînes de longueur deux Exercice supplémentaire

Lire le cours de ce chapitre