Demande d'aide sur un problème de Graphe

Demande d'aide sur un problème de Graphe - Aide aux devoirs - Emploi & Etudes

Marsh Posté le 30-10-2005 à 12:02:33    

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

Reply

Marsh Posté le 30-10-2005 à 12:02:33   

Reply

Marsh Posté le 30-10-2005 à 15:54:04    

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


---------------
Taupin un jour, Normalien toujours...
Reply

Marsh Posté le 30-10-2005 à 16:13:03    

c'est le degré entrant du sommet x

Reply

Marsh Posté le 30-10-2005 à 18:46:45    

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

Reply

Marsh Posté le 30-10-2005 à 22:32:54    

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.


Message édité par pains-aux-raisins le 30-10-2005 à 22:33:50
Reply

Marsh Posté le 30-10-2005 à 23:03:01    

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.

Reply

Marsh Posté le 31-10-2005 à 21:41:21    

super pain tu déchires merci beaucoup

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed