Applications

Composantes connexes

Soit \(G\) un graphe non orienté. La composante connexe d’un sommet \(s\) de \(G\) est l’ensemble des sommets atteignables depuis \(s\) en suivant un chemin dans \(G\).

Exercice

  1. Décrire un algorithme pour calculer toutes les composantes connexes d’un graphe non orienté

  2. (Bonus) Implanter cet algorithme et visualiser son exécution

Généralisation

Exercice:

  1. Généraliser la fonction parcours de la fiche 01-ParcoursDeGraphe.ipynb pour qu’elle prenne en argument la fonction de voisinage du graphe plutôt que le graphe lui-même.

from typing import Callable, Iterable, Set
from graph import Node

def parcours_fonction(voisins: Callable[[Node], Iterable[Node]], u: Node) -> Set[Node]:
    """
    INPUT:
    - `voisins`: une fonction telle que `voisins(v)` renvoie les voisins sortants de `v`
    - 'u' - un sommet du graphe
    
    OUTPUT: l'ensemble des sommets `v` de `G`
            tels qu'il existe un chemin de `u` à `v`
    """
    # YOUR CODE HERE
    raise NotImplementedError()
  1. Testez votre fonction sur l’exemple suivant.
    Indication: étant donné un graphe G tel que implanté précédément, la fonction voisins requise par distance peut être construite comme suit:

from graph import examples
G = examples.parcours_directed()
voisins = G.neighbors
assert parcours_fonction(voisins, 'D') == {'D', 'F', 'G', 'H'}
  1. Reprenez de même tous les tests de la fiche 01 avec votre nouvelle fonction

Application: ensembles définis récursivement

De nombreux ensembles mathématiques sont définis en donnant quelques éléments initiaux, puis en applicant récursivement un processus permettant de produire de nouveaux éléments à partir d’éléments déjà présents. Par exemple, l’ensemble des entiers naturels est construit à partir de \(0\) et de la fonction successeur \(x \mapsto x+1\).

Définition:

Soit \(E\) un ensemble, \(R\subset E\) un sous ensemble fini, et \(f\) une fonction associant à chaque élément de \(E\) un sous-ensemble fini de \(E\). L’ensemble \(f\) défini récursivement par \(R\) et \(f\) est le plus petit sous-ensemble de \(E\) contenant \(R\) et stable par \(f\): si \(e\in F\) alors \(f(e)\subset F\).

Exercice

Décrire les ensembles définis récursivement obtenus dans chacun des cas suivants:

  • \(E=\mathbb N\), \(R=\{1\}\), \(f(e) = \{ e + 2 \}\) YOUR ANSWER HERE

  • \(E=\mathbb N\), \(R=\{1\}\), \(f(e) = \{ 2e, e+3 \}\) YOUR ANSWER HERE

  • \(E\): listes, \(R=\{()\}\), \(f(u)\): rajouter \(0\) ou \(1\) à la fin du \(u\) YOUR ANSWER HERE

  • \(E\): listes, \(R=\{(1,2,3,2,1)\}\), \(f(u)\): supprimer la première ou dernière lettre de \(u\) YOUR ANSWER HERE

Exercice

Soit \(C_n\) l’ensemble récursivement défini par:

  • \(R=\{ (\underbrace{1,1,\cdots,1}_n)\}\)

  • \(f\) qui a une liste associe toute les listes obtenues en regroupant et sommant deux entrées consécutives
    Par exemple, \(f((2,3,1,1)) = \{(5,1,1), (2,4,1), (2,3,2)\}\)

  • Calculer à la main les quatres éléments de \(C_3\), sans oublier \((3)\)!

  • Calculer avec la machine tous les éléments de \(C_6\).

  • Combien y en a t’il?

  • Même chose pour \(C_1,C_2,C_3,C_4,C_5\).

  • Que conjecturez vous?

  • Pouvez vous le prouver?

YOUR ANSWER HERE

Exercice (bonus) Une permutation est une liste d’entiers telle que, si \(n\) est sa longueur, alors tous les entiers de \(1\) à \(n\) apparaissent exactement une fois. Décrire l’ensemble des permutations comme un ensemble énuméré. Utiliser cela pour lister toutes les permutations de longueur \(n\leq 6\)

# YOUR CODE HERE
raise NotImplementedError()