Bonjour je dois montrer par récurrence cette propriété 

Pour tout graphe sans triangle a n sommets et m arêtes m \( \leq \frac{n^2}{4} \)

Pour n=0 j'ai reussi a le montrer mais pour le n \( \geq \) 0 je ne sais pas trop comment m'y prendre

Je sais que ce graphe a n sommets possede(au moins) un sommet de degré inférieur ou egale a \( \frac{n}{2} \) mais je ne sais pas si ce serait utile.

Merci

Salut non pas besoin de cette propriété, en fait tu dois  :

1) prouver pour le cas d'initialisation : parfois 0 mais parfois 1, tout dépend si le cas 0 à du sens, parfois il n'en a pas et tu dois commencer par n = 1. Dans ce cas, pour n=0 c'est à dire pour 0 noeud, on n'a pas d'arète donc le théorème est vérifié.

2) pour n>0, on se réfère à un cas donné, on ajoute un noeud et on voit ce qui se passe. Partons du fait que ce soit vérifié pour n noeuds. On prend le pire cas possible, c'est à dire le graphe avec le plus d'arête possible pour n noeuds sans triangle. la relation m<=n^2/4 est bien vérifiée par hypothèse. Ensuite, on ajoute un noeud, et on remarque qu'on peut ajouter max n/2 arêtes à partir du nouveau noeud vers les anciens noeuds. En gros on ne peut relier qu"un ancien noeud sur deux au nouveau, sinon on aurait un triangle. Donc effectivement, on peut ajouter max n/2 arêtes. Ensuite c'est facile, on a :

n/2<n/2+(1/4)  => n/2 <(2n+1)/4 , par hypothèses => m+(n/2)<=((2n+1)/4)+n^2/4 => m+(n/2) <= ((n+1)^2)/4

On a bien prouver que le max d'arête totales est valables pour n+1 noeuds, donc c'est vrai. déso pour la syntaxe, j'espère que c'est assez clair

-
Edité par JeanCharles28 25 octobre 2017 à 21:48:43

Pourquoi on ajoute 1/4?

pour permettre la mise en évidence et obtenir n+1 à la place de n dans la formule de récurrence! j'ajoute 1/4 par ce que ça m'arrange pour le reste du développement

The triangle finding problem is the problem of determining whether a graph is triangle-free or not. When the graph does contain a triangle, algorithms are often required to output three vertices which form a triangle in the graph. Chase Bank Sign In