Inscription / Connexion Nouveau Sujet
maths discrètes-graphes
bonjour j'ai un exo concernant les graphes et j'aurais bien aimé que quelqu'un puisse m' aider merci :
Dans un graphe (non orienté) G, on appelle triangle un triplet de sommets distincts x,y, z tels que xy,yz, zx sont des arêtes de G. Soiet G=(X,E) un graphe simple, $n$ le nbre de sommets, $m$ le nombre d'arêtes. On suppose que G ne contient pas de triangles.
1) Montrer que pour deux sommets voisins distincts x, y, le nbre n_x de sommets de X\ {x,y} voisins de x et le nbre n_y de sommets de X \{x,y} voisins de y satisfont l'égalité:
$n_x+n_y \leq n-2$
--pr celà je pense que l' on peut faire :
n_x =< n-1 (tout les sommets moins le sommet $x$)
n_y =<n-1 (idem)
d' oùu n_x+n_y =< n-2
(mais normalement on aurai 2n-2... donc je bloque)
2) on me demande de déduire par induction sur $n$, l'inégalité :
m=< n^2/4
3) Trouver une famille infinie de graphes simples et sans triangles pour lesquels on a l' égalité :
m=n^2/4$
Donc voilà si des personnes pouvait me mettre sur le bon chemin merci.
Bonjour helmut_perchut!
(1) Si dans X il y a n sommets, dans X-{x,y} il y a n-2 sommets (x et y non confondus). Si x et y sont voisins et que le graphe ne contient pas de triangles, x et y n'auront pas de somnmet voisin en commun. Donc les voisins de x et y sont au plus au nombre de n-2.
Si tu n'y est toujours pas, on a (avec V(x) l'ensemble des voisins de x)
(2) Imaginons pour commencer que n est pair. avec n=2 un graphe simple a au plus 1 arête, donc l'inégalité est vérifiée. Supposons que ceci est vrai pour n-2 et prouvons-le pour n.
Je considère alors un graphe G(X,E) simple sans triangles avec #(X)=n et #(E)=m. Si m=0 le résultat est trivial. Sinon on peut choisir une arête (u,v) de E. Le sous graphe induit G' de G sans u et v a n-2 sommets et au plus arêtes. Pour compter les arêtes de G il suffit de compter les arêtes de G sans G' et sommer avec celles de G'.
Les arêtes de G qui ne sont pas dans G' sont (u,v) et (u,k), (v,k) avec k sommet de G'. L'arête (u,v) est unique et les arêtes du type (u,k), (v,k) sont au plus n-2 (cf point (1) de l'exercice). On a donc que le nombre d'arêtes de G vérifie l'inéquation
Pour n impair la peuve est semblable.
(3) Regarde les graphes bipartis-complets. Si n est pair prend avec n/2 sommets chacun. Si n est impair prend
avec respectivement (n-1)/2 et (n+1)/2 sommets.
Isis
Annuler
connectez vous
topologie en post-bac