Démonstration graphe régulier.

[jeremux]

Bonsoir dans mon cours j'ai:

Tout couple de nombres naturels d et n tels que 0<=d<=n-1. Il existe un graphe régulier d'ordre n et de degré d.
Mon prof a dit que la démo était trivial...mais bon pour moi pas =(.
J'ai essayé par récurrence sur n, pour l'initialisation ça va. Mais ensuite...J'ai essayé d'introduire un un sommet supplémentaire pour la démonstration du rang suivant...mais sans succès.

Quelqu'un pourrait-il m'aider, ça m'aidera pour mon futur devoir =).

Merci d'avance!

[Ben314]

Salut,
Tu as essayé pour n=3 et d=1 ?

[houda 20]

Bonsoir
Alors en premier jeremux, lorsqu'on comprend pas on demande, même si le prof disait que c'est trivial
bon pour le reste, un graphe est caractérisé par l'ensemble de ses sommets et l'ens de ses arêtes
un sommet a un degré mais pour un graphe?? que signifie le degré d'un graphe??
tu veux dire un graphe d-régulier, c'est ça?
et s'il te plait pourrai tu donner le contexte ou le prof a fait cette remarque??
essayes par absurde, ...on utilise souvent les demos par absurde en théorie des graphes...
je vais encore réfléchir et si j'arriverai à quelque chose je te le dirai...

[houda 20]

bon par absurde,
on suppose qu'il existe n et d tel qu'aucun graphe d'ordre n n'est d-régulier
i.e
quelque soit le graphe d'ordre n, il existe tjrs un xi tel que d°(xi) est différent de d

[jeremux]

Oui je veux dire d-regulier. En fait il a balancé ça juste après avoir définit un graphe régulier (tous les sommets ont même degré). En fait j'ai continué sur mon idée le fait d'introduire un sommet supplémentaire, ça ne change pas le nombre d’arêtes. Donc là je sais pas si ça va changer le d...si j'arrive à montrer que c'est toujours d-régulier, alors c'est fini non? ...Bref je suis surement confus. Mais j'ai l'idée....

Je continue de chercher!

Merci

[jeremux]

bon par absurde,
on suppose qu'il existe n et d tel qu'aucun graphe d'ordre n n'est d-régulier
i.e
quelque soit le graphe d'ordre n, il existe tjrs un xi tel que d°(xi) est différent de d

J'ai pas vu, je me penche là dessus.

Merci!

[houda 20]

pourquoi l'absurde?
parce que c'est souvent difficile de trouver une demo directe, c'est plus facile de chercher une contradiction avec les propositions qu'on a
j'ai fait la théorie des graphes, l'année dernière je ne me rappelle pas de trop de choses
mais ce que je retiens très bien est qu'il faut tjrs essayer avec l'absurde en premier...

[houda 20]

J'ai pas vu, je me penche là dessus.

Merci!

c'est pas la demo voyons!!
j'essaye de formuler le pb avec toi c'est tout

[jeremux]

Salut,
Tu as essayé pour n=3 et d=1 ?

Lol ça marche pas...où alors je ne vois pas! Pourtant la propriété a été citée en cours! (><)

[houda 20]

"pour l'ajout d'un sommet, c'est vrai ça ne changera pas le nbres d'aretes et tu pourra constriure ton graphe d-régulier ac n+1 sommets" ça c'est faux, le nbres d'aretes changeras car ça ajoute des aretes aux sommets auxquels on va relier le nieme sommets

[jeremux]

S'il n'a pas démontré c'est peut-être que ce n'était pas utile...Mais bon aussi étrange que cela puisse etre. Je retiens mon cours que par les démonstration, ça me permet d'etre convaincu...Et là ben c'est raté! lol
Bonne soirée et merci, je vais aller prendre des force :dodo: .

A bientot, et merci encore! :lol3:

[houda 20]

voilà une propo qui pourra aider
dans un graphe il existe tjrs x et y de même degré

[houda 20]

bonne chance alors!!

[Doraki]

Si d et n sont impairs, tu peux voir qu'il ne peut pas exister de graphe d-régulier à n sommets,
en tentant de compter le nombre d'arêtes qu'il doit contenir.

[jeremux]

Donc si G est d-régulier de degré n et d impair. Alors il est impossible de construire un graphe d-régulier de degré n+1...Par le lemme des poignées de mains ça oblige que d et n ne peuvent etre simultanément impair. D'où ma conclusion.

Soit la propriété du prof est fausse. Soit je suis mal-barrée!