Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Degré d'un graphe

Posté par
Theo92
11-05-12 à 15:38

Bonjour,

j'essaie de démontrer que la somme des carrés des degrés des sommets d'un graphe est égale à la somme des degrés des 2 sommets de chaque arête, soit pour G=(S,A) un graphe simple d'ordre n à m arêtes :
(x,y)A (d(x)+d(y)) = xS d2(x)
Ce que je ne comprends pas, c'est pourquoi on a obligatoirement d(x)+d(y) =< n.
Est-ce à dire que la définition d'un graphe simple implique qu'il ne contienne pas de triangle?

Merci par avance pour vos éclaircissements.

Posté par
matovitch
re : Degré d'un graphe 11-05-12 à 15:48

Bonjour,

Je suis très fatigué, mais non, la définition d'un graphe n'est pas "contrainte". L'inégalité m'étonne aussi.
(j'aurais dit 2(n-1)).

Posté par
matovitch
re : Degré d'un graphe 11-05-12 à 16:00

Je vois...enfin je crois. En fait ça serait plutôt d(xy) non ? On "compresse" l'arrête xy, puis on estime le degré.
Dans ce cas, il est inférieur à n-2.

Posté par
Theo92
re : Degré d'un graphe 11-05-12 à 16:15

Merci pour votre réaction.

En fait, je ne parviens pas à justifier l'égalité des 2 sommes dans un graphe simple (cas le plus général).
On fait la somme sur les arêtes et un sommet x apparaît autant de fois que son degré.
Comme sa contribution est d(x), on a donc le xS d2(x) ?

Merci à nouveau

Posté par
matovitch
re : Degré d'un graphe 11-05-12 à 16:51

J'ai raconté des âneries. On a bien :

\sum_{xy\in A} d(x)+d(y)=\sum_{x\in S}\sum_{xx_i\in A}d(x)=\sum_{x\in S}d(x)^2

Posté par
matovitch
re : Degré d'un graphe 11-05-12 à 16:51

C'est intuitif, mais le calcul n'explicite pas bien le résultat....

Posté par
Theo92
re : Degré d'un graphe 11-05-12 à 20:24

Merci de votre aide, et bonne soirée.
Cordialement.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !