1.Dans un graphe non orienté, la somme des degrés de tous les sommets vaut le nombre d’arêtes.
2.Un graphe orienté est fortement connexe si, pour tout couple (u,v), il existe un chemin de u vers v et un chemin de v vers u.
3.Le nombre de sommets de degré impair dans un graphe est toujours pair.
4.Un arbre à n sommets possède toujours n arêtes.
5.La représentation par matrice d’adjacence est toujours plus économe en mémoire que les listes d’adjacence.
On considère le graphe G=(S,A) avec S={1,2,3,4,5} et A={{1,2},{1,3},{2,3},{3,4},{4,5}}.
Calculer deg(u) pour chaque sommet u∈S.
deg(1)=2 ({1,2},{1,3}),deg(2)=2 ({1,2},{2,3}),deg(3)=3 ({1,3},{2,3},{3,4}) deg(4)=2 ({3,4},{4,5}),deg(5)=1 ({4,5})
Vérifier la formule des degrés sur cet exemple.
u∈S∑deg(u)=2+2+3+2+1=10 Et ∣A∣=5, donc 2∣A∣=10. On a bien ∑u∈Sdeg(u)=2∣A∣, conformément au théorème du cours.
Pour chacune des suites de degrés suivantes, dire si elle peut être la suite des degrés d’un graphe, en utilisant uniquement le corollaire de parité du cours (on ne demande pas de construire un graphe correspondant).
(4,3,2,2,1)
La somme vaut 4+3+2+2+1=12, paire — condition nécessaire pour que ce soit une suite de degrés (formule des degrés). Les degrés impairs sont 3 et 1 : il y en a 2, un nombre pair. Le corollaire de parité n’est donc pas violé : cette suite peut correspondre à un graphe.
(4,4,3,3,2)
Somme =4+4+3+3+2=16, paire. Degrés impairs : 3 et 3, soit 2 (pair). Le corollaire n’est pas violé non plus.
(5,4,3,2,1)
Somme =5+4+3+2+1=15, impaire. Degrés impairs : 5,3,1, soit 3 (impair). Le corollaire est violé : cette suite ne peut pas être la suite des degrés d’un graphe.
Montrer que la condition « la somme des degrés est paire » et la condition « le nombre de degrés impairs est pair » sont en réalité une seule et même condition.
Modulo 2, un degré pair contribue 0 à la somme et un degré impair contribue 1. La somme des degrés, modulo 2, est donc exactement égale au nombre de degrés impairs, modulo 2. Les deux conditions — somme paire, nombre de degrés impairs pair — sont donc rigoureusement équivalentes : c’est la même vérification, formulée de deux façons différentes.
6 blocs de plus : les autres énoncés et tous les corrigés, rédigés en entier. Le reste du programme est écrit de la même main, avec les figures interactives et votre progression.