suit la théorie des graphes (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 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.
=
بلغ الادارة عن محتوى مخالف من هنا
ابلغون على الروابط التي لا تعمل من هنا