# Mini Projet ~ Prépa agreg 2014 > Ce petit document (aussi [en PDF](rapport.pdf) ou [en ligne](http://agreg.uk.is/m/2/rapport.html)) fait sobrement office de rapport pour le second mini projet, demandé pour la préparation à l'agrégation (2013/2014). Le [sujet de ce projet](sujet.html) est là ([en PDF ?](sujet.pdf)). ## Une archive ? Voilà : [Projet2__Lilian_Besson.zip](http://agreg.uk.is/m/2/zip) ## Par [Lilian Besson](http://besson.qc.to/) > J'ai rendu ce projet le vendredi 09 mai, et j'ai eu 17/20 (seconde meilleure note), derrière [Jill-Jênn](http://jill-jenn.net). *** # Dépendances 1. `ocamlc` (et `ocamlopt`) pour construire (avec le module `Sys`) (_v3.12+_ suffit), 2. `GNU/Make` pour constuire le code, 3. `ocamldoc` pour construire la documentation, 4. Éventuellement, [`strapdown2pdf`](http://lbesson.bitbucket.io/md/strapdown2pdf.html) et PDFLaTeX pour la documentation en PDF (par deux étapes `html --> LaTeX --> PDF`). *** # Construire Un `Makefile` est là pour ça, mais ce n'est _testé que sous_ `GNU/Linux` `(X)Ubuntu 14.04` : * `projet` : fait tout, * `dochtml` : fait la doc en html, * `rapport.pdf` : construit la version PDF de cette page, * `euler` : fait le binaire, * `testeuler` : constuire le binaire, et le teste, * `euler.opt` : fait le binaire en natif (plus rapide), * `testeuler.opt` : constuire le binaire en natif, et le teste, * `toplevel` : pour jouer avec le toplevel (avec _rlwrap_ et _ledit_). * `cleanall` : pour nettoyer, * `help` : pour plus d'aide sur le Makefile. *** # Plus d'explications et quelques remarques d'ordre théorique ## Théorèmes « d'Euler » L'intuition derrière ces deux résultats est la suivante : chaque fois qu'un sommet $x$ est traversé par le chemin, son degré augmente de 2 car le cycle **rentre et ressort** : $ \rightarrowtail x \rightarrowtail $ (en non orienté). ### Pour un chemin On va utiliser le théorème suivant, souvent appelé théorème d'Euler. S'il y a un chemin eulérien, si le sommet initial est aussi le sommet d'arrivée, il est de degré pair, comme tous les autres sommets. Par contre s'ils sont distincts, on a deux sommets de degrés impairs qui sont le sommet de départ $u\_{\text{départ}}$ et d'arrivée $u\_{\text{arrivée}}$. > **Il existe un chemin eulérien si et seulement s'il y a 0 ou 2 sommets de degrés impairs.** ### Pour un cycle Et la seconde version est pour l'existence d'un cycle (ou circuit), où l'on impose que le sommet de départ soit le même que le sommet d'arrivée. Ainsi s'il y a un cycle eulérien, chaque sommet a un degré pair. La réciproque étant aussi vraie, on a le second théorème d'Euler : > **Il existe un cycle eulérien si et seulement s'il y a 0 sommets de degrés impairs.** ## À propos de l'algorithme choisi Pour trouver un chemin eulérien, on applique l'algorithme suivant (dû à Rosentielh). > 1. Compter le nombre de sommets de degré impair, 2. Si + c'est 0 : construire un cycle partant du premier sommet (choix arbitraire), + c'est 2 : construire un chemin entre les deux sommets en question, + sinon, il n'y a pas de chemin eulérien (on répond non). 3. parcourir le chemin déjà construit : à chaque sommet + tant qu'il reste des arêtes partant de ce sommet dans le graphe 0. construire un cycle partant de ce sommet 0. puis l'insérer dans le chemin. Étant donné les conditions sur le graphe, construire un chemin ou un cycle n'est pas compliqué : il suffit de partir de l'origine, de prendre la première arête rencontrée et de recommencer récursivement. ## À propos de complexité Si on est capable de retirer une arête (dans les deux sens $x \rightarrowtail y$ et $y \leftarrowtail x$) en un temps $O(1)$, alors l'algorithme retenu, implémenté et testé possède les complexités suivantes : * temporelle (dans le pire des cas) en $O(\max ( |S|, |A|) )$ (mais pas sûr de ça), * spatiale en $O(|G|)$ (mais pas sur place). > Ici est adoptée la convention usuelle de $S$ pour l'ensemble des sommets ($S$ pour *sommet*) et $A$ pour l'ensemble des arêtes ($A$ pour *arête*). ### Est-ce vraiment la complexité obtenue en pratique ? > *En pratique* mon code n'est pas optimisé pour réussir à retirer le sens retour d'une arête ($x \leftarrowtail y$) en un temps constant, mais cela prend un temps $O(|\text{Adj}[y]|)$ soit un temps au pire en $O(|A|)$, à chaque fois, ce qui ferait du $O(|S| |A|)$ à la fin, soit une complexité bien pire que celle annoncée. > Mais une *analyse "par agrégat"*, sommant sur chaque appels à ``suppr`` (il y en a un nombre en $O(1)$ pour chaque sommet de $S$), on constate qu'à la fin on récupère un $O(\sum\_{y \in S} O( |\text{Adj}[y]|) )$ soit donc encore de l'ordre de $O(|A|)$ *à la fin*. Ouf, on a bien le résultat annoncé ! ## Quelques tests Quelques tests sont présents, avec deux graphes eulériens, et avec un graphe non eulérien à 4 sommets. Le premier est le [graphe complet à 3 éléments ($K\_3$)](k3_1.dot), et est eulérien (comme le trouve le programme, avec $K\_3$ défini [ici](doc/code_VALGraph.cst_k3.html)) : <img style="align:center;margin-right:auto;margin-left:auto;display:block;" src="k3_1.png" title="Graphe complet à 3 sommets" alt="Graphe complet à 3 sommets" /> Et le second est un [graphe non complet à 5 sommets ($G\_5$)](g5_2.dot), et est eulérien (comme le trouve le programme, avec $G\_5$ défini [ici](doc/code_VALGraph.cst_g5.html)) : <img style="align:center;margin-right:auto;margin-left:auto;display:block;" src="g5_2.png" title="Graphe non complet à 5 sommets" alt="Graphe non complet à 5 sommets" /> ### Königsberg J'ai aussi pu tester avec le graphe « historique » des [*ponts de Königsberg*](https://fr.wikipedia.org/wiki/Probl%C3%A8me_des_sept_ponts_de_K%C3%B6nigsberg). Voici une carte de la ville (telle qu'elle était en 1735) (*les images suivantes sont issues de Wikipédia, sous licence CC3*) : <img style="align:center;margin-right:auto;margin-left:auto;display:block;" src="konigsberg_1.png" title="Carte de la ville de Königsberg" alt="Carte de la ville de Königsberg" /> Voici un premier schéma, qui montre que pour l'*île du centre* (désormais appelée $a$), **deux** ponts la relient à l'île du haut (appelée $b$) et **deux** ponts la relient à l'île du bas (appelée $c$). <img style="align:center;margin-right:auto;margin-left:auto;display:block;" src="konigsberg_2.png" title="Schéma de la ville de Königsberg" alt="Schéma de la ville de Königsberg" /> Le dessin suivant montre le multi-graphe associé au schéma précédent, dans lequel le sommet $a$ est relié à $b$ (et à $c$) par **deux arcs** sortant. On constate que cet exemple requiert un *multi-graphe* (avec possiblement plusieurs arêtes entre chaque sommets). *Il faut donc ruser un peu.* <img style="align:center;margin-right:auto;margin-left:auto;display:block;" src="konigsberg_3.png" title="Multi-graphe de la ville de Königsberg" alt="Multi-graphe de la ville de Königsberg" /> #### Première ruse Comment ruser ? Une première méthode peut être de dédoubler un sommet ! En fait, il suffit de dédoubler le sommet de gauche ($a$) dans le sens ou au lieu d'avoir deux arêtes parallèles qui pointent vers $b$ (et vers $c$) on a deux sommets $a\_1$ et $a\_2$, avec $a\_1 \rightarrowtail b$ et $a\_2 \rightarrowtail b$ qui sont désormais deux arêtes bien distinces d'un graphe simple. Voici une représentation du graphe tel que [codé en OCaml](doc/code_VALGraph.cst_konisgberg.html), écrit dans un [fichier .dot](Konisgberg_3.dot), et transformé en joli [fichier vectoriel .svg](Konisgberg_3.svg) via [``dot``](http://www.graphviz.org/Download.php). Le graphe numérote les sommets de la façon suivante : $a\_1 = 0$, $b = 1$, $c = 2$, $d = 3$, et le nouveau sommet est $a\_2 = 4$. On vérifie qu'on a bien obtenu ce graphe simple, en dédoublant l'île de gauche, et en gardant relié les deux nouvaux $a\_1$ et $a\_2$ chacun à $b$ et $c$ mais en ne la gardant relié à $d$ (*ie.* à $4$) qu'*une seule fois* (il faut qu'on ait le même nombre d'arête à la fin, pour avoir la même répartition des degrés). <img style="align:center;margin-right:auto;margin-left:auto;display:block;" src="Konisgberg_3.png" title="Graphe simple pour la ville de Königsberg" alt="Graphe simple pour la ville de Königsberg" /> #### Deuxième ruse, plus élégante Une seconde méthode peut être d'ajouter un point de passage artificiel au milieu des deux ponts parallèles, pour en faire des arêtes distinctes. Cette transformation est en fait plus naturelle, et *plus visuelle* (car plus symétrique). Et elle est aussi plus efficace, comme on ne fait qu'ajouter un sommet et une arête à chaque traitement d'un pont parallèle (donc, s'il y a $n$ arêtes multiples de $x$ à $y$, on terminera avec $n-1$ nouveaux sommets $S\_{x,y,i}, i\in{2,\dots,n}$, $n-1$ changements d'arête de la forme $x \rightarrowtail\_{i} y$ en $x \rightarrowtail S\_{x,y,i}$ et $n-1$ ajouts d'arêtes de la forme $S\_{x,y,i} \rightarrowtail y$). Voici une représentation du second graphe tel que [codé en OCaml](doc/code_VALGraph.cst_konisgberg2.html), écrit dans un [fichier .dot](Konisgberg2_1.dot), et transformé en joli [fichier vectoriel .svg](Konisgberg2_1.svg) via [``dot``](http://www.graphviz.org/Download.php). Le graphe numérote les sommets de la façon suivante : $a = 0$, $b = 1$, $c = 2$, $d = 3$, et les nouveaux sommets sont $S\_{a,b,2} = 4$, $S\_{a,c,2} = 5$. <img style="align:center;margin-right:auto;margin-left:auto;display:block;" src="Konisgberg2_1.png" title="Second graphe simple pour la ville de Königsberg" alt="Second graphe simple pour la ville de Königsberg" /> #### Conclusion En conclusion, notons que notre programme parvient bien à reprouver l'impossibilité du chemin (et du cycle) eulérien entre les différentes îles de la ville de Königsberg (un résultat vieux de [279 ans](http://www.wolframalpha.com/input/?i=Time+from+today+to+1735) !), à la fois avec la première ruse et avec la deuxième. ### Tests automatiques (non implémentés) Avec du temps, on aurait pu faire un petit générateur aléatoire de graphe eulérien (ou non) pour automatiser les tests. *Mais la flemme.* ### Comment tester par soi même Pour le tester, il suffit de faire `make testeuler` qui compile et lance le test. On peut aussi exécuter le code du fichier [web.ml](web.html) via ``ocaml web.ml`` ou ``ocaml < web.ml``. *** # Documentation **RTFD** ici [doc](doc/). Aussi en ligne [http://agreg.uk.is/m/2/doc/](http://agreg.uk.is/m/2/doc/). ## Organisation des sources ### Les différents types de données abstraits ![Une capture d'écran d'une animation du projet](dependType.svg "Un diagrame UML montrant les dépendances entre types.") ### Les différents modules (fichiers `.ml`) Les sources peuvent être lues directement ici : [graph.html](graph.html) et [euler.html](euler.html). Ou même en PDF : [graph.pdf](graph.pdf) et [euler.pdf](euler.pdf). ![Une capture d'écran d'une animation du projet](dependModule.svg "Un diagrame UML montrant les dépendances entre modules.") ## Le projet dans votre navigateur ? Le toplevel [try-ocaml][] permet de tester le projet, et même les animations de démonstrations, directement dans votre navigateur. [try-ocaml]: http://besson.qc.to/try-ocaml.html "Toplevel OCaml v4.01 en JavaScript" Il suffit de copier le [code compacté](web.ml) des deux codes `graph.ml` et `euler.ml` et de le coller dans la zone d'édition du toplevel [try-ocaml][], puis de valider avec la touche *Entrée* (ou le bouton `Send`). > Avec plus de temps, on pourrait faire une démo *trop classe* avec juste un bouton "Go!" (et un peu de JavaScript derrière) pour pouvoir tout tester dans un navigateur. ## Licence ? Distribués sous les termes de la [**Licence GPLv3**](http://besson.qc.to/LICENSE.html). Les trois images de la ville de Königsberg viennent de Wikipédia, et sont distribués sous Licence Creative Commons. ## Dernière remarque Pour toute question, signalement de bug, ou autre : 1. par courriel, `Lilian(.)Besson(@)ens-cachan(.)fr`, 2. ou [`bitbucket.org/lbesson/agreg/issues/new`](https://bitbucket.org/lbesson/agreg/issues/new) en ligne via Bitbucket ! GA|Analytics