Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Futur Membre du Club
    Prouver qu'il existe un circuit dans un graphe orienté avec un demi-degré suffisant
    Bonjour,
    Comment montrer rigoureusement qu'un graphe orienté dont tout les sommets ont un demi degrés extérieur(d+)>= 1, possède un circuit ?

    Merci

  2. #2
    Expert confirmé
    salut

    Quelques rappel :

    un graphe orienté est un P-Graphe si il comporte au plus p arcs entre deux sommets
    le plus souvent les études se font sur des 1-graphe

    Un graphe orienté est dit élémentaire s’il ne contient pas de boucle. (donc pas de circuit)

    Un graphe orienté est dit complet s’il comporte un arc (Si, Sj ) et un arc (Sj , Si) pour tout couple de sommets différents Si,Sj ∈ S2

    2°) Dans un graphe orienté, on distingue les sommets successeurs des sommets prédécesseurs
    SUCC(Si) = {Sj/(Si,Sj) ∈ A}
    PRED(Si) = {Sj/(Sj,Si) ∈ A}

    Dans un graphe orienté, le demi-degré extérieur d’un sommet Si, noté d◦+(Si), est le nombre
    d’arcs partant de Si (dans le cas d’un 1-graphe, on aura d◦+(Si) =| succ(Si) |)

    pour qu'il y ai circuit il faut que l'on puissent vérifier que S0= Sn et que n >= 1

    sinon ici tu auras aussi quelques réponses
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  3. #3
    Expert éminent sénior
    Bonjour

    Comment montrer rigoureusement qu'un graphe orienté dont tout les sommets ont un demi degrés extérieur(d+)>= 1, possède un circuit ?
    Par récurrence.

    • Si le graphe a un seul nœud, alors l'arête pointe sur le nœud. Il y a donc un circuit. La propriété est vraie pour un seul noeud.
    • Supposons la propriété vraie pour un graphe de n nœuds.
    • Si on prend un graphe de n+1 nœuds, il y a 3 cas :
      • Soit ce (n+1)ème nœud pointe vers lui-même et il y a un circuit.
      • Soit ce (n+1)ème nœud pointe vers le sous-graphe de n noeuds qui pointe vers le (n+1)ème et il y a donc un circuit.
      • Soit ce (n+1)ème nœud pointe vers le sous-graphe de n noeuds qui ne pointe pas vers le (n+1)ème et on utilise la formule de récurrence pour dire que le sous graphe comporte un circuit.


    Conclusion : Pour tout graphe d'au moins un noeud, si tous les sommets ont un demi degrés extérieur>= 1, il y a un circuit.

    À noter : je pense que cela est faux pour un graphe avec zéro nœud ... le prof y a-t-il pensé ?
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  4. #4
    Futur Membre du Club
    Bonsoir,
    Merci pour vos réponses !