Degré

Degré d'un sommet Pour un graphe ou un multigraphe, on appelle degré du sommet v, et on note d(v), le nombre d'arêtes incidentes avec ce sommet. Attention! une boucle sur un sommet est comptée deux fois. Dans un graphe simple, on peut aussi définir le degré d'un sommet comme étant le nombre de ses voisins (la taille de son voisinage). Lemme des poignées de mains La somme des degrés des sommets d'un graphe est égale à deux fois le nombre d'arêtes.

Dans le graphe ci-contre, on a les degrés: d(v1) = 2 d(v2) = 1 d(v3) = 3 d(v4) = 2 d(v5) = 1 d(v6) = 1

Degré d'un graphe

Le degré d'un graphe est le degré maximum de tous ses sommets. Dans l'exemple ci-dessus, le degré du graphe est 3.

Un graphe dont tous les sommets ont le même degré est dit régulier. Si le degré commun est k, alors on dit que le graphe est k-régulier.

Exercices

Exercice 1

Une suite décroissante (au sens large) d'entiers est graphique s'il existe un graphe simple dont les degrés des sommets correspondent à cette suite (par exemple, le triangle à trois sommets correspond à la suite 2, 2, 2). Les suites suivantes sont-elles graphiques?

1. 3, 3, 2, 1, 1
2. 3, 3, 1, 1
3. 3, 3, 2, 2
4. 4, 2, 1, 1, 1, 1
5. 5, 3, 2, 1, 1, 1
6. 5, 4, 3, 1, 1, 1, 1

Exercice 2

Démontrez le lemme des poignées de mains.

Exercice 3

Montrez qu'un graphe simple a un nombre pair de sommets de degré impair.

Exercice 4

Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié avec exactement trois autres?

Exercice 5

On s'intéresse aux graphes 3-réguliers. Construisez de tels graphes ayant 4 sommets, 5 sommets, 6 sommets, 7 sommets.
Qu'en déduisez-vous?
Prouvez-le!

Exercice 6

• Chaque personne connaît au moins 7 autres
• Toute information détenue par une personne est répercutée dans la minute qui suit à ses connaissances (et uniquement à elles)

Didier Müller, 6.2.03