Algo2/dm1.md

author	title	geometry	header-includes
Augustin LUCAS	DM 1	margin=2.6cm	\usepackage{tikz-cd}

Exercice 1

1. Soit G un graphe non orienté.
   a. Supposons que G admette un cycle eulérien. Notons (a_1, a_2, \dots, a_n) la liste des sommets de ce cycle.

     Soit $a$ un sommet de $G$.
     - si $a$ n'est pas dans $a_1, \dots, a_n$, alors aucune arête n'a d'extrémité en $a$,
       $a$ est isolé donc de degré 0 (pair).
     - sinon, à chaque indice $i$ tel que $a_i = a$, on trouve deux arêtes distinctes
       ayant une extrémité en $a$: $(a_i, a_{i+1})$ et $(a_{i-1}, a_i)$.  
       (modulo les cas particuliers $i \in \{1, n\}$)  
       Alors, $a$ est de degré pair car chaque arête utilisée dans le cycle est distincte des autres.
   
     Soient deux sommets $a, b$ de $G$ non isolés, alors soient $i, j$ tels que $a = a_i$, $b = a_j$,
     quitte à renommer $a$ et $b$, on suppose $i \leq j$.
     Alors $a_i, a_{i+1}, \dots, a_j$ est un chemin de $a$ à $b$.
     Donc - à l'exception des sommets isolés - $G$ est connexe.
   

   b. Si G = (S, A) est connexe, avec tous ses sommets de degré pair, On peut construire un cycle eulérien C pour G de la manière suivante :

        ```
        C = []
        A' = A
        c_i = prendre un sommet de G
        c = c_i
        Tant que A' n'est pas vide:
            #i = nombre d'arêtes ayant une extrémité en i dans A'
            si #i == 1 et #A > 1:
                (c, c2) = a dans A' partant de c, c2 != c_i
            sinon:
                (c, c2) = a dans A' partant de c
            retirer (c, c2) de A'
            ajouter c2 à C
            c = c2
        ```
   

2. Soit G un graphe non orienté. a. Supposons que G admette un chemin eulérien. Notons C = (a_1, a_2, \dots, a_n) la liste des sommets de ce chemin.

     Si $a_1 = a_n$, on a le résultat d'après la question 1)
   
     Sinon, on note $G'$ le graphe $G$ où les sommets $a_1$ et $a_n$ sont confondus.
     Dans $G'$, $C$ est un cycle eulérien, donc d'après la question 1),
     $G'$ est connexe et tous ses sommets sont de degré pair.
   
     Or, $C$ est un chemin de $a_1$ à $a_n$ dans $G$, donc $G$ est connexe.  
     De plus, le degré de $a_1$ et $a_n$ est assez naturellement impair car chacune
     a $2\times \# \{a_i \in C\}-1$ arêtes
   

   b. - Si G = (S, A) est connexe avec 0 sommets de degré impair, d'après la question 1), G admet un cycle eulérien, qui est aussi un chemin eulérien - Sinon, si G = (S, A) est connexe avec 2 sommets de degré impair, On peut construire un chemin eulérien de la manière suivante :

        ```
        C = []
        A' = A
        c, c_i = 2 sommets de A de degré impair
        Tant que A' n'est pas vide:
            #i = nombre d'arêtes ayant une extrémité en i dans A'
            si #i == 1 et #A > 1:
                (c, c2) = a dans A' partant de c, c2 != c_i
            sinon:
                (c, c2) = a dans A' partant de c
            retirer (c, c2) de A'
            ajouter c2 à C
            c = c2
        ```
   

