Voila je vous expose ce problème
 
Soit G un graphe orienté, connexe et vérifiant les Conditions de degrés de liberté (CDI)
 
---  
CDI :  
G vérifie les CDI si :  
Il existe s appartemenant à G, d-(s)=0
et quelquesoit x différent à s, d-(x)=1
---
 
Montrer que le graphe G' (graphe non orienté associé) est acyclique
 
Merci d'avance

euh c'est quoi ta notation d-(x) ?
 
Réponds svp, je veux bien essayer de faire ton exo, ça a l'air sympa

c'est le degré entrant du sommet x

oui car ya le _ , le - mai pas le moins supérieur

Raisonnement par l'absurde.
Tu supposes que ton graphe G' issu de G vérifiant les CDI comporte un cycle.
Avec les conditions de départ tu trouves une contradiction (au niveau du demi-degré intérieur) et donc G' est acyclique.
 
Ebauche de démo :
Si G' comporte un cycle, alors on a une chaine (x1,x2,...,xk,x1)
Mais comme G' est connexe, il existe une chaine entre la source s et les autres sommets x1,x2,...,xk.
Donc il existe une chaine (s,xi,...,xj,x1,x2,...,xk,x1)
Il faut montrer que les sommets d'une telle chaine ne peuvent pas vérifier les CDI dans G.
d-(s)=0 donc s prédécesseur de xi et d-(xi)=1.
Comme xi a déjà un prédécesseur, le prédécesseur de xi+1 est xi.
et ainsi de suite jusqu'à xk.
Quand on retrouve x1 en bout de chaine, deux possibilités s'offre à nous.
Soit x1 est le prédécesseur de xk
Soit xk est le prédécesseur de x1
Dans les deux cas la contrainte d-(x) = 1 est violée. D'où la contradiction donc G' est acyclique.

Autre manière de démonstration :
Le graphe G est un arbre. Or un arbre par définition n'a pas de cycle donc G' est acyclique...
 
Evidemment, ce n'est pas dans l'esprit de l'exercice que d'utiliser cette méthode.

super pain tu déchires merci beaucoup