Comment utiliser la formule… : En additionnant tous les degrés des… — ECG1 appliquées | MetMat

Comment utiliser la formule d'Euler (des poignées de main) pour relier degrés et arêtes ?

En additionnant tous les degrés des sommets et en divisant par $2$ pour obtenir le nombre d'arêtes d'un graphe non orienté

Calculer (ou vérifier) le nombre d'arêtes d'un graphe non orienté à partir des degrés de ses sommets grâce à la formule des poignées de main.

Que ferais-tu face à un exercice de ce type ?

Soit le graphe non orienté à $5$ sommets dont les arêtes sont $\{1,2\}$ , $\{2,3\}$ , $\{3,4\}$ , $\{4,5\}$ , $\{5,1\}$ et $\{1,3\}$ . Vérifier la formule d'Euler et donner le nombre d'arêtes.

L'objectif

Calculer (ou vérifier) le nombre d'arêtes d'un graphe non orienté à partir des degrés de ses sommets grâce à la formule des poignées de main.

Le principe

Dans un graphe non orienté $G=(S,A)$ à $n$ sommets, chaque arête contribue à $2$ dans la somme des degrés, d'où la formule d'Euler (dite des poignées de main) : $\sum_{i=1}^{n}\deg(i)=2|A|$ ; en particulier, la somme des degrés est toujours paire.

La méthode

1
Je détermine le degré $\deg(i)$ de chaque sommet $i$ (nombre d'arêtes incidentes, ou somme des coefficients de la ligne $i$ de la matrice d'adjacence dans le cas non orienté).
Comment construire la matrice d'adjacence d'un graphe (orienté ou non) ?Voir
2
Je calcule la somme $S=\sum_{i=1}^{n}\deg(i)$ et je vérifie qu'elle est bien paire (sinon, c'est qu'il y a une erreur dans les degrés).
3
J'obtiens le nombre d'arêtes par $|A|=\dfrac{S}{2}$ et je conclus.

Pour comprendre, fais des exercices !

Exercice d'exemple

Soit le graphe non orienté à $5$ sommets dont les arêtes sont $\{1,2\}$ , $\{2,3\}$ , $\{3,4\}$ , $\{4,5\}$ , $\{5,1\}$ et $\{1,3\}$ . Vérifier la formule d'Euler et donner le nombre d'arêtes.

Étape 1 —

Je détermine le degré

\deg(i)

de chaque sommet

i

(nombre d'arêtes incidentes, ou somme des coefficients de la ligne

i

de la matrice d'adjacence dans le cas non orienté).

Je lis les degrés à partir de la liste d'arêtes : $\deg(1)=3$ (arêtes $\{1,2\}$ , $\{5,1\}$ , $\{1,3\}$ ), $\deg(2)=2$ , $\deg(3)=3$ , $\deg(4)=2$ , $\deg(5)=2$ .

Étape 2 —

Je calcule la somme

S=\sum_{i=1}^{n}\deg(i)

et je vérifie qu'elle est bien paire (sinon, c'est qu'il y a une erreur dans les degrés).

Je fais la somme : $S=3+2+3+2+2=12$ , qui est bien paire.

Étape 3 —

J'obtiens le nombre d'arêtes par

|A|=\dfrac{S}{2}

et je conclus.

D'où $|A|=\dfrac{12}{2}=6$ , ce qui coïncide avec le nombre d'arêtes énumérées.

$6$ arêtes, formule d'Euler vérifiée.

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

Comment utiliser la formule d'Euler (des poignées de main) pour relier degrés et arêtes ?

En additionnant tous les degrés des sommets et en divisant par 222 pour obtenir le nombre d'arêtes d'un graphe non orienté

Pour comprendre, fais des exercices !

En additionnant tous les degrés des sommets et en divisant par $2$ pour obtenir le nombre d'arêtes d'un graphe non orienté