# OLA, TD5
## Exercice 1: Vrai ou faux

1. Vrai FEABCG
2. Faux : le graphe est orienté
3. Faux pour les mêmes raisons
4. Vrai : le chemin vide
5. Faux : de H on ne peut pas aller aux autres sommets
6. Faux parce qu'il manque C et G

## Exercice 2: Auto-défense intellectuelle

Alice admet que H ⇒ ¬ T et ¬ H
Elle en déduit T.
Son raisonnement n'est pas valide, on peut avoir les hypothèses vraies mais la conclusion fausse.

Le fait que H ne soit peut-être pas fausse ne permet pas de conclure que H est vraie.

## Exercice 3 : Parcours en profondeur et détection de cycles

1. Etats successifs de la pile:
[]
[A]
[A ; B]
[A; B ; C]
[A; B ; C ; D]
[A; B ; C ; D ; G]
[A; B ; C ; D ; G ; F]
[A; B ; C ; D ; G]
[A; B ; C ; D ; G ; H]
[A; B ; C ; D ; G]
[A; B ; C ; D ]
[A; B ; C]
[A ; B]
[A ; B ; E]
[A; B]
[A]
[]

2.
On applique visiter S :
- soit S est déjà marqué et on ne fait rien, la pile ne bouge pas
- soit on empile S et on obtient [S1 ; ... ; Sn ; S]
Même si on ajoute des sommets à visiter dans la pile (les voisins de S), à la fin la pile sera toujours [S1 ; ... ; Sn ; S] et comme la dernière instruction est de dépiler, on aura la liste [S1 ; ... ; Sn ].

Donc au début de visiter et à la fin de visiter, la pile reste la même.

encours.depiler() retire le sommet qu'on est en train de visiter (donc ici, S)

3. Quand on ajoute un sommet S à la pile [S1 ; ... ; Sn ], ça veut dire que S est un successeur de Sn donc la pile est une suite de sommets successeurs les uns des autres, donc c'est un chemin.

4. Contre-exemple du critère:

On peut garder le même critère en ajoutant la condition que le sommet marqué doit déjà être dans la pile.
En effet, rencontrer un sommet S marqué veut dire = il existe une arête entre le sommet en haut de la pile et S
Et comme S est déjà dans la pile, cela veut dire qu'il y a un chemin non vide entre S et S (donc un cycle)

## Exercice 4 : Algorithme de Kosaraju-Sharir pour les composantes fortement connexes

1.
a) On suppose qu'il existe des sommets visités à partir de s1 qui ne sont pas dans la composante fortement connexe C1 de s1.
On regarde le premier sommet visité s qui n'est pas dans C1.
Il y a une arête entre s et un sommet de C1.
Cela veut dire que s est dans le halo de C1.
Donc le numéro de s est plus petit que le numéro de s1. Donc le numéro de s est strictement plus petit que 1 ce qui est impossible car la numérotation commence à 1.
On a bien une contradiction. Donc on a montré par l'absurde la propriété.

b) A partir de s1, on explore tous les sommets accessibles depuis s1 donc, par définition de la composante fortement connexe, on explore bien tous les sommets de cette composante C1.

c) On suppose qu'on a la numérotation avec la bonne propriété.
Algorithme:
On prend le sommet de plus petit numéro, on explore tous les sommets à partir de lui, et on les note comme faisant partie de sa composante fortement connexe.
On les retire du graphe.
On explore ensuite le graphe restant en prenant le sommet de plus petit numéro qu'il reste et ainsi de suite jusqu'à ce qu'il ne reste plus de sommets dans le graphe.

2.

a)
C'est un parcours en profondeur mais dans le sens inverse car on regarde les prédécesseurs.

b)