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

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 (S_i, S_j ) et un arc (S_j , S_i) pour tout couple de sommets différents S_i,S_j ∈ S²

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

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

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

sinon ici tu auras aussi quelques réponses

Bonjour :coucou:

Citation:

---

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é ?

Bonsoir,
Merci pour vos réponses !