3. Soit G = (S, A) un graphe orienté. Supposons pour la rédaction que G n'ait pas de sommets isolés. a. Supposons que G admette un cycle eulérien Notons (a_1, a_2, \dots, a_n) la liste des sommets de ce cycle.

    Soit $a$ un sommet de $G$.
    À chaque indice $i$ tel que $a_i = a$, on trouve deux arêtes distinctes
    ayant une extrémité en $a$: $(a_i, a_{i+1})$ et $(a_{i-1}, a_i)$,
    l'une entrante, l'autre sortante.  
    (modulo les cas particuliers $i \in \{1, n\}$ où les indices diffèrent)  
    Alors, $a$ possède autant d'arêtes entrantes que sortantes, c'est-à-dire $d^+(a) = d^-(a)$
   
    De plus, soient $a, b$ des sommets de $G$. On a $i, j$ tels que $a = a_i, b = a_j$.
    - Si $i \leq j$, $a_i, a_{i+1}, \dots, a_j$ est un chemin de $a$ à $b$.
    - Sinon, $a_j, a_{j+1}, \dots, a_n, a_1, \dots, a_i$ est un chemin de $a$ à $b$.
   
    Alors, $G$ est fortement connexe et $\forall x \in S, d^+(x)=d^-(x)$
   

   b. Supposons G fortement connexe avec $\forall x \in S, d^+(x)=d^-(x)$ On peut construire un cycle eulérien C pour G de la manière suivante :

   ```
   C = []
   A' = A
   c_i = prendre un sommet de G
   c = c_i
   Tant que A' n'est pas vide:
       #i = nombre d'arêtes ayant une extrémité en i dans A'
       si #i == 1 et #A > 1:
           (c, c2) = a dans A' partant de c, c2 != c_i
       sinon:
           (c, c2) = a dans A' partant de c
       retirer (c, c2) de A'
       ajouter c2 à C
       c = c2
   ```
   

4. Le graphe représentant les différentes parties de cette ville, dont les arêtes sont les ponts, a pour degrés de ses sommets les valeurs 3, 3, 3, 5. Donc ses 4 sommets sont de degré impair, ainsi, il n'existe pas de telle balade à Königsberg (d'après 2).

5. Algorithme

   Entrée:
       G sous forme de listes d'adjacence
   C = []
   G' = copie de G
   c_fin = 0
   Tant que G'[c_i] == []:
       c_fin += 1 # c_i ne doit pas être isolé
   c = c_fin
   Tant que G'[c] != []:
       j = 0
       c_suiv = c_fin
       Tant que c_suiv == c_fin et j < #(G'[c])
           j += i
           c_suiv = G'[c][j]
   
       retirer c_suiv de G'[c]
       retirer c de G'[c_suiv]
       ajouter c_suiv
       c = c_suiv
   
   Pour i allant de 0 à #G':
       Si G'[j] != []:
           échouer "Pas de cycle eulérien possible"
   renvoyer C
   

   Dans le pire cas, le sommet avec le plus grand nombre d'arêtes est celui choisi comme c_{fin}, si on y retourne un coup sur deux, on pourrait notamment avoir une complexité en O(|S|^2). Pour parer à celà, on pourrait se souvenir du nombre d'arêtes qui lui sont adjacentes non visitées et ne l'ignorer que s'il en reste qu'une seule. Si on écarte ce cas extrême, la boucle Tant que sera utilisée |A| fois et l'algorithme sera au total en O(|S|+|A|)

Exercice 2

1. Soit un mot sur \Sigma de longueur L. Alors, il contient au plus L-(p-1) sous-mots distincts de longueur p.
   Donc L(n, p) \geq n^p + p-1 car il existe n^p mots de longueur p sur l'alphabet \Sigma.

2. On considère le graphe orienté G dont les sommets sont les mots de \Sigma^{p-1}. L'arête (a, b) pour a = a_1, \dots a_{p-1} et $b = b_1, \dots b_{p-1}$ étant dans le graphe si a_2 = b_1, a_3 = b_2 \dots a_{p-1} = a_{p-2}.

   Chaque mot de \Sigma^p est représenté par une arête de G.

   Alors, trouver un mot contenant tous les codes possibles correspond à trouver un chemin passant par toutes les arêtes au moins une fois.
   Le cas optimal étant donc de trouver un chemin eulérien.

   On vérifie bien que le graphe est fortement connexe, et que pour tout sommet x, d^+(x) = d^-(x) = n.

   Donc G admet un chemin eulérien d'après Ex1.3

   La séquence formée par ce chemin est constituée de :

   • un mot initial de taille p-1 correspondant au premier sommet du chemin
   • la lettre ajoutée pour passer d'un mot à un autre pour chaque arête (n^p fois)

   Alors, la séquence formée est de taille n^p + p -1.

Finalement, L(n, p) = n^p + p-1