{"cells":[{"metadata":{},"cell_type":"markdown","source":"![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)\n\n\n<i>© Copyright Franck CHEVRIER 2019-2023 https://www.python-lycee.com.</i><br>\n<i>Les activités partagées sur <a href=\"https://capytale2.ac-paris.fr/web/accueil\"><strong>Capytale</strong></a> sont sous licence <a href=\"https://creativecommons.org/licenses/by-sa/3.0/fr/\">Creative Commons</a>.</i>\n\n<span style=\"color: #9317B4\"> Pour exécuter une saisie Python, sélectionner la cellule et valider avec </span><span style=\"color: #B317B4\"><strong>SHIFT+Entrée</strong></span>.\n"},{"metadata":{},"cell_type":"markdown","source":"<h1 style=\"color:#02731C; font-size:44px\">Graphes et trajets eulériens <span style=\"color:red;\">(Corrigé)</span></h1>\n"},{"metadata":{"trusted":true},"cell_type":"markdown","source":"<a href=\"https://github.com/PythonLycee/PyLyc/blob/850b40608587b00efd142d571f6b1c004be979de/Annexes/Doc_accompagnement_graphes.pdf\"><figure style=\"width:50px; float:right\" title=\"Fichier imprimable à télécharger\">\n    <img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/pdf_telech.png\">\n    <figcaption style=\"text-align: center; font-size: 10px;\">Figures <br>et tableaux</figcaption>\n</figure></a>\n\n### <span style=\"color:#58A76A\">Sommaire</span>\n\n<span style=\"color:#222222\">1.</span> <a href=\"#1\">Première approche des graphes</a><br>\n<span style=\"color:#222222\">2.</span> <a href=\"#2\">Parcours dans un graphe et ponts de Kœnigsberg</a><br>\n<span style=\"color:#222222\">3.</span> <a href=\"#3\">Annexes</a><br>\n"},{"metadata":{},"cell_type":"markdown","source":"<span id=\"1\"></span>\n<h3 style=\"color:#02731C; font-size:28px\">1. Première approche des graphes</h3>"},{"metadata":{},"cell_type":"markdown","source":"<strong>1.1. Suivre la vidéo suivante, qui introduit la notion de graphe et le vocabulaire associé.</strong>\n<br><br>\n$\\quad\\;$En complément, si nécessaire, vous trouverez également un <a href=\"#3.1.\">lexique</a> dans les annexes de l'activité.\n<br><br>\n<video controls src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/video/Video_intro_graphe.mp4\" width=\"960\" height=\"540\" />"},{"metadata":{},"cell_type":"markdown","source":"<span title=\"essai info bulle\">bla</span>"},{"metadata":{},"cell_type":"markdown","source":"<strong>1.2. On considère les 10 graphes ci-dessous.<br>\n$\\quad\\;\\;$Compléter le tableau avec les valeurs qui conviennent.</strong>\n<br><br>\n$\\quad\\;\\;$Aide : Le graphe $\\text{G}_1$ est celui qui est traité en exemple dans la vidéo précédente."},{"metadata":{},"cell_type":"markdown","source":"\n<img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Graphes.png\">\n\n    \n<table style=\"border-collapse:collapse;border-spacing:0;table-layout: fixed; width: 758px\" class=\"tg\"><colgroup><col style=\"width: 128px\"><col style=\"width: 98px\"><col style=\"width: 101px\"><col style=\"width: 96px\"><col style=\"width: 166px\"><col style=\"width: 169px\"></colgroup><thead><tr><th style=\"background-color:#DBFCE3;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Graphe</th><th style=\"background-color:#DBFCE3;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\"><span style=\"font-weight:bold\">Connexe ?</span><br><span style=\"font-weight:bold\">(oui/non)</span></th><th style=\"background-color:#DBFCE3;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Complet ?<br>(oui/non)</th><th style=\"background-color:#DBFCE3;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Ordre du <br>graphe</th><th style=\"background-color:#DBFCE3;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Somme des degrés<br> des sommets</th><th style=\"background-color:#DBFCE3;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Nombre d'arêtes <br>du graphe</th></tr></thead><tbody><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{1}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{2}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{3}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{4}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{5}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{6}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{7}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{8}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{9}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{10}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr></tbody></table>\n\n"},{"metadata":{},"cell_type":"markdown","source":"\n<table style=\"border-collapse:collapse;border-spacing:0;table-layout: fixed; width: 758px\" class=\"tg\"><colgroup><col style=\"width: 128px\"><col style=\"width: 98px\"><col style=\"width: 101px\"><col style=\"width: 96px\"><col style=\"width: 166px\"><col style=\"width: 169px\"></colgroup><thead><tr><th style=\"background-color:#FDBAB6;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Graphe</th><th style=\"background-color:#FDBAB6;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\"><span style=\"font-weight:bold\">Connexe ?</span><br><span style=\"font-weight:bold\">(oui/non)</span></th><th style=\"background-color:#FDBAB6;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Complet ?<br>(oui/non)</th><th style=\"background-color:#FDBAB6;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Ordre du <br>graphe</th><th style=\"background-color:#FDBAB6;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Somme des degrés<br> des sommets</th><th style=\"background-color:#FDBAB6;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Nombre d'arêtes <br>du graphe</th></tr></thead><tbody><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{1}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">5</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">14</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">7</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{2}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">5</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">10</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">5</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{3}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">4</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">8</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">4</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{4}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">5</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">16</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">8</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{5}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">6</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">12</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">6</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{6}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">4</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">10</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">5</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{7}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">5</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">12</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">6</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{8}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">6</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">16</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">8</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{9}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">5</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">12</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">6</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{10}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">4</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">12</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">6</td></tr></tbody></table>"},{"metadata":{},"cell_type":"markdown","source":"<strong>1.3.a. Quel lien peut-on conjecturer entre la somme des degrés des sommets et le nombre d'arêtes du graphe ?<br><br>\n$\\quad\\;$b. Justifier que cette conjecture est correcte.<br><br>\n$\\quad\\;$c. Un graphe peut-il avoir un nombre impair de sommets de degrés impairs ?</strong>\n\n<br><br>\n<span style=\"color:red;\">\na. La somme des degrés des sommets semble être égal au double du nombre d'arêtes du graphe.<br><br>\nb. Lorsqu'on somme tous les degrés des sommets, cela revient à compter les arêtes du graphe mais celles-ci sont comptées deux fois car chaque arête a deux extrémités. D'où le résultat.<br><br>\nc. Si un graphe avait un nombre impair de sommets de degrés impairs, la somme des degrés des sommets serait alors impair. C'est absurde puisque, étant égal au double du nombre d'arêtes du graphe, ce nombre doit être pair.\n</span>\n"},{"metadata":{},"cell_type":"markdown","source":"<strong>1.4. Une application :<br>\n<BLOCKQUOTE style=\"background-color:#DBFCE3;\">   \n<img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/poignee_main.png\" style=\"float: right; width:150px;\">\nÀ une réception, 42 personnes se retrouvent.<br>\nChaque convive serre la main de chacun des autres convives.<br><br>\nCombien de poignées de main sont échangées en tout ?\n</BLOCKQUOTE>\n</strong>\n\n<br><br>\n<span style=\"color:red;\">\nOn peut modéliser la situation à l'aide d'un graphe où chaque sommet représente un convive et chaque arête représente une poignée de main échangée. Comme chacun des $42$ convives serre la main des $41$ autres, chacun des sommets est de degré $41$. Il en résulte que la somme des degrés des sommets vaut $42\\times41=1722$, qui est donc aussi le double du nombre d'arête. Au final, il y a $861$ poignées de main échangées.\n</span>"},{"metadata":{},"cell_type":"markdown","source":"<span id=\"2\"></span>\n<h3 style=\"color:#02731C; font-size:28px\">2. Parcours dans un graphe et ponts de Kœnigsberg</h3>"},{"metadata":{},"cell_type":"markdown","source":"<strong>2.1. Suivre la vidéo suivante, qui introduit les notions de chaînes et de cycles eulériens.</strong>\n<br><br>\n<video controls src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/video/Video_parcours_graphe.mp4\" width=\"960\" height=\"540\" />"},{"metadata":{},"cell_type":"markdown","source":"<strong>2.2. On reprend les 10 graphes étudiés dans la partie 1, rappelés ci-dessous.<br>\n$\\quad\\;\\;$Compléter le tableau avec les valeurs qui conviennent.</strong>\n"},{"metadata":{},"cell_type":"markdown","source":"\n<img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Graphes.png\">\n\n<table style=\"border-collapse:collapse;border-spacing:0;table-layout: fixed; width: 719px\" class=\"tg\"><colgroup><col style=\"width: 124px\"><col style=\"width: 95px\"><col style=\"width: 175px\"><col style=\"width: 161px\"><col style=\"width: 164px\"></colgroup><thead><tr><th style=\"background-color:#DBFCE3;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Graphe</th><th style=\"background-color:#DBFCE3;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\"><span style=\"font-weight:bold\">Connexe ?</span><br><span style=\"font-weight:bold\">(oui/non)</span></th><th style=\"background-color:#DBFCE3;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Nombre de sommets de degrés impairs</th><th style=\"background-color:#DBFCE3;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Existence d'une chaîne eulérienne ?<br>(oui/non)</th><th style=\"background-color:#DBFCE3;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Existence d'un cycle eulérien ?<br>(oui/non)</th></tr></thead><tbody><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{1}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{2}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{3}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{4}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{5}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{6}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{7}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{8}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{9}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr><tr><td style=\"background-color:#EEFFF2;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{10}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"></td></tr></tbody></table>"},{"metadata":{},"cell_type":"markdown","source":"\n<table style=\"border-collapse:collapse;border-spacing:0;table-layout: fixed; width: 719px\" class=\"tg\"><colgroup><col style=\"width: 124px\"><col style=\"width: 95px\"><col style=\"width: 175px\"><col style=\"width: 161px\"><col style=\"width: 164px\"></colgroup><thead><tr><th style=\"background-color:#FDBAB6;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Graphe</th><th style=\"background-color:#FDBAB6;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\"><span style=\"font-weight:bold\">Connexe ?</span><br><span style=\"font-weight:bold\">(oui/non)</span></th><th style=\"background-color:#FDBAB6;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Nombre de sommets de degrés impairs</th><th style=\"background-color:#FDBAB6;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Existence d'une chaîne eulérienne ?<br>(oui/non)</th><th style=\"background-color:#FDBAB6;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Existence d'un cycle eulérien ?<br>(oui/non)</th></tr></thead><tbody><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{1}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">2</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{2}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">0</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{3}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">0</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{4}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">4</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{5}$</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">0</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{6}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">2</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{7}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">2</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{8}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">0</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{9}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">2</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td></tr><tr><td style=\"background-color:#FFD6D4;border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">$\\text{G}_{10}$</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">oui</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">4</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td><td style=\"border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\">non</td></tr></tbody></table>"},{"metadata":{},"cell_type":"markdown","source":"<strong>2.3. Quelle règle peut-on conjecturer pour déterminer de l'existence ou non d'une chaîne ou d'un cycle eulérien ?<br>\n$\\quad\\;\\;$Une fois votre conjecture faite, cliquez sur la zone ci-dessous pour obtenir l'énoncé du théorème d'Euler.</strong>"},{"metadata":{"deletable":false,"editable":false},"cell_type":"markdown","source":"<details>\n    <summary style=\"cursor: pointer; background:#48B662; color:#FFFFFF;\"><center><strong><br>Cliquer pour voir le théorème d'Euler<br><br></strong></center></summary>\n    <BLOCKQUOTE style=\"background-color:#EEFFF2\">\n    <strong>Théorème d'Euler</strong>\n    <ul>\n        <li>Un graphe connexe non orienté admet une <strong>chaîne eulérienne</strong> si et seulement si le nombre de sommets de degrés impairs de ce graphe vaut 0 ou 2.<br>Dans le cas où il y a deux sommets de degrés impairs, ces sommets sont les extrémités de la chaîne eulérienne.<br><br></li>\n        <li>Un graphe connexe non orienté admet un <strong>cycle eulérien</strong> si et seulement si tous ses sommets sont de degrés pairs.</li>\n    </ul><br>\n    </BLOCKQUOTE>\n</details>  "},{"metadata":{},"cell_type":"markdown","source":"<br><br><strong>2.4. Automatisation de la recherche de chaines et cycles eulériens.<br><br>\n\na. La structure Python <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">G1</mark> ci-dessous permet de modéliser le graphe $\\text{G}_1$ vu précédemment. Expliquer brièvement comment sont codées les informations du graphe dans cette structure. </strong>\n<br><br>\nAvant de continuer, exécuter cette cellule pour mettre ce graphe en mémoire.\n\n<br><br>\n<span style=\"color:red;\">\nDans la structure G1, on associe à chaque sommet la liste des sommets qui lui sont reliés par une arête.\n</span>"},{"metadata":{"trusted":true},"cell_type":"code","source":"# exécuter cette cellule\n\nG1 = {  'A':['C','D','E'],\n        'B':['D','E'],\n        'C':['A','D'],\n        'D':['A','B','C','E'],\n        'E':['A','B','D']\n     }","execution_count":1,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"<strong>b. On fournit ici des fonctions Python <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">est_complet</mark>, <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">est_connexe</mark>, <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">non_oriente</mark> et <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">algo_euler</mark> permettant respectivement de déterminer si un graphe est complet, s'il est connexe, s'il est non orienté et s'il est eulérien (et si oui, on obtient une chaîne ou un cycle eulérien).<br><br>\nExécuter ces cellules et vérifier qu'on retrouve les résultats obtenus précédemment pour $\\text{G}_1$.</strong>"},{"metadata":{"trusted":true},"cell_type":"code","source":"# exécuter cette cellule\n\nfrom random import choice\nfrom copy import deepcopy\n\ndef est_complet(G):\n    \"\"\"\n    fonction qui indique si le graphe G est complet\n    \"\"\"\n    for S0 in G:\n        for S in G:\n            # s'il existe deux sommets non reliés, le graphe n'est pas complet\n            if S!=S0 and S not in G[S0]: return False\n    return True\n    \ndef est_connexe(G,S0=None,atteint=None,profondeur=0):\n    \"\"\"\n    fonction qui indique si le graphe G est connexe\n    \"\"\"\n    if not atteint: atteint=[]\n    #si on a atteint tous les sommets, le graphe est connexe\n    if len(atteint)==len(G): return True\n    #si on a effectué suffisamment profonde et qu'on n'a pas atteint tous les sommets, il n'est pas connexe\n    if profondeur>=len(G): return False\n    #on choisit un sommet de départ\n    if not S0: \n        S0 = choice([S for S in G])\n        atteint.append(S0)\n        profondeur+=1\n    #pour chaque sommet déjà atteint, on complète la liste avec les sommets que l'on peut atteindre\n    for S in atteint:\n        for adj in G[S]:\n            if adj not in atteint: atteint.append(adj)\n    return est_connexe(G,S0,atteint,profondeur+1)      \n\ndef non_oriente(G):\n    for S0 in G:\n        for S in G[S0]: \n            #s'il existe une arête non réciproque, le graphe est orienté\n            if S0 not in G[S]: return False\n    return True\n\ndef algo_euler(G):\n    G=deepcopy(G)\n    \n    #si le graphe est orienté, arrêt de l'algorithme\n    if not non_oriente(G): \n        print(\"Arrêt. Le graphe soumis est un graphe orienté.\")\n        return None\n    #si le graphe n'est pas connexe, il n'est pas eulérien\n    if not est_connexe(G): \n        print(\"Le graphe n'est pas connexe, donc il n'y a ni chaîne ni cycle eulérien.\")\n        return None\n    #calcul du nombre de sommets de degrés impairs\n    sommets_deg_impair=[S for S in G if len(G[S])%2==1]\n    nb_som_deg_imp=len(sommets_deg_impair)\n    \n    #choix des sommets de départ et d'arrivée si G admet une chaine eulérienne et arrêt sinon\n    if nb_som_deg_imp== 0:\n        Debut=Fin=[S for S in G].pop(0)\n    elif nb_som_deg_imp== 2:\n        Debut=sommets_deg_impair.pop(0)\n        Fin=sommets_deg_impair.pop(0)\n    else:\n        print(\"Le graphe a \"+str(nb_som_deg_imp)+\" sommets de degrés impairs, donc il n'y a ni chaîne ni cycle eulérien.\")\n        return None\n   \n    #détermination du nombre de sommets de la chaine à construire\n    longueur_chaine_euler = sum([len(G[S]) for S in G])//2+1\n        \n    #contruction d'une chaine quelconque reliant Debut à Fin\n    chaine=[Debut]\n    while chaine[-1]!=Fin:\n        suiv=choice(G[chaine[-1]])\n        G[chaine[-1]].remove(suiv)\n        G[suiv].remove(chaine[-1])\n        chaine.append(suiv)\n        \n    #tant que la chaine construite n'emprunte pas toutes les arêtes\n    while len(chaine)<longueur_chaine_euler:\n        #choix d'un début de cycle à insérer à partir d'un sommet de la chaine\n        deb_cycl=choice([S for S in chaine if G[S]!=[]])\n        #construction du cycle\n        cycl=[deb_cycl]\n        while cycl[-1]!=deb_cycl or len(cycl)<2:\n            suiv=choice(G[cycl[-1]])\n            G[cycl[-1]].remove(suiv)\n            G[suiv].remove(cycl[-1])\n            cycl.append(suiv)\n        #insertion du cycle dans la chaîne\n        rang_insert=chaine.index(deb_cycl)\n        chaine = chaine[:rang_insert]+cycl+chaine[rang_insert+1:]\n        \n    print(\"Le graphe admet un\"+(\" cycle eulérien\" if nb_som_deg_imp== 0 else \"e chaine eulérienne\")+\".\\nExemple:\")\n    return chaine","execution_count":2,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# exécuter cette cellule\nest_complet(G1)","execution_count":3,"outputs":[{"output_type":"execute_result","execution_count":3,"data":{"text/plain":"False"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"# exécuter cette cellule\nest_connexe(G1)","execution_count":4,"outputs":[{"output_type":"execute_result","execution_count":4,"data":{"text/plain":"True"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"# exécuter cette cellule\nnon_oriente(G1)","execution_count":5,"outputs":[{"output_type":"execute_result","execution_count":5,"data":{"text/plain":"True"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"# exécuter cette cellule\nalgo_euler(G1)","execution_count":6,"outputs":[{"output_type":"stream","text":"Le graphe admet une chaine eulérienne.\nExemple:\n","name":"stdout"},{"output_type":"execute_result","execution_count":6,"data":{"text/plain":"['A', 'E', 'B', 'D', 'C', 'A', 'D', 'E']"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"<strong>c. Effectuer les saisies nécessaires pour modéliser quelques autres graphes parmi ceux étudiés précédemment. Effectuer ensuite des saisies pour vérifier les résultats du tableau de la question 2.2.</strong>\n<br><br>\nAide : On pourra commencer par effectuer un copier/coller de la structure <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">G1</mark> fournie précédemment."},{"metadata":{"trusted":true},"cell_type":"code","source":"# Utiliser ces cellules pour effectuer les saisies\n\n# Saisies pour G8\n\nG8 = {  'A':['B','E'],\n        'B':['A','C','D','F'],\n        'C':['B','E'],\n        'D':['B','E'],\n        'E':['A','C','D','F'],\n        'F':['B','E']\n     }","execution_count":7,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"est_complet(G8)","execution_count":8,"outputs":[{"output_type":"execute_result","execution_count":8,"data":{"text/plain":"False"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"est_connexe(G8)","execution_count":9,"outputs":[{"output_type":"execute_result","execution_count":9,"data":{"text/plain":"True"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"non_oriente(G8)","execution_count":10,"outputs":[{"output_type":"execute_result","execution_count":10,"data":{"text/plain":"True"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"algo_euler(G8)","execution_count":11,"outputs":[{"output_type":"stream","text":"Le graphe admet un cycle eulérien.\nExemple:\n","name":"stdout"},{"output_type":"execute_result","execution_count":11,"data":{"text/plain":"['A', 'B', 'F', 'E', 'D', 'B', 'C', 'E', 'A']"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"<br><br><br><strong>2.5. Une application :</strong><br>\n\nDans son mémoire <a href=\"https://scholarlycommons.pacific.edu/cgi/viewcontent.cgi?article=1052&context=euler-works\">Solutio problematis ad geometriam situs pertinentis</a>, publié en 1741, <a href=\"https://fr.wikipedia.org/wiki/Leonhard_Euler\">Leonhard Euler</a> décrit un problème qui deviendra célèbre sous le nom de \"problème des 7 ponts de Kœnigsberg\", et considéré comme étant à l'origine de la théorie des graphes.<br><br>\nVoici ci-dessous un extrait de cet ouvrage et <a href=\"https://www.cantab.net/users/michael.behrend/repubs/maze_maths/pages/lucas_ch2.html\">sa traduction</a> :\n"},{"metadata":{},"cell_type":"markdown","source":"\n<table style=\"border-collapse:collapse;border-spacing:0;table-layout: fixed; width: 919px\" class=\"tg\"><colgroup><col style=\"width: 118px\"><col style=\"width: 801px\"></colgroup><thead><tr><th style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Extrait du <br>texte<br>original</th><th style=\"background-color:#ffffff;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"><img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Mémoire_Euler.png\"></th></tr></thead><tbody><tr><td style=\"background-color:#EEFFF2;border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;font-weight:bold;overflow:hidden;padding:10px 5px;text-align:center;vertical-align:top;word-break:normal\">Traduction</td><td style=\"border-color:inherit;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;overflow:hidden;padding:10px 5px;text-align:left;vertical-align:top;word-break:normal\"><ol>\n    <li> Outre cette partie de la Géométrie qui s’occupe de la grandeur et de la mesure, et qui a été cultivée dès les temps les plus reculés, avec une grande application, Leibniz a fait mention, pour la première fois, d’une autre partie encore très inconnue actuellement, qu’il a appelée Geometria situs. D’après lui, cette branche de la science s’occupe uniquement de l’ordre et de la situation, indépendamment des rapports de grandeur. Mais quels sont les problèmes qui appartiennent à cette géométrie; quelles sont les méthodes qu’il faut employer a leur résolution ? C’est ce qui n’a pas encore été nettement défini. Récemment j’ai entendu parler d’un problème qui paraît se rapporter à la Géométrie de situation, puisqu’il ne contient, dans son énoncé, que des considérations d’ordre et non de mesure; aussi ai-je résolu d’exposer ici, comme un spécimen, la méthode que j’ai trouvée pour résoudre ce problème.<br><br></li>\n    <li><span style=\"background-color:#BAEEC7\">À Kœnigsberg, en Poméranie, il y a une île appelée Kneiphof ; le fleuve qui l’entoure se divise en deux bras (fig. 1), sur lesquels sont jetés les sept ponts a, b, c, d, e, f, g. Cela posé, peut-on arranger son parcours de telle sorte que l’on passe sur chaque pont, et, que l’on ne puisse y passer qu’une seule fois ? Cela semble possible, disent les uns ; impossible, disent les autres; cependant personne n’a la certitude de son sentiment.</span><br>\nJe me suis donc proposé le problème suivant, qui est très général :<br>\nQuelle que soit la forme d’un fleuve, sa distribution en bras, par des îles en nombre quelconque, et quel que soit le nombre des ponts jetés sur le fleuve, trouver si l’on peut franchir celui-ci en passant une fois, et une seule, sur chacun des ponts.\n    </li>\n</ol></td></tr></tbody></table>"},{"metadata":{},"cell_type":"markdown","source":"<img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Sept_ponts_Koenigsberg.gif\" style=\"float:right; width:270px\">\n\n<strong>a. Répondre à la question posée par Euler concernant la situation des 7 ponts de Kœnigsberg (fig. 1):<br><br>\n$\\;\\;\\;$Est-il possible d'effectuer un trajet qui emprunte chaque pont une et une seule fois ?\n<br><br><br>\nb. De la même façon que dans la question 1.4, créer une structure Python <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">E1</mark> permettant de modéliser le graphe correspondant à la situation des 7 ponts de Kœnigsberg. Effectuer ensuite un appel à la fonction <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">algo_euler</mark> pour vérifier la réponse précédente.</strong>\n<br><br>\nAides : \n<ul>\n    <li>On pourra commencer par effectuer un copier/coller de la structure <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">G1</mark> fournie précédemment.</li>\n    <li>Lorsqu'il existe plusieurs arêtes reliant deux sommets, il faut les saisir plusieurs fois dans la structure Python.</li>\n</ul>\n\n<br><br>\n<span style=\"color:red;\">\nLe graphe qui modélise la situation possède 4 sommets de degrés impairs, donc d'après le théorème d'Euler il n'existe ni chaîne ni cycle eulérien. On ne peut pas efectuer de trajet qui emprunte chaque pont une et une seule fois.\n</span>"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Créer ici la structure E1 correspondant à la situation des 7 ponts de Koenigsberg\nE1 = { \n    'A':['B','B','C','C','D'],\n    'B':['A','A','D'],\n    'C':['A','A','D'],\n    'D':['A','B','C']\n    }","execution_count":12,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Effectuer ici un appel à la fonction algo_euler\nalgo_euler(E1)","execution_count":13,"outputs":[{"output_type":"stream","text":"Le graphe a 4 sommets de degrés impairs, donc il n'y a ni chaîne ni cycle eulérien.\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"<strong>c. Dans son mémoire, Euler propose deux autres situations, réprésentées sur les figures ci-dessous (fig. 2 et fig. 3).<br>\n$\\quad$Indiquer, pour chaque situation, s'il est possible d'effectuer un trajet qui emprunte chaque pont une et une seule fois.</strong>\n<img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Graphe_autres.png\">\n\n<span style=\"color:red;\">\nPour la figure 2, les deux sommets du graphe sont de degrés pairs, donc il existe un cycle eulérien.<br>\nPour la figure 3, il y a deux sommets de degrés impairs, donc il existe une chaîne eulérienne.\n</span>"},{"metadata":{},"cell_type":"markdown","source":"<strong>d. Créer des structures Python <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">E2</mark> et <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">E3</mark> permettant de modéliser les graphes correspondant aux situations représentées ci-dessus (fig. 2 et fig. 3). Effectuer ensuite des appels à la fonction <mark style=\"font-family: Consolas; background-color:#EEFFF2;\">algo_euler</mark> pour vérifier vos réponses précédentes.</strong>\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Créer ici la structure E2 \nE2 = { \n    'A':['B','B','B','B','B','B'],\n    'B':['A','A','A','A','A','A']\n    }","execution_count":14,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Effectuer ici un appel à la fonction algo_euler\nalgo_euler(E2)","execution_count":15,"outputs":[{"output_type":"stream","text":"Le graphe admet un cycle eulérien.\nExemple:\n","name":"stdout"},{"output_type":"execute_result","execution_count":15,"data":{"text/plain":"['A', 'B', 'A', 'B', 'A', 'B', 'A']"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Créer ici la structure E3\nE3 = { \n    'A':['B','C','C','D','E','E','F','F'],\n    'B':['A','E','F','F'],\n    'C':['A','A','D','F'],\n    'D':['A','C','E'],\n    'E':['A','A','B','D','F'],\n    'F':['A','A','B','B','C','E']\n    }","execution_count":16,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Effectuer ici un appel à la fonction algo_euler\nalgo_euler(E3)","execution_count":17,"outputs":[{"output_type":"stream","text":"Le graphe admet une chaine eulérienne.\nExemple:\n","name":"stdout"},{"output_type":"execute_result","execution_count":17,"data":{"text/plain":"['D', 'E', 'F', 'C', 'D', 'A', 'F', 'B', 'A', 'C', 'A', 'E', 'A', 'F', 'B', 'E']"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"<span id=\"3\"></span>\n<h3 style=\"color:#02731C; font-size:28px\">3. Annexes</h3>"},{"metadata":{},"cell_type":"markdown","source":"<span id=\"3.1.\"></span>\n<strong>3.1. Lexique</strong>"},{"metadata":{},"cell_type":"markdown","source":"<BLOCKQUOTE style=\"background-color:#EEFFF2;\">\n<ol>\n    <li><strong>Graphes et sommets</strong>\n        <ul>\n            <li>Un <strong>graphe</strong> est composé :\n                <ul>\n                    <li>de sommets ;</li>\n                    <li>d'arêtes qui relient ces sommets.</li>\n                </ul>\n            </li>\n            <li>L'<strong>ordre</strong> d'un graphe est le nombre de sommets de ce graphe.</li>\n            <li>Le <strong>degré</strong> d'un sommet est le nombre de fois qu'il apparaît comme extrémité d'une arête.</li>\n            <li>Deux sommets sont dits <strong>adjacents</strong> s'ils sont reliés par une arête.</li>\n        </ul>\n    <br></li>\n    <li><strong>Structure de graphes</strong>\n        <ul>\n            <li>Un graphe est dit <strong>connexe</strong> si n'importe lesquels de ses sommets sont reliés par une chaîne.</li>\n            <li>Un graphe est dit <strong>complet</strong> si deux quelqconques de ses sommets sont tous adjacents.</li>\n        </ul>\n    <br></li>\n    <li><strong>Chaînes et cycles</strong>\n        <ul>\n            <li>Une <strong>chaîne</strong> est une suite quelconque d'arêtes du graphe.</li>\n            <li>La <strong>longueur</strong> d'une chaîne est le nombre d'arêtes qui la compose.</li>\n            <li>Une chaîne est dite <strong>fermée</strong> si ses deux extrémités sont confondues.</li>\n            <li>Un <strong>cycle</strong> est une chaîne fermée composée d'arêtes toutes distinctes.</li>\n        </ul>    \n    <br></li>\n    <li><strong>Problème d'Euler</strong>\n        <ul>\n            <li>Une chaîne est dite <strong>eulérienne</strong> si elle parcourt <u>toutes</u> les arêtes du graphe <u>une seule fois</u>.</li>\n            <li>Un cycle est dit <strong>eulérien</strong> s'il parcourt <u>toutes</u> les arêtes du graphe <u>une seule fois</u>.</li>\n            <li>Un graphe est dit <strong>eulérien</strong> s'il admet un cycle eulérien.</li>\n        </ul>\n    </li>\n</ol>\n</BLOCKQUOTE>"},{"metadata":{},"cell_type":"markdown","source":"<strong>3.2. Kœnigsberg aujourd'hui</strong>\n<br><br>\nLa ville de <a href=\"https://fr.wikipedia.org/wiki/K%C3%B6nigsberg\">Kœnigsberg (ou Königsberg)</a> se nomme aujourd'hui <a href=\"https://fr.wikipedia.org/wiki/Kaliningrad\">Kaliningrad</a>, et est située dans l'<a href=\"https://fr.wikipedia.org/wiki/Oblast_de_Kaliningrad\">oblast russe de Kaliningrad</a>.\n<br>\nVous pouvez exécuter la cellule ci-dessous pour obtenir une carte interactive représentant le centre de Kaliningrad. On remarquera que la disposition des ponts n'est plus la même qu'à l'époque où Euler a écrit son mémoire."},{"metadata":{"trusted":true},"cell_type":"code","source":"# Exécuter cette cellule pour obtenir la figure dynamique\nfrom IPython.display import HTML ; HTML(\"\"\"<iframe src=\"https://www.google.com/maps/embed?pb=!1m14!1m12!1m3!1d4610.1784389459735!2d20.5085608355321!3d54.70805343977486!2m3!1f0!2f0!3f0!3m2!1i1024!2i768!4f13.1!5e0!3m2!1sfr!2sfr!4v1686260755573!5m2!1sfr!2sfr\" width=\"800\" height=\"600\" style=\"border:0;\" allowfullscreen=\"\" loading=\"lazy\" referrerpolicy=\"no-referrer-when-downgrade\"></iframe>\"\"\")","execution_count":18,"outputs":[{"output_type":"execute_result","execution_count":18,"data":{"text/plain":"<IPython.display.HTML object at 0xe11798>","text/html":"<iframe src=\"https://www.google.com/maps/embed?pb=!1m14!1m12!1m3!1d4610.1784389459735!2d20.5085608355321!3d54.70805343977486!2m3!1f0!2f0!3f0!3m2!1i1024!2i768!4f13.1!5e0!3m2!1sfr!2sfr!4v1686260755573!5m2!1sfr!2sfr\" width=\"800\" height=\"600\" style=\"border:0;\" allowfullscreen=\"\" loading=\"lazy\" referrerpolicy=\"no-referrer-when-downgrade\"></iframe>"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"<center><BLOCKQUOTE style=\"background-color:#EEFFF2;\">\n<figure style=\"max-width:50%;\">\n    <img src=\"https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Leonhard_Euler.jpg\">\n    <figcaption style=\"text-align: center; font-size: 10px;\"><a href=\"https://fr.wikipedia.org/wiki/Leonhard_Euler\">Leonhard Euler</a> (1707-1783) est considéré comme le fondateur de la théorie des graphes</figcaption>\n</figure>\n</BLOCKQUOTE></center>\n"},{"metadata":{},"cell_type":"markdown","source":"<i>© Copyright Franck CHEVRIER 2019-2023 https://www.python-lycee.com.</i><br>\n<i>Les activités partagées sur <a href=\"https://capytale2.ac-paris.fr/web/accueil\"><strong>Capytale</strong></a> sont sous licence <a href=\"https://creativecommons.org/licenses/by-sa/3.0/fr/\">Creative Commons</a>.</i>\n<br><br>\n<span style=\"font-size:8px\">Dernière modification de l'activité : Juin 2023</span>"}],"metadata":{"celltoolbar":"Éditer les Méta-Données","kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"nbformat":4,"nbformat_minor":2}