Bornes sur les degrés d'un graphe

[Résolu/Fermé]
Signaler
-
 ghesm -
Bonjour à tous,
Je me demande si quelqu'un peut m'aider à trouver des bornes supérieur et inférieur d'un graphe non orienté ayant n sommets (noeuds) et m arêtes?
Merci.


1 réponse

Bonjour,

Au risque de passer pour un ignare, pourrais-tu m'expliquer ce qu'est un graphe non orienté, de même ce que sont ses bornes supérieures et inférieures?

Merci. ;-)
Un graphe non orienté est un graphe dont les liens entre ses sommets sont des arêtes c-à-d pas de flèches sur elles, et ma question est: étant donné un graphe G, quel est le degré minimum que peut avoir un noeud (sommet) quelconque (de même pour le degré maximal)?
Merci.
Par curiosité, j'ai posé la question à mon ami Google, et parmi les nombreuses réponses reçues, j'ai ai déduit que le degré mini d'un noeud est 1.
En effet il y a au moins une arrête ayant ce noeud pour extrémité , autrement dit, il y a au moins une arrête qui part de ce noeud.
Quant au degré maxi d'un noeud, il est n-1, n étant le nombre de noeuds du graphe, si on exclut les boucles, sinon il est égal à n.

Cordialement.
Merci de ta recherche ;)
Mais au fait je cherche des bornes en fonction de n (nombre de noeuds) et m (nombre d'arêtes) et qu'elles forment un intervalle le plus fin possible!
Par exemple, étant donné un graphe de 4 noeuds et 5 arêtes on peut jamais avoir un tel graphe possédant un noeud de degré 1!
Remarque, on considère pas des boucles!

Merci.
Boujour. La nuit a porté conseil.

Soit N le nombre de noeuds du graphe
M le nombre d'arrêtes
Dmin le degré mini d'un noeud
Dmax le degré maxi d'un noeud

M doit vérifier les conditions suivantes

SI
   M >= (N-1) ; nombre d'arrêtes mini
ET
   M <= N*(N-1)/2 ; nombre d'arrêtes maxi pour un graphe complet

Alors

   Dmax=N-1
   SI M <= (N*(N-1)/2)-(N-2)
      Alors Dmin=1 
	  Sinon Dmin=(N-1)-((N*(N-1)/2)-M)

Exemple: un graphe à N=5 noeuds
condition initiale : M>=4 et M<=10 ;(5*4/2)
On a toujours Dmax = 5-1 = 4
Si M est compris entre 4 et 7 alors Dmin=1
sinon Dmin = (N-1)-((N*(N-1)/2)- M)
si M = 8 -> Dmin = 4 - (10 - 8) = 2
si M = 9 -> Dmin = 3
si M = 10 -> Dmin = 4
Merci de cette bonne réponse ;)
Mais comment peut-on prouver ce résultat?