1 réponse à ce sujet

[well6]

bonjour j ai essaye de reoudre un exo en graphe qui est le suivant:
on considere un graphe simple(non oriente et sans boucle) tel que le nomnre de sommet n =2p et a m arrete
montrer que si le graphe G ne contient pas de cycle de longueur 3 , alors m<=p^2

jai pense a utiliser une recurence sur p et a faire un raisonnement par contrapose , mais je tourne en rond.
pouvez vous m aider silvou plait merci

[Boltzmann_Solver]

well6, le 08 novembre 2010 - 23:49, dit :

bonjour j ai essaye de reoudre un exo en graphe qui est le suivant:
on considere un graphe simple(non oriente et sans boucle) tel que le nomnre de sommet n =2p et a m arrete
montrer que si le graphe G ne contient pas de cycle de longueur 3 , alors m<=p^2

jai pense a utiliser une recurence sur p et a faire un raisonnement par contrapose , mais je tourne en rond.
pouvez vous m aider silvou plait merci

Bonjour well,

Je suis pas mathématicien (ni informaticien sauf si tu comptes un peu de programmation...). Donc, ne prend pas ce que je te dis comme une certitude (mais c'est sympa la théorie de grahes)
Ici, une récurrence me semble bien.

I : Facile (commence à p=3).
H : Supposons le graphe complet à 2p sommet tel que m p². A t-on transmission au rang p+1. Celui-ci peut être représenté par une polygone de 2p sommets avec un certains nombre d'arêtes interne à la figure. On intègre les deux sommets pour former un polygone de 2p+2 sommets.

On a 3 nouvelles arêtes lié à l'intégration dans le polygone et en interne, on a au plus, 2(chaque nouveau sommet)*(2p-6)/2

m(p+1) p² + 2p-4+3 p²+2p+1 = (p+1)².

Donc, Prop vrai au rang p ===> vrai au rang p+1.

C : Par récurrence, etc..

Je t'ai donné l'idée de base. Si tu n'y arrive pas, je détaillerai ma rédac. Mais, c'est juste du dénombrement mais je te recommande de faire les dessins.

On intègre les deux nouveaux sommets qui peut créer une arrête.