Applications

Applications#

Composantes connexes#

Définition

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 (pour aller plus loin)

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

    BEGIN SOLUTION END SOLUTION

  2. Implanter cet algorithme et visualiser son exécution

Généralisation#

Exercice

  1. Généraliser la fonction parcours de la fiche 01-ParcoursDeGraphe.md 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`
    """
    ### BEGIN SOLUTION
    marked = {u} # L'ensemble des sommets déjà rencontrés
    todo   = {u} # L'ensemble des sommets déjà rencontrés, mais pas encore traités
    
    while todo:
        # Invariants:
        # - Si `v` est dans `marked`, alors il y a un chemin de `u` à `v`
        # - Si `v` est dans `marked` et pas dans `todo`
        #   alors tous les voisins de `v` sont dans dans `marked`
        v = todo.pop()
        for w in voisins(v):
            if w not in marked:
                marked.add(w)
                todo.add(w)
    return marked
    ### END SOLUTION

Exercice (suite)

  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'}

Exercice (suite)

  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 (pour aller plus loin)

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

  • \(E=\mathbb N\), \(R=\{1\}\), \(f(e) = \{ e + 2 \}\) BEGIN SOLUTION END SOLUTION

  • \(E=\mathbb N\), \(R=\{1\}\), \(f(e) = \{ 2e, e+3 \}\) BEGIN SOLUTION END SOLUTION

  • \(E\): listes, \(R=\{()\}\), \(f(u)\): rajouter \(0\) ou \(1\) à la fin du \(u\) BEGIN SOLUTION END SOLUTION

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

Exercice (pour aller plus loin)

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?

BEGIN SOLUTION

END SOLUTION

Exercice (pour aller plus loin)

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\).

BEGIN SOLUTION

END SOLUTION