correction_LesGraphes_2020.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5Tv2duaSSfZH"
   },
   "source": [
    "# **Structure de données : Les Graphes**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7juWKUJESj-u"
   },
   "source": [
    "## **1. Exemple de la représentation d'un réseau social**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "c8hI5lvBTHet"
   },
   "source": [
    " Imaginez un réseau social ayant 6 abonnés (A, B, C, D, E et F) où :\n",
    "\n",
    "    A est ami avec B, C et D\n",
    "    B est ami avec A et D\n",
    "    C est ami avec A, E et D\n",
    "    D est ami avec tous les autres abonnés\n",
    "    E est ami avec C, D et F\n",
    "    F est ami avec E et D\n",
    "\n",
    "La description de ce réseau social, malgré son faible nombre d'abonnés, est déjà quelque peu rébarbative, alors imaginez cette même description avec un réseau social comportant des millions d'abonnés !\n",
    "\n",
    "Il existe un moyen plus \"visuel\" pour représenter ce réseau social : on peut représenter chaque abonné par un cercle (avec le nom de l'abonné situé dans le cercle) et chaque relation \"X est ami avec Y\" par un segment de droite reliant X et Y (\"X est ami avec Y\" et \"Y est ami avec X\" étant représenté par le même segment de droite).\n",
    "\n",
    "Voici ce que cela donne avec le réseau social décrit ci-dessus "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "KRypp_05UTlU"
   },
   "source": [
    "<img src=\"https://pixees.fr/informatiquelycee/n_site/img/graphe.png\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "IrKoKyC7Yzz_"
   },
   "source": [
    " Ce genre de figure s'appelle un graphe. Les graphes sont des objets mathématiques très utilisés, notamment en informatique.\n",
    "\n",
    "- Les cercles sont appelés des sommets\n",
    "- Les segments de droites qui relient 2 sommets sont appelés relations\n",
    "\n",
    "Plus formellement on dira qu'un graphe G est un couple G = (V,E) avec V un ensemble de sommets et E un ensemble de relations "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "IdrNStW1Y_f2"
   },
   "source": [
    "**Exercice :**\n",
    "\n",
    "\n",
    "\n",
    "Construisez un graphe de réseau social à partir des informations suivantes :\n",
    "\n",
    "    A est ami avec B et E\n",
    "    B est ami avec A et C\n",
    "    C est ami avec B,F et D\n",
    "    D est ami avec C,F et E\n",
    "    E est ami avec A,D et F\n",
    "    F est ami avec C, D et E\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Nq8s07fJZEzg"
   },
   "source": [
    "## **2. Exemple en cartographie**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "cKlCNLQ7ZS6f"
   },
   "source": [
    "Autre utilisation possible des graphes : les logiciels de cartographie (ces logiciels sont souvent utilisés couplés à des récepteurs GPS). Ces logiciels de cartographie permettant, connaissant votre position grâce à un récepteur GPS, d'indiquer la route à suivre pour se rendre à endroit B. Comment modéliser l'ensemble des lieux et des routes ? Simplement à l'aide d'un graphe ! Chaque lieu est un sommet et les routes qui relient les lieux entre eux sont des arêtes. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "cbkag0OhZlhN"
   },
   "source": [
    "### **2.1 Graphe non orienté**\n",
    "\n",
    "\n",
    "\n",
    "Soit les lieux suivants : A, B, C, D, E, F et G.\n",
    "\n",
    "Les différents lieux sont reliés par les routes suivantes :\n",
    "\n",
    "    il existe une route entre A et C\n",
    "    il existe une route entre A et B\n",
    "    il existe une route entre A et D\n",
    "    il existe une route entre B et F\n",
    "    il existe une route entre B et E\n",
    "    il existe une route entre B et G\n",
    "    il existe une route entre D et G\n",
    "    il existe une route entre E et F\n",
    "\n",
    "Ici aussi, la représentation sous forme de graphe s'impose : \n",
    "\n",
    "![Texte alternatif…](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_1.png)\n",
    "\n",
    "Pour les graphes **non orientés** : les relations sont appelées **arêtes**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "VL3z1xB5Xq71"
   },
   "source": [
    "### **2.2 Graphe orienté**\n",
    "\n",
    "\n",
    "\n",
    " Problème : avec cette représentation du réseau routier sous forme de graphe, il est impossible de tenir compte des routes en sens unique (par exemple il est possible d'aller de A vers D mais pas de D vers A)\n",
    "\n",
    "Voici de nouvelles contraintes :\n",
    "\n",
    "    il existe une route entre A et C (double sens)\n",
    "    il existe une route entre A et B (sens unique B->A)\n",
    "    il existe une route entre A et D (sens unique A->D)\n",
    "    il existe une route entre B et F (sens unique B->F)\n",
    "    il existe une route entre B et E (sens unique E->B)\n",
    "    il existe une route entre B et G (double sens)\n",
    "    il existe une route entre D et G (double sens)\n",
    "    il existe une route entre E et F (double)\n",
    "\n",
    "Pour tenir compte de ces nouvelles contraintes, on utilisera un graphe orienté :\n",
    "\n",
    "![Texte alternatif…](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_2.png)\n",
    "\n",
    "Dans un graphe orienté , les relations possèdent une orientation. Ces relations sont appelées \"arcs\" .\n",
    "On dira qu'un graphe orienté G est un couple G = (V,A) avec V un ensemble de sommets et A un ensemble d'arcs. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "eTy20iQJYBJs"
   },
   "source": [
    "### **2.3 Graphe pondéré**\n",
    "\n",
    "\n",
    "Parfois il est intéressant d'associer aux arrêtes ou aux arcs des valeurs, on parle alors de graphes pondérés. Si nous revenons à notre \"graphe cartographie\", il est possible d'associer à chaque arête la distance en km entre les 2 lieux, ou encore, le temps de trajet entre les deux lieux : \n",
    "\n",
    "**Pondéré en distance**\n",
    "\n",
    "![Texte alternatif…](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_3.png)\n",
    "\n",
    "**Pondéré en minutes**\n",
    "\n",
    "![Texte alternatif…](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_4.png)\n",
    "\n",
    "En fonction du choix fait par le conducteur (trajet le plus court \"en distance\" ou trajet le plus court \"en temps\"), l'algorithme permettant de déterminer le \"chemin le plus court entre 2 points\" travaillera sur le graphe \"graphe pondéré (km) cartographie\" ou sur le graphe \"graphe pondéré (minutes) cartographie\". À noter que le \"graphe pondéré (minutes) cartographie\" peut évoluer au cours du temps en fonction du trafic routier : une application comme Waze utilise les données en en provenance des utilisateurs de l'application afin de mettre à jour en temps réél leur \"graphe pondéré (minutes) cartographie\". \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QuBI5BQRY2ZV"
   },
   "source": [
    "## **3. Situations où la structure de données graphe nous est utile**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "u0kDDkzFZHEe"
   },
   "source": [
    " Source de cette partie : [https://zestedesavoir.com/]  \n",
    " Un graphe sert avant tout à manipuler des concepts, et à établir un lien entre ces concepts. N'importe quel problème comportant des objets avec des relations entre ces objets peut être modélisé par un graphe.\n",
    "Il apparaît donc que les graphes sont des outils très puissants et largement répandus qui se prêtent bien à la résolution de nombreux problèmes.\n",
    "\n",
    "En voici quelques uns. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "F54LaSCQZKHq"
   },
   "source": [
    "### **3.1 La recherche de chemins**\n",
    "\n",
    "Il s'agit d'un cas très classique, notamment dans le domaine du jeu vidéo. Chaque nœud représente une position (ici une case libre) et chaque arête correspond à un chemin entre deux positions (ici deux cases libres adjacentes).\n",
    "Il est courant de chercher le chemin le plus court entre deux positions : les IA s'en servent pour déplacer les créatures aussi vite que possible dans le monde virtuel. En remplaçant les nœuds par des adresses et les arêtes par des routes, on obtient le graphe utilisé par les GPS ou Google Map par exemple.\n",
    "On utilise couramment le terme anglais pathfinding pour désigner la recherche de chemins dans un graphe. \n",
    "\n",
    "![Texte alternatif…](https://zestedesavoir.com/media/galleries/912/0dcbf772-4c53-471a-89a5-80a64a58be9f.jpg.960x960_q85.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zE1r1kAWZlTY"
   },
   "source": [
    "### **3.2 Des relations entre individus**\n",
    "\n",
    "Cet outil est très utilisé en sciences sociales pour représenter des individus et leurs différents liens. On en fait usage dans le milieu de la recherche, mais aussi dans les réseaux sociaux. L'objectif va être de pouvoir identifier les communautés formées, les centres d'intérêt communs… Une exploitation intelligente de ces données est indispensable pour suggérer à l'utilisateur les choses qu'il est susceptible d'aimer, les personnes qu'il connaît peut-être, et avant tout (et surtout) pour créer des publicités ciblées adaptées à chacun.\n",
    "\n",
    "Une anecdote à ce sujet : en moyenne seules 8 personnes vous séparent de n'importe quelle autre personne à la surface de la Terre. Si vous prenez la connaissance de la connaissance etc… d'une de vos connaissances, en moyenne 8 personnes permettront de vous connecter avec n'importe quel français, américain, indien ou japonais. Et il est rare de dépasser 11 ou 12. Il s'agit là du diamètre moyen du graphe social de l'humanité.\n",
    "\n",
    "\n",
    "![Texte alternatif…](https://zestedesavoir.com/media/galleries/912/f84449b8-1172-4f05-b133-43ec692e42a4.png.960x960_q85.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "mCcRTYqsaBlQ"
   },
   "source": [
    "### **3.3 L’ordonnancement de tâches : le tri topologique**\n",
    "\n",
    "Les problèmes d'ordonnancement de tâches sont toujours un sujet de recherche active aujourd'hui. On peut représenter chacune des tâches à effectuer par un nœud, et les dépendances entre chacune des tâches par les arêtes. Ainsi, l’ordre dans lequel on enfile chaussettes et pantalon importe peu, mais il faut que les deux soient mis avant de lacer ses chaussures. De la même façon, on peut installer les câblages électrique et téléphonique dans l'ordre de notre choix, mais il faut que les murs soient construits avant !\n",
    "On résout ce problème avec **un tri topologique**. \n",
    "\n",
    "\n",
    "![Texte alternatif…](https://zestedesavoir.com/media/galleries/912/2215a2ef-3d28-492e-a1ca-652a956fda31.jpg.960x960_q85.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_BqjfzASaL6Q"
   },
   "source": [
    "### **3.4 Minimiser l'usage de ressources avec les arbres couvrants minimaux**\n",
    "\n",
    "En parlant de câblage, vous souhaitez que toutes vos prises soient reliées au secteur, non ? Cela est simple ! Mais le fil électrique coûte cher au mètre et vous souhaitez minimiser le prix de votre installation.\n",
    "Ainsi, vous associerez un nœud à chaque prise, et une arête à chaque fil qu'il est possible (mais pas nécessaire) d'installer. A vous de choisir l'ensemble de câbles les plus courts pour relier toutes les prises !\n",
    "Cela correspond à la recherche de l'arbre couvrant minimal. \n",
    "\n",
    "**Ici l'ensemble de fils les plus courts est colorié en rouge. **\n",
    "![Texte alternatif…](https://zestedesavoir.com/media/galleries/912/579ce0b7-7181-4eb1-a199-364cc761079f.png.960x960_q85.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Bg9oyrrnad5W"
   },
   "source": [
    "### **3.5 Tromper votre ennui en géographie en coloriant des cartes**\n",
    "\n",
    "Vous vous ennuyez à mourir en géographie. Comme vous êtes un individu froid et austère, mais aussi efficace, économe et démuni, vous souhaitez colorier cette triste carte en utilisant un minimum de couleurs, et en faisant en sorte que deux pays limitrophes ne soient jamais de la même couleur.\n",
    "Il s'agit du problème de coloration de graphe. Pour une carte en 2D ne cherchez plus : la réponse est 4, mais ce n'est pas le cas de tout les graphes… en effet, dans un carte, chaque pays est un nœud, et les arêtes correspondent au frontières communes. \n",
    "\n",
    "\n",
    "![Texte alternatif…](https://zestedesavoir.com/media/galleries/912/029ad86a-cbc0-4a1a-ae7d-26aa339924c2.gif.960x960_q85.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "IOLFBXxSareO"
   },
   "source": [
    "### **3.6 Poster du courrier**\n",
    "\n",
    "\n",
    "\n",
    "Vous êtes le facteur d'un petit village, vous distribuez le courrier à vélo, à la seule force de vos jambes. Vous devez passer devant toutes les maisons du village, ce qui implique de traverser toutes les rues. Mais soucieux de préserver vos forces et de renouveler continuellement votre découverte des paysages, vous ne voulez pas traverser deux fois la même rue. Ici chaque nœud est un carrefour, et chaque arête une rue. Vous êtes en train de chercher un circuit Eulérien !\n",
    "\n",
    "Il doit son nom à Leonhard Euler, qui chercha à savoir s'il était possible de franchir les 7 ponts de Königsberg sans jamais repasser deux fois sur le même (et en ne traversant le fleuve que grâce aux ponts, bien entendu).\n",
    "\n",
    "\n",
    "\n",
    "![Texte alternatif…](https://zestedesavoir.com/media/galleries/912/f16ed77f-92ef-4a07-bd8f-e41f37ffff48.png.960x960_q85.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0wOLPnO7bCav"
   },
   "source": [
    "### **3.7 ... d'autres exemples**\n",
    "\n",
    "Pensez à Youtube qui suggère des vidéos proches de celle que vous regardez (d'aucun prétendent qu'on finira toujours par aboutir à des vidéos de chats), pensez à wikipédia qui propose des articles connexes (nous reviendrons sur ce terme), pensez au cerveau humain, à ses milliards de neurones et à ses centaines de milliards de connexions entre eux ! Les graphes sont partout.\n",
    "\n",
    "Apprenez à reconnaître un problème de graphe lorsque vous en voyez un, c'est déjà la moitié du travail. Il ne vous reste alors plus qu'à trouver l'algorithme qui répond à votre problème !\n",
    "\n",
    "**Il existe de nombreuses méthodes permettant d'implémenter un graphe. Nous verrons tout d'abord les matrices d'adjacences et les listes d'adjacences.** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jlcITPWqcMHd"
   },
   "source": [
    "## **4. Terminologie**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2Ghuu0KccTXV"
   },
   "source": [
    "### **4.1 Terminologie des graphes non orientés**\n",
    "\n",
    "***Tous les termes définis dans cette section sont de simples définitions, que vous devez connaitre***\n",
    "\n",
    "**Arrête** : Relation entre deux sommets. Notation : A−B\n",
    "\n",
    "**Sommets Adjacents** : Deux sommets sont adjacents si ils possèdent au moins une arrête qui les joint.\n",
    "\n",
    "**Degré d'un sommet X** : Le nombre d'arrêtes dont X est une extrémité.\n",
    "\n",
    "**Chaîne** : Suite de sommets consécutifs joints par des arrêtes.\n",
    "\n",
    "**Cycle** : Chaine dont le début est le même que la fin.\n",
    "\n",
    "**Graphe connexe** : Chaque sommet est relié à tous les autres par au moins une chaîne.\n",
    "\n",
    "![Texte alternatif…](https://cms.alloprof.qc.ca//sites/default/files/importFiche/2730i3.jpg)\n",
    "\n",
    "**Graphe complet** : Chaque sommet est relié directement à tout les autres.\n",
    "\n",
    "![Texte alternatif…](https://cms.alloprof.qc.ca//sites/default/files/importFiche/d1414i10.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kcFDgffWdL3U"
   },
   "source": [
    "### **4.2 Terminologie des graphes orientés**\n",
    "\n",
    " **Arc** : Relation orientée entre deux sommets. Notation : A→B\n",
    "\n",
    "**Sommets Adjacents** : Deux sommets sont adjacents si il existe au moins un arc qui les joint.\n",
    "\n",
    "**Degré d'un sommet X** : Le nombre d'arcs dont X est une extrémité.\n",
    "\n",
    "**Chemin** : Suite de sommets consécutifs joints par des arcs.\n",
    "\n",
    "**Circuit** : Chemin dont le début est le même que la fin.\n",
    "\n",
    "**Exemple :**\n",
    "\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/2/23/Directed_graph_no_background.svg/1200px-Directed_graph_no_background.svg.png\" width=300px>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BnE6RkQfd5Pr"
   },
   "source": [
    "### **4.3 Graphes simples et multigraphes**\n",
    "\n",
    "**Graphe simple** : au plus une relation relie 2 sommets et il n'y a pas de boucle (une boucle est une relation reliant un sommet à lui même). Peut être orienté ou non-orienté. \n",
    "Ci dessous un exemple de graphe simple non orienté.\n",
    "\n",
    "**Exemple :**\n",
    "\n",
    "![Texte alternatif…](Capture_graphe_simple.jpg)\n",
    "\n",
    "**Multi graphe** : les graphes qui ne sont pas simples ! C'est à dire possédant au moins une boucle ou 2 sommets avec 2 relation\n",
    "\n",
    "**Exemple :**\n",
    "\n",
    "![Texte alternatif…](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Multigraph.svg/200px-Multigraph.svg.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "siaVGYYZRITe"
   },
   "source": [
    "## **5. Exercices sur les graphes**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "M8H9uPRbROXT"
   },
   "source": [
    "Faire sur wims : GRAPHE exercice sur les graphes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "CWrLdcDORY-s"
   },
   "source": [
    "## **6. Implémenter un graphe avec une Matrice d'adjacence**\n",
    "\n",
    "Une matrice est un tableau à double entrée : \n",
    "\n",
    "Exemple de matrice\n",
    "![texte du lien](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_5.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wubJeuVvUg7S"
   },
   "source": [
    " La matrice A ci-dessus est constitué de 5 lignes et 4 colonnes. On appelle matrice carrée une matrice qui comporte le même nombre de lignes et de colonnes. Les matrices d'adjacences sont des matrices carrées.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Reprenons l'exemple du \"graphe cartographie\" vu en 2.1: \n",
    "\n",
    "![Texte alternatif…](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QtwsZgReUtD5"
   },
   "source": [
    "Voici la matrice d'adjacence de ce graphe :\n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_6.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "nBLzX8TbU-RJ"
   },
   "source": [
    " Comment construire une matrice d'adjacence ?\n",
    "\n",
    "Il faut savoir qu'à chaque ligne correspond un sommet du graphe et qu'à chaque colonne correspond aussi un sommet du graphe. À chaque intersection ligne i-colonne j (ligne i correspond au sommet i et colonne j correspond au sommet j), on place un 1 s'il existe une arête entre le sommet i et le sommet j, et un zéro s'il n'existe pas d'arête entre le sommet i et le sommet j. \n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_7.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2bDCez_SVH6A"
   },
   "source": [
    "\n",
    "  Il existe une arête entre le sommet E et le sommet F, nous avons donc placé un 1 à l'intersection de la ligne E et de la colonne F (il en est de même à l'intersection de la ligne F et de la colonne E)\n",
    "  \n",
    "  Il n'existe pas d'arête entre le sommet D et le sommet C, nous avons donc placé un 0 à l'intersection de la ligne D et de la colonne C (il en est de même à l'intersection de la ligne C et de la colonne D)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_UToa_H6VYEZ"
   },
   "source": [
    "**Exercice 1:**\n",
    "\n",
    "Vérifiez que la matrice d'adjacence proposée ci-dessus correspond bien au graphe \"cartographie\" (retracer à la main le graphe à partir de la matrice).\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "UO5GywrYVrav"
   },
   "source": [
    "**Exercice 2:**\n",
    "\n",
    "Établissez la matrice d'adjacence du graphe ci-dessous \n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/graphe.png)\n",
    "Graphe réseau social\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Correction**  \n",
    "$$\\begin{bmatrix}\n",
    " 0& 1 & 1 &1  & 0 &0 \\\\ \n",
    " 1& 0 & 0 & 1 & 0 & 0\\\\ \n",
    " 1&0  & 0 & 1 &1  &0 \\\\ \n",
    " 1& 1 & 1 &0  & 1 &1 \\\\ \n",
    " 0& 0 &1  & 1 &0  &1 \\\\ \n",
    " 0& 0 &0  & 1 & 1 & 0\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MilGY-ZfV1mH"
   },
   "source": [
    "**Exercice 3:**\n",
    "\n",
    "Il est aussi possible d'établir une matrice d'adjacence pour un graphe orienté. Le principe reste le même : si le sommet i (ligne) est lié au sommet j (colonne), nous avons un 1 à l'intersection (0 dans le cas contraire).  \n",
    "\n",
    "\n",
    " Établissez la matrice d'adjacence du graphe ci-dessous  \n",
    "\n",
    "![](Capture_exo_mat_adj.jpg)\n",
    "Graphe orienté"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Correction**  \n",
    "$$\\begin{bmatrix}\n",
    " 0&3  &3\\\\ \n",
    " 2& 0 & 0\\\\ \n",
    " 0&  4& 0\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_-3NseGHkSNH"
   },
   "source": [
    "**Matrices d'adjacence en python**\n",
    "\n",
    "Il est assez simple d'utiliser les matrices d'adjacence en Python grâce aux tableaux de tableaux vus l'année dernière :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "FhsVzRlnkXwe"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 1, 1, 1, 0, 0, 0], [1, 0, 0, 0, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 0], [0, 1, 0, 1, 0, 0, 0]]\n"
     ]
    }
   ],
   "source": [
    "#matrice d'ajacence pour le graphe cartographie\n",
    "m = [[0, 1, 1, 1, 0, 0, 0],\n",
    "     [1, 0, 0, 0, 1, 1, 1],\n",
    "     [1, 0, 0, 0, 0, 0, 0],\n",
    "     [1, 0, 0, 0, 0, 0, 1],\n",
    "     [0, 1, 0, 0, 0, 1, 0],\n",
    "     [0, 1, 0, 0, 1, 0, 0],\n",
    "     [0, 1, 0, 1, 0, 0, 0]]\n",
    "\n",
    "print(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "J8BM2HPfkin-"
   },
   "source": [
    "## **7. Implémenter un graphe avec des Listes d'adjacence**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jQiqhyvjk1QO"
   },
   "source": [
    " Pour commencer, on définit une liste des sommets du graphe. À chaque élément de cette liste, on associe une autre liste qui contient les sommets lié à cet élément :\n",
    "\n",
    "Reprenons l'exemple du \"graphe cartographie\" : \n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_1.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "G4D1x8YEtPhY"
   },
   "source": [
    "Voici la liste d'adjacence de ce graphe : \n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_10.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Kotm7LJvtW9n"
   },
   "source": [
    "Pour les graphes orientés, il est nécessaire de définir 2 listes : la liste des successeurs et la liste des prédécesseurs. Soit un arc allant d'un sommet A vers un sommet B (flèche de A vers B). On dira que B est un successeur de A et que A est un prédécesseur de B :\n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_2.png)\n",
    "\n",
    "liste d'adjacence successeurs du graphe orienté cartographie :\n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_11.png)\n",
    "\n",
    "\n",
    "liste d'adjacence prédécesseurs du graphe orienté cartographie :\n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/nsi_term_structDo_graphe_12.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6IPvNCSKuA3m"
   },
   "source": [
    "**Exercice 1:**\n",
    "\n",
    "Établissez la liste d'adjacence du graphe ci-dessous :\n",
    "\n",
    "![](https://pixees.fr/informatiquelycee/n_site/img/graphe.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "pAsUYIEYvLVm"
   },
   "source": [
    "Il est possible de travailler avec des listes d'adjacences en Python en utilisant les dictionnaires : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "cMM7YeHXvNZg"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'A': ['B', 'C', 'D'], 'B': ['A', 'E', 'F', 'G'], 'C': ['A'], 'D': ['A', 'G'], 'E': ['B', 'F'], 'F': ['B', 'E'], 'G': ['B', 'D']}\n"
     ]
    }
   ],
   "source": [
    "#liste d'ajacence pour le graphe cartographie\n",
    "l = {'A':['B','C','D'], 'B':['A', 'E', 'F', 'G'], 'C':['A'], 'D':['A', 'G'], 'E':['B', 'F'],\\\n",
    "     'F':['B', 'E'], 'G':['B', 'D']}\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XwM6cmGLvzRW"
   },
   "source": [
    "## **8. Exercices sur les matrices et listes d'adjacence**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "VJ0H_DJsv_md"
   },
   "source": [
    "Faire sur wims : GRAPHE exercice sur les graphes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MBn9rl7EzXJ0"
   },
   "source": [
    "## **9. Implémentation en pratique (en Python)**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gRD9kFq4zVcO"
   },
   "source": [
    "**Comment choisir l'implémentation à utiliser (matrice d'adjacence ou liste d'adjacence) ?**\n",
    "\n",
    "\n",
    "  le choix se fait en fonction de la densité du graphe, c'est-à-dire du rapport entre le nombre d'arêtes et le nombre de sommets. Pour un graphe dense on utilisera plutôt une matrice d'adjacence.\n",
    "\n",
    "  certains algorithmes travaillent plutôt avec les listes d'adjacences alors que d'autres travaillent plutôt avec les matrices d'adjacences. Le choix doit donc aussi dépendre des algorithmes utilisés (nous aurons très prochainement l'occasion d'étudier plusieurs de ces algorithmes).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "iOoEG3wR0Lsr"
   },
   "source": [
    "**Implémenter les graphes :**\n",
    "\n",
    "Comme les listes, les piles, et les files, il est important de distinguer le type abstrait de représentation des données, du type implémenté dans le langage.\n",
    "\n",
    "En Python il n'existe pas de type GRAPHE prédéfini. C'est donc à chacun de l'implémenter avec les outils disponibles dans le langage.\n",
    "\n",
    "Comme pour les listes il peut exister, selon les auteurs, des différences sur le nombre et la définition des primitives de bases. Nous allons utiliser ici ce jeu de primitives :  \n",
    "\n",
    "- `creerGrapheVide()` : retourne un graphe vide\n",
    "- `estVideGraphe(G)` : retourne True si G est un graphe vide\n",
    "- `ajouterSommet(G,s)` : retourne le graphe après ajout du sommet s\n",
    "- `supprimerSommet(G,s)` : retourne le graphe après suppression du sommet s (et tout les arcs rliés à s)\n",
    "- `existeSommet(G,s)` : retourne True si s est un sommet du graphe G  \n",
    "  \n",
    "  \n",
    "    \n",
    "- Pour un graphe orienté :\n",
    "  - `ajouterArc(G,sd,sa)` : retourne le graphe après ajout d'un arc reliant sd à sa (orienté)\n",
    "  - `supprimerArc(G,sd,sa)` : retourne le graphe après suppression de l'arc sd->sa\n",
    "  - `existeArc(G,sd,sa)` : retourne True si sd->sa est un arc du graphe G\n",
    "- Pour un graphe non orienté :\n",
    "  - `ajouterArete(G,sd,sa)` : retourne le graphe après ajout d'une arête reliant sd à sa (non-orienté)\n",
    "  - `supprimerArete(G,sd,sa)` : retourne le graphe après suppression de l'arête sd->sa\n",
    "  - `existeArete(G,sd,sa)` : retourne True si sd->sa est une arête du graphe G\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4VGUcrZe0Y06"
   },
   "source": [
    "**Une première implémentation avec un dictionnaire**\n",
    "\n",
    "Comme nous l'avons vu, un graphe peut être représenté par une liste d'adjacence. Cette représentation peut être implémentée efficacement avec un dictionnaire. Chaque sommet sera donc une clé dictionnaire, et sa valeur sera la liste des sommets sa reliés à s dans le sens s -> sa.\n",
    "\n",
    "En conséquence, un graphe vide est un dictionnaire vide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "pE9ZlDsF0bJs"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "après ajout des 4 sommets et des arcs A->B et C->D:\n",
      "G =  {'A': ['B'], 'B': [], 'C': ['D'], 'D': []}\n",
      "A dans G ? : True\n",
      "A->B dans G ? : True\n",
      "A->B dans G après suppression ? : False\n",
      "Après suppression du sommet D\n",
      " G =  {'A': [], 'B': [], 'C': []}\n"
     ]
    }
   ],
   "source": [
    "def creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G : dict) -> bool :\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G,'Vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArc(G : dict ,sd,sa) -> dict : #sd et sa peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet  de depart '\n",
    "    assert sa in G ,'le graphe ne contient pas le sommet  arrivee '\n",
    "    G[sd].append(sa)\n",
    "def supprimerSommet(G : dict , s ) -> dict:  #s peut être str ou int\n",
    "    assert s in G,'le graphe ne contient pas le sommet '\n",
    "    del G[s]\n",
    "    for sommet in G.keys() :\n",
    "        if s in G[sommet] :\n",
    "            G[sommet].remove(s)\n",
    "def supprimerArc(G : dict,sd,sa) -> dict : # sd et sa peuvent etre int ou str \n",
    "    assert sd in G,'le graphe ne contient pas le sommet '\n",
    "    assert sa in G,'le graphe ne contient pas le sommet dcarrivee'\n",
    "    assert sa in G[sd] , 'l arc  n existe pas.'\n",
    "    G[sd].remove(sa)\n",
    "def existeSommet(G : dict ,s) -> bool :  #s peut être str ou int\n",
    "    return s in G\n",
    "def existeArc(G : dict ,sd,sa) -> bool :  #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G[sd]\n",
    "\n",
    "G=creerGrapheVide()\n",
    "ajouterSommet(G,'A')\n",
    "ajouterSommet(G,'B')\n",
    "ajouterSommet(G,'C')\n",
    "ajouterSommet(G,'D')\n",
    "ajouterArc(G,'A','B')\n",
    "ajouterArc(G,'C','D')\n",
    "\n",
    "print('après ajout des 4 sommets et des arcs A->B et C->D:\\nG = ',G)\n",
    "\n",
    "print('A dans G ? :',existeSommet(G,'A'))\n",
    "print('A->B dans G ? :',existeArc(G,'A','B'))\n",
    "supprimerArc(G,'A','B')\n",
    "print('A->B dans G après suppression ? :',existeArc(G,'A','B'))\n",
    "\n",
    "supprimerSommet(G,'D')\n",
    "\n",
    "print('Après suppression du sommet D\\n G = ',G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kC4_Wwgx3Egi"
   },
   "source": [
    "**Exercice 1 : Implémenter un graphe**\n",
    "\n",
    "En utilisant l'implémentation de l'exemple précédant, créez le dictionnaire G correspondant au graphe ci-dessous. Votre code doit afficher le dictionnaire correspondant à ce graphe. \n",
    "\n",
    "implémentation avec dictionnaire\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/2/23/Directed_graph_no_background.svg/1920px-Directed_graph_no_background.svg.png\" width=\"300\" height=\"300\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "t0CE7iry362I"
   },
   "outputs": [],
   "source": [
    "def creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G : dict) -> bool :\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G.keys(),'vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArc(G : dict , sd , sa ) -> dict : #sa et sd peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G ,'le graphe ne contient pas le sommet d arrivee'\n",
    "    G[sd].append(sa)\n",
    "def supprimerSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s in G,'le graphe ne contient pas le sommet '\n",
    "    del G[s]\n",
    "    for sommet in G.keys() :\n",
    "        if s in G[sommet] :\n",
    "            G[sommet].remove(s)\n",
    "def supprimerArc(G : dict ,sd , sa ) -> dict: #sd et sa peuvent être str ou int\n",
    "    assert sd in G,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G,'le graphe ne contient pas le sommet '\n",
    "    assert sa in G[sd] , 'l arc  n existe pas.'\n",
    "    G[sd].remove(sa)\n",
    "def existeSommet(G : dict , s ) -> bool:\n",
    "    return s in G\n",
    "def existeArc(G : dict , sd  , sa ) -> bool: #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G and sa in G[sd]\n",
    "\n",
    "G=creerGrapheVide()\n",
    "# complétez ici\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Correction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "t0CE7iry362I"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: [2, 3], 2: [], 3: [2, 4], 4: [3]}\n"
     ]
    }
   ],
   "source": [
    "def creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G : dict) -> bool :\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G.keys(),'vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArc(G : dict , sd , sa ) -> dict : #sa et sd peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G ,'le graphe ne contient pas le sommet d arrivee'\n",
    "    G[sd].append(sa)\n",
    "def supprimerSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s in G,'le graphe ne contient pas le sommet '\n",
    "    del G[s]\n",
    "    for sommet in G.keys() :\n",
    "        if s in G[sommet] :\n",
    "            G[sommet].remove(s)\n",
    "def supprimerArc(G : dict ,sd , sa ) -> dict: #sd et sa peuvent être str ou int\n",
    "    assert sd in G,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G,'le graphe ne contient pas le sommet '\n",
    "    assert sa in G[sd] , 'l arc  n existe pas.'\n",
    "    G[sd].remove(sa)\n",
    "def existeSommet(G : dict , s ) -> bool:\n",
    "    return s in G\n",
    "def existeArc(G : dict , sd  , sa ) -> bool: #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G and sa in G[sd]\n",
    "\n",
    "G=creerGrapheVide()\n",
    "# complétez ici\n",
    "for i in range(1,5):\n",
    "    ajouterSommet(G,i)\n",
    "ajouterArc(G,1,2)\n",
    "ajouterArc(G,1,3)\n",
    "ajouterArc(G,3,2)\n",
    "ajouterArc(G,4,3)\n",
    "ajouterArc(G,3,4)\n",
    "print(G)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visualiser un graphe orienté :**  \n",
    "Il est pratique de visualiser un graphe implémenté par exemple sous forme de dictionnaire.  \n",
    "Pour cela nous allons utiliser la bibliothèque networkx. Vous pouvez lire un documentation ici : [https://networkx.github.io/documentation/stable/reference/introduction.html]  \n",
    "Voici un exemple qui montre comment créer un graphe orienté de type networkx, et qui l'affiche"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deVyU1eIG8GeGAYYdwQG9YbmLmlqWuYTsI8qSqBCmZlcpF9Rb3spb0e9eb2ZlWaYl3ot91DLDBXclFQkkDfOquRYZhhpuA6ggywAD7++Pbt6IRQaBMzPv8/18+miz8VDZwznnPedVSJIkgYiISCaUogMQERG1JRYfERHJCouPiIhkhcVHRESywuIjIiJZYfEREZGssPiIiEhWWHxERCQrLD4iIpIVFh8REckKi4+IiGSFxUdERLLC4iMiIllh8RERkayw+IiISFZYfEREJCssPiIikhUWHxERyQqLj4iIZIXFR0REssLiIyIiWWHxERGRrKhEByDLUFBSgeRjeci+VoxivQHOahW8Ozgj+hEvuDvaio5HRHSHQpIkSXQIMl8nf7mF5Rk5OHAuHwBQYai585xapYQEwL+XBnF+3TGgk6uglERE/8Pio2b7/PAFLEzJht5Qjcb+K1IoALXKCvGh3pg0pHOb5SMiqg+nOqlZfi29H1BeVXPX10oSUF5VjYUpPwAAy4+IhOKIj4x28pdbGL/yMMqrqu88JhmqULgvAfoLJ1CjL4HKtSPa+U2GXbdHa73XztoKG6YNQX8vTnsSkRi8qpOMtjwjB3pDda3HpJpqqJzao8OEd9Bp7ga4+k5C/vZFMNy6Xut1ekM1EjJy2jIuEVEtLD4ySkFJBQ6cy6+zpqe0UcN1+ESoXD2hUChh3/0xqFw8UXGtdslJEpD+Yz4KSyraMDUR0f+w+MgoycfymvS66tKbqLpxGTaa++s8pwCQfLxpn0NE1NJYfGSU7GvFtbYs1EeqNqBgx2I49guCtXunOs/rDTXIvnq7tSISETWKxUdGKdYbGn1ekmpQsOt9wEoFN+2MRj6nqqWjERE1CYuPjOKsbngHjCRJKExZhurSW9CMeQ0Kq4Zf66y2bo14RER3xeIjo3h3cIatqv7/bG7sXY6qwl/gEfV3KK0bPqZMrVLCu6NTa0UkImoU9/GRUQpKKvD4oq/qrPMZinS4vGIqYGUNhdLqzuNuI2fBsW9ArdfaqpT45m+BPMOTiITgyS1klPaOtvDrqUHqD9drbWlQuXjggVd23fX9CgUQ0EvD0iMiYTjVSUab5d8dapXV3V9YD7XKCnH+3Vs4ERFR07H4yGgDOrliTGcJ6gbW+hpiYwVc/XI53vzrNHz55ZeoqOAmdiJqeyw+ajK9Xo81a9aga9eueDs2FCM7lMHO2goKRePvUyh+PaMzfpQ3yk/tw6ZNm/Dkk0/C1dUVTz75JLjMTERticVHTfLBBx9Ao9Fg9uzZyM3NhZWVFd6JDcOGaUMQ0scTtiplnRGgWqWErUqJkD6e2DBtCJ55vBsmT54MhUKBkpISSJIEGxsbKO7WnERELYgXt1CT2Nraoqqq6s70ZL9+/aBWq9HfS41/TXoUhSUVSD6eh+yrt1Gsr4Kz2hreHZ0QNbD2HdhjY2ORlJSEyspKAMC8efOEfD9EJF/czkBNUlNTg2HDhuHo0aOQJAnx8fF44403jP4cSZLQqVMn9OnTB5MmTcK8efOQkpKCgQMHtkJqIqK6OOKjJpk3bx7UajUyMzMxduxYhIeHN+tzFAoFvv32W2g0GtjY2MDJyQkjR47E9u3bMXTo0BZOTURUF0d8dFcrVqzAhx9+iKysLLi5uUGSpBZdl9uzZw8mT56MDRs2ICAg4O5vICK6Byw+atSXX36JqVOn4uDBg+jWrVurfZ2MjAxER0fj008/RWhoaKt9HSIiFh816OTJk9Bqtdi2bRuGDRvW6l/v8OHDGD16NBISEjBu3LhW/3pEJE9c46N6Xb58GREREfjoo4/apPQAYMiQIdizZw9CQ0NRXl6OSZMmtcnXJSJ5YfFRHSUlJYiIiMDMmTMRExPTpl/74YcfRlpaGkaMGIGysjJMmzatTb8+EVk+TnVSLdXV1YiMjISnpydWrlwpbHN5Tk4OgoOD8fzzz2Pu3LlCMhCRZeKIj2qZO3cuysvLsWLFCqEnqnTv3h2ZmZkICgpCWVkZ4uPjhWUhIsvC4qM7li1bhrS0NBw6dAjW1uLvkH7//fcjMzMTWq0WpaWlWLhwIY83I6J7xqlOAgDs2LEDM2fOxKFDh9C5c2fRcWopKChASEgIfHx8sGTJEiiVPGKWiJqPxUc4duwYRo4cid27d+Oxxx4THadet27dQmhoKPr06YN///vfsLJq3v0AiYj4o7PMXbp0CaNHj0ZiYqLJlh4AuLq6Yt++ffj5558xefJkVFVViY5ERGaKIz4ZKy4uho+PD5555hm8+OKLouM0SXl5OaKiomBjY4P169fD1tb27m8iIvodFp9MVVVVISIiAl27dsXy5cvN6qKRyspKTJgwASUlJdiyZQvs7e1FRyIiM8KpThmSJAlz5syBQqHAsmXLzKr0ANwZ7Wk0GowaNQq3b98WHYmIzAiLT4bef/99ZGVlYcOGDVCpzHNHi0qlwqeffgpvb29otVrcvHlTdCQiMhMsPpnZvHkzli5dit27d8PZ2Vl0nHuiVCrxr3/9C0OHDkVAQAB0Op3oSERkBlh8MvLtt99ixowZ2L59O7y8vETHaREKhQIffPABIiIi4OfnhytXroiOREQmzjznuchoubm5GDNmDFavXo2BAweKjtOiFAoFFixYAAcHB/j6+mL//v0mtwmfiEwHi08Gbt68ibCwMLz22msIDw8XHafVvPLKK3BwcICfnx9SU1PRs2dP0ZGIyASx+CxcZWUloqKiMGLECMyePVt0nFY3Z84c2NvbIyAgAHv37sWDDz4oOhIRmRju47NgkiQhNjYWhYWF2LJli6yO+UpKSsLcuXOxe/duPPLII6LjEJEJ4YjPgr311ls4efIkMjMzZVV6APDUU0/Bzs4Oo0aNwtatW/H444+LjkREJoLFZ6GSkpKQmJiIrKwsODg4iI4jRGRkJOzs7BAZGYn169cjKChIdCQiMgGc6rRABw8exNixY5GWloZ+/fqJjiPcgQMHEB0djdWrVyMsLEx0HCISjPv4LExOTg6ioqKwdu1alt5/+fn5YefOnZg6dSqSk5NFxyEiwTjVaUEKCwsRGhqKN954AyEhIaLjmJTBgwdj7969GDVqFMrKyjB58mTRkYhIEBafhaioqMCYMWMQGRmJadOmiY5jkh566CF89dVX0Gq1KC8vx/Tp00VHIiIBuMZnASRJwtNPPw29Xo+NGzdCqeQMdmPOnz+P4OBg/OUvf8HcuXNFxyGiNsYRnwWYP38+cnJykJ6eztJrgm7duiEzMxNBQUEoKSnB66+/bna3ZiKi5mPxmbnPPvsMn332GQ4fPgw7OzvRccxGp06dkJmZCa1Wi9LSUrz99tssPyKZ4FSnGcvIyEBMTAzS09PRp08f0XHMUmFhIUJCQjBs2DB8+OGHHDETyQCLz0xlZ2fDz88PSUlJCAwMFB3HrBUVFSE0NBTe3t5ITEyU3Sk3RHLDH2/NUH5+PsLCwvDOO++w9FqAi4sL9u7diwsXLmDSpEmoqqoSHYmIWhFHfGamvLwcQUFBCAwMxJtvvik6jkUpLy9HdHQ0VCoVNmzYAFtbW9GRiKgVsPjMSE1NDcaPHw+VSoV169bxYoxWUFlZiYkTJ6K4uBhbt26Fvb296EhE1MI41WlG4uPjceXKFaxatYql10psbGyQlJQET09PjBw5EsXFxaIjEVELY/GZiU8++QTJycnYtm0b1Gq16DgWTaVSYc2aNejbty+0Wi1u3LghOhIRtSBOdZqB1NRUPP300/j666/Ro0cP0XFkQ5IkvPTSS0hLS8O+ffvg4eEhOhIRtQCO+EzcmTNnMHHiRGzatIml18YUCgUWL16M0aNHw8/PD5cvXxYdiYhaAE9uMWHXrl1DeHg4lixZguHDh4uOI0sKhQL//Oc/YW9vD19fX6SlpaFz586iYxHRPWDxmajS0lJEREQgNjYWEydOFB1H9v72t7/BwcEBfn5+SE1NRc+ePUVHIqJm4hqfCaqursa4cePg4uKCNWvW8ApOE7Jq1Sq8/vrr2Lt3L2/0S2SmOOIzQfPmzUNRURE2btzI0jMxU6dOhb29PbRaLXbt2oVHH31UdCQiMhKLz8QkJCRg9+7dyMrKgo2Njeg4VI/x48fDzs4OoaGh2Lp1Kx5//HHRkYjICJzqNCEpKSmIjY3FoUOH0LVrV9Fx6C727duHiRMnYv369QgKChIdh4iaiMVnIk6cOAGtVosdO3Zg6NChouNQE2VmZiIqKgqrVq1CeHi46DhE1ATcx2cCLl++jCeeeAIJCQksPTPj6+uLXbt2ITY2Fps2bRIdh4iagGt8gt2+fRvh4eGYNWsWoqOjRcehZnjsscewb98+jBo1CuXl5Zg8ebLoSETUCE51CmQwGBAZGYmOHTsiMTGRV3CauezsbGi1Wrz22muYOXOm6DhE1ACO+ASRJAkvvPACKisrkZCQwNKzAN7e3jhw4ACCgoJQVlaGF198UXQkIqoHi0+QpUuXIiMjA4cOHYK1tbXoONRCunbtiszMTAQHB6O0tBT/93//xx9qiEwMi0+A7du347333sM333wDFxcX0XGohXXq1KlW+b3zzjssPyITwjW+Nnb06FGMGjUKKSkpGDRokOg41IoKCwsREhKCIUOGYNmyZVAqeRE1kSngn8Q2dOnSJYwePRorV65k6cmAu7s70tLScOLECTz77LOorq4WHYmIwBFfmykqKoKPjw+mTp2KuXPnio5Dbai0tBSjR49G+/btsXbtWq7pEgnG4msDVVVVCAsLQ48ePfDxxx9zvUeG9Ho9oqKioFQqsXHjRqjVatGRiGSLU52tTJIkzJo1C9bW1li6dClLT6bUajW2bNkCtVqNJ554AmVlZaIjEckWi6+Vvffeezhy5AjWr18PlYoX0cqZjY0NvvjiC3Ts2BEjR45EcXGx6EhEssTia0XJycn46KOPsGvXLjg5OYmOQyZApVJh9erVePDBBxEcHIwbN26IjkQkOyy+VnL48GHMnDkTO3bsgJeXl+g4ZEKUSiWWL18OX19fBAQEQKfTiY5EJCssvlaQm5uLsWPHYs2aNXj44YdFxyETpFAo8N5772HMmDHw9fXF5cuXRUcikg0uOrWwmzdvIjQ0FPHx8QgLCxMdh0yYQqHA/Pnz4eDggOHDhyMtLQ1dunQRHYvI4rH4WlBlZSXGjRuHkSNHYtasWaLjkJl4+eWXYW9vDz8/P6SmpqJXr16iIxFZNBZfC5EkCdOnT4eTkxMWL14sOg6ZmVmzZsHBwQEBAQHYs2cP+vfvLzoSkcVi8bWQt956C6dPn8aBAwdgZWUlOg6ZoT//+c+ws7PDiBEjsHPnTh5rR9RKWHwtICkpCYmJiTh8+DAcHBxExyEzFhMTA3t7e4SFhWHLli3w8fERHYnI4vDIsnt08OBBjB07FmlpaejXr5/oOGQhUlNTMWHCBCQlJSE4OFh0HCKLwu0M9+Cnn35CVFQUPv/8c5YetSitVostW7ZgwoQJ2Llzp+g4RBaFxddMhYWFCAsLw4IFCzBixAjRccgCDR8+HLt378azzz6LjRs3io5DZDG4xtcMFRUViIyMxJgxY/Dcc8+JjkMWbNCgQUhNTcXIkSNRVlaGP//5z6IjEZk9rvEZSZIkTJo0CRUVFdi4cSPvqk1tIjs7G1qtFq+++iri4uJExyEyaxzxGWn+/Pk4f/480tPTWXrUZry9vZGZmYmgoCCUlZXhpZdeEh2JyGyx+Izw6aefYu3atTh8+DDs7OxExyGZ6dKlCzIzMxEcHIySkhL84x//4P0diZqBU51NlJ6ejvHjxyMjIwO9e/cWHYdk7Pr169BqtQgJCcG7777L8iMyEouvCbKzs+Hn54ekpCQEBgaKjkOEGzduYOTIkRg0aBA++ugjTrsTGYF/Wu5Cp9MhLCwMixYtYumRyXBzc8P+/ftx6tQpTJ06FQaDQXQkIrPBEV8jysvLERgYiODgYCxYsEB0HKI6SktLERkZiXbt2uHzzz+HjY2N6EhEJo/F14CamhqMHz8eKpUK69at4zoKmSy9Xo8nn3wSkiRh06ZNUKvVoiMRmTROdTYgPj4eV65cwapVq1h6ZNLUajU2b94MBwcHREREoLS0VHQkIpPG4qvHypUrkZycjG3btvGnZzIL1tbWWLduHby8vBASEoKioiLRkYhMFqc6/yA1NRVPP/00vv76a/To0UN0HCKj1NTUYM6cOThy5Aj27NkDd3d30ZGITA5HfL9z5swZTJw4EZs2bWLpkVlSKpX4+OOPERAQAH9/f1y/fl10JCKTw5Nb/uvatWsIDw/Hhx9+iOHDh4uOQ9RsCoUCixYtgqOjI3x9fZGWlgYvLy/RsYhMBosPv14SHhERgdjYWEyYMEF0HKJ7plAo8Pe//x0ODg7w9fXF/v370bVrV9GxiEyC7Nf4qqurMW7cOLi4uGDNmjW8gpMszooVK/DWW28hNTUV3t7eouMQCSf7Ed+8efNQVFSEjRs3svTIIs2cORP29vYIDAzEnj170L9/f9GRiISSdfElJCRg9+7dyMrK4okXZNGeeeYZ2NvbQ6vVYufOnXjsscdERyISRrZTnSkpKYiNjcWhQ4e49kGysWvXLkydOhXJycnw9fUVHYdICFkW34kTJ6DVarFjxw4MHTpUdByiNrV//3489dRTWLduHUaMGCE6DlGbk90+vsuXL+OJJ55AQkICS49kKTg4GFu3bsWkSZOwY8cO0XGI2pys1vhu376N8PBwzJo1C9HR0aLjEAnj4+ODlJQUhIeHo6ysDOPHjxcdiajNyGaq02AwYPTo0fjTn/6ExMREXsFJBOD06dMICQnBwoULMWXKFNFxiNqELEZ8kiThhRdeQFVVFRISElh6RP/Vr18/ZGRkIDg4GGVlZZg1a5boSEStThbFt3TpUmRkZODQoUOwtrYWHYfIpPTs2ROZmZkICgpCaWkp5s2bJzoSUauy+OLbvn073nvvPXzzzTdwcXERHYfIJHXu3BmZmZkIDg5GSUkJ/vnPf3JmhCyWRa/xHT16FKNGjUJKSgoGDRokOg6RydPpdNBqtQgODsbixYtZfmSRLHY7w6VLlzB69GisXLmSpUfURB4eHkhPT8fBgwcRFxeHmpoa0ZGIWpxFjviKiorg4+ODqVOnYu7cuaLjEJmd4uJihIeHo3Pnzli1ahVUKotfFSEZsbjiq6qqQlhYGHr06IGPP/6YUzVEzVRWVoYxY8bA2dkZ69at43m2ZDEsqvgkScL06dNx+fJlbN++nT+lEt2jiooKxMTEwGAwIDk5GWq1WnQkontmNsVXUFKB5GN5yL5WjGK9Ac5qFbw7OCP6ES+4O9oCAN5991188cUX+Prrr+Hk5CQ4MZFlqKqqwuTJk6HT6bB9+3Y4OjqKjkR0T0y++E7+cgvLM3Jw4Fw+AKDC8L/FdrVKCQmAfy8NelVfxJLXX0BWVha8vLwEpSWyTNXV1Zg2bRqys7ORkpLCrUFk1ky6+D4/fAELU7KhN1SjsZQKADVVFZgx2AOvRvu0WT4iOampqcHzzz+PrKws7N27F+7u7qIjETWLyW5n+LX0fkB5VeOlBwASAIW1LT47fRufH77QFvGIZEepVGLZsmUIDg6Gv78/rl27JjoSUbOY5Ijv5C+3MH7lYZRXVd95rPjYTpSeTkNl/gU49PZD+/D6tynYWVthw7Qh6O/l2lZxiWRFkiQsXLgQn332GdLS0tCpUyfRkYiMYpIjvuUZOdAbqms9pnJ0h8uwGDj21zb6Xr2hGgkZOa0Zj0jWFAoFXn/9dcyYMQO+vr44f/686EhERjG56/0LSipw4Fx+nelN+17DAAAV13JQXVXQ4PslCUj/MR+FJRV3rvYkopb317/+FQ4ODvD398e+ffvQu3dv0ZGImsTkRnzJx/Lu+TMUAJKP3/vnEFHjpk+fjrfeeguBgYE4ceKE6DhETWJyI77sa8W1tiw0h95Qg+yrt1soERE15umnn4adnR1CQkKwY8cODB48WHQkokaZXPEV6w0t8jnfHPsOC87thLu7O9zc3Gr96u7uDkdHRx5nRtRCoqKiYGdnh4iICGzatAl+fn6iIxE1yOSKz1ndMpHa2dtCr9fj1KlTuHHjBgoLC+/8WlhYiKqqqjqF+PtibOgxOzu7FslHZGnCwsKwfv16REdHY+3atQgJCREdiaheJld83h2cYau6Vme6U6qpBn77S6qBZKgElFZQKK3qfIZapcSYwMGY7juhwa+j1+tx48aNWmX4+4LMycmpU5aFhYVQqVRNKsg//so7v5McBAYGYtu2bYiMjERiYiIiIyNFRyKqw+T28RWUVODxRV/VKb5bX69D0aGkWo+5PP4UXIdPrPMZtiolvvlbYItf1SlJEkpLSxssy4Yeu3nzJuzt7Y0qS3d3d7i4uMDKqm6xE5m6Y8eOISwsDEuWLMFTTz0lOg5RLSZXfAAwbe1RpP5w/a4nttRHoQBC+njiX5MebflgzVRTU4Pi4uK7FuQff19SUgIXFxejR5hOTk5cvyThzpw5g5CQELzxxhuIjY0VHYfoDpMsvvpObmkqSzq5xWAw4ObNm0aPMCsqKhotyIYKlOuX1NJ++uknBAcH46WXXsKcOXNExyECYKLFB/z+rM6mb22ws1YiPrQ3Jg3p3HrBzEBFRUWTCvKPv1cqlU2+yOe3X93c3HiDUmrUxYsXERQUhGeffRavvPKK6DhEplt8gBF3Z1AAapUV4kO9ZV96zSVJEsrKyowqy98uDrK3tzd6hOnq6sr1Sxm5cuUKgoODMXbsWCxYsIBT8SSUSRcfAJzKu4WEjByk/5gPBX7dnP6b3+7HF9BLgzj/7hYxvWluflu/vNto8o/PFxcXw8XFxegRprOzM/+naaby8/MxYsQI+Pv744MPPuC/RxLG5IvvN4UlFUg+nofsq7dRrK+Cs9oa3h2dEDXQi2dymiGDwYBbt241aYT5+9GlXq+/M8VqzAU/9vb2or9lAnDz5k2MGjUKAwYMwIoVK6BU1j41saCkAsnH8pB9rRjFegOc1Sp4d3BG9CP8c04tx2yKjwj43/qlsWuYCoXC6OlYrl+2jtu3byM8PBz3338/Vq9eDZVKhZO/3MLyjBwcOJcPALW2M/02s+PfS4M4v+4Y0IkzO3RvWHxk8SRJQnl5uVFXxv72ezs7O6OmY7l+2TRlZWUYO3YsHB0dEf7CIiza9xPX8qnNsPiIGiBJUq31y6aWZnFxMZydnY2ejpXb+mVFRQVGzVmIXzSPoaqm6d83r96me8XiI2ph1dXVTV6//P3v9Xo92rVr16z9l+ZYmA3t1y3YuRj6CydRU6WHlUM7OA8ZB6cBtc/9tKT9utT2WHxEJqKysrLR82MbekySJKOnY01h/bKhE5oq8y/Cut2foFBZo6rwF1z74lV4RM+HbYfud15jiic0kfkwuUOqieTKxsYGHTp0QIcOHYx6X1lZWYMFqdPpkJ2dXW9pqtVqo6dj27VrZ/T6Za9evTBw4EAsXboUHh4eAH69evPAufx61/RsNA/87u8UUEABw82rtYpPkoD0H/NRWFLBqz3JaBzxEcmQJEm4ffu20Rf7FBUVwcnJyaiy7N27NyRJgo2NDd58803Mnj0bnxy6iCX7zzV40+nCvQkoPZ0GyVABG89u8Jz4DpQ2tY/UU6uUmKvtiem+3driHxlZEBYfETVZdXU1ioqKmjwVW1BQgIsXL9b6DHd3d0xanoptJ640+rWkmmpUXM6G/tJpuAyJgsKq7gTVmIfuw5KYh1r0eyTLx6lOImoyKyurOwcI9OjR466vv3r1Kh544IE7G9UfffRRxMXFYb/ecNf3KpRWUHfqi9Kz6bj9XQqcH32izmuK9VXGfxMkeyw+Imo1SqUS9913HyZMmIC4uDjcd999AIAjG75r+ofU1MBw82q9TzmreYNnMh6Lj4hajaenJ3Jzc+s87t3BGbaqa3XW+KpLb0F/8STsuj8GhcoG+gsnUPrDAbSPeLnOZ6hVSnh3dGq17GS5WHxE1OaiHvHCkv3n6j6hUOD2d1+icG8CINVA5eKBdkHPwb7nkDovlQBEDfRq/bBkcVh8RNTm2jvawq+nps4+Pit7F3SY+M5d369Q/HpXFm5loOZQ3v0lREQtb5Z/d6hVzTvTVK2yQpx/97u/kKgeLD4iEmJAJ1fEh3rDztq4/w0pqqtgc3Yn7PUFrZSMLB2Lj4iEmTSkM+JDe8PO2gp3O25Uofj1jM4Xg7rg1JYE9OjRA/fddx/mzJmD9PT0tglMFoEb2IlIuFN5t5CQkYP0H/OhAKCv5358Ab00iPPvjv5eroiJicHGjRsBAAqFAiqVCpcvX4ZGoxHzDZBZYfERkckoLKlA8vE8ZF+9jWJ9FZzV1vDu6ISogbXvwH7kyBEEBASgrKwMALBq1SpMmTJFVGwyMyw+IjI7kiThgQcewLVr1+Dm5oaSkhJ89913TTpNhohrfERkdhQKBRYtWoQlS5bgypUr6Nu3L/r164ejR4+KjkZmgCM+IrIIoaGhSE1NRUpKCrRareg4ZMI44iMii5CSkoKJEydi5MiRSEpKEh2HTBhPbiEii7FmzRp4eHhg4sSJKCgowJw5c0RHIhPE4iMii/Luu+9Co9Hg+eefh06nw4IFC0RHIhPD4iMii/Pyyy/Dw8MDU6dOxfXr15GYmCg6EpkQFh8RWaRnnnkG7u7uiIyMRH5+PrZu3So6EpkIXtVJRBYtKysLfn5+GDx4MA4cOHDnbvAkXyw+IrJ4P/zwAx599FF06dIFx48fh42NjehIJBCLj4hkIS8vD/369YOTkxO+//57ODo6io5EgnDMT0Sy4OXlhdzcXBgMBnTu3Bk6nU50JBKExUdEsuHq6oqff/4Zbm5u6NatG86fPy86EgnA4iMiWVGr1cjOzkavXr3Qt29fHD9+XHQkamMsPiKSHaVSiSNHjsDf39jh48YAAAoZSURBVB+DBw9GWlqa6EjUhlh8RCRLSqUSe/bsQUxMDEaMGHHnxrZk+biBnYhk7fPPP4enpyfGjx8PnU6H2bNni45ErYzFR0Sy9/7770Oj0eAvf/kLCgoKMH/+fNGRqBWx+IiIALzyyivQaDSYNm0adDodEhISREeiVsLiIyL6r9jYWGg0GowdOxbXr1/H5s2bRUeiVsCTW4iI/uDQoUMICAjA0KFDkZ6ezvM9LQyLj4ioHmfPnsWgQYPQvXt3HD9+HCoVJ8gsBYuPiKgBly5dQv/+/eHq6oozZ87wfE8LwfE7EVED7r//fvz888+oqKhA165dUVBQIDoStQAWHxFRI9zc3JCbmwsnJyd07doVubm5oiPRPWLxERHdhVqtxo8//oju3bujT58+OHHihOhIdA9YfERETaBSqXD06FH4+Phg0KBByMjIEB2JmonFR0TUREqlEqmpqYiOjkZQUBCSk5NFR6JmYPERERnpiy++wOzZs/Hkk09ixYoVouOQkbgxhYioGZYuXQoPDw/MmjULOp0O//jHP0RHoiZi8RERNVN8fDw8PT3vnO+5fPly0ZGoCVh8RET34Nlnn4W7uzuioqKQn5/P+/qZAZ7cQkTUAjIzMxEcHAwfHx/s37+f53uaMBYfEVELOXPmDAYNGoSePXvi2LFjPN/TRLH4iIha0MWLF9G/f3+4ubnh7NmzsLe3Fx2J/oDFR0TUwgoKCtC3b19IkoTvv/8e7du3Fx2JfoeT0ERELax9+/bIzc2Fo6MjunXrhosXL4qORL/D4iMiagX29vY4d+4cunTpAm9vb5w6dUp0JPovFh8RUStRqVQ4fvw4hg0bhkceeQSZmZmiIxFYfERErUqpVCItLQ3jxo1DQEAANm/eLDqS7LH4iIjawPr16xEXF4fo6GgkJiaKjiNr3GRCRNRGPvroI3h6emLGjBnIz89HfHy86EiyxOIjImpDr7/+OjQaDWbOnInr169j2bJloiPJDouPiKiNTZ8+He7u7oiJiUF+fj6SkpJER5IVbmAnIhIkIyMDWq0Wvr6+SE1N5fmebYTFR0Qk0IkTJzB06FB4e3vjP//5D8/3bAMsPiIiwXJzczFgwABoNBqcPn2a53u2MhYfEZEJKCgoQJ8+faBUKvH999/Dzc1NdCSLxQllIiIT0L59e1y4cAFqtRpdunTBpUuXREeyWCw+IiITYW9vj5ycHDzwwAPw9vbGmTNnREeySCw+IiITolKpcOLECQwePBgDBw7EwYMHRUeyOCw+IiITo1QqkZ6ejieeeAL+/v7YunWr6EgWhcVHRGSikpOTMW3aNIwbNw6ffPKJ6DgWgxtGiIhMWEJCAjw8PDBt2jTk5+fj1VdfFR3J7LH4iIhM3Pz58+Hh4YHZs2dDp9NhyZIloiOZNRYfEZEZiIuLg4eHB2JiYqDT6bBu3TrRkcwWN7ATEZmRr776CiEhIQgICMCePXt4vmczsPiIiMzM8ePHMWzYMDz44IM4fPgwz/c0EouPiMgM5ebmon///vD09MSZM2egVqtFRzIbLD4iIjOl0+nQt29fqFQqnD17lud7NhEnh4mIzJSHhwdyc3NhY2ODrl278nzPJmLxERGZMUdHR/z000/w8vKCt7c3zp49KzqSyWPxERGZORsbG5w6dQqDBg3Cww8/jEOHDomOZNJYfEREFkCpVOLAgQOIiIiAn58fduzYITqSyWLxERFZkM2bN+O5557DmDFjsHr1atFxTBI3fxARWZgVK1ZAo9EgNjYW+fn5mDdvnuhIJoXFR0Rkgd544w1oNBo8//zzuH79Ot5//33RkUwGi4+IyELNmTMHHh4emDBhAvLz8/HZZ5+JjmQSWHxERBYsJiYGbm5uCA0NhU6nQ0pKiuzP9+TJLUREMnD06FH4+PigX79++Pbbb2Vdfiw+IiKZOH/+PB566CF07NgRp06dku35niw+IiIZ0el06NOnD2xsbPD999/D1dVVdKQ2J9+xLhGRDHl4eODChQtQqVTo0qUL8vLyREdqcyw+IiKZcXR0RE5ODjp27IhevXrhhx9+EB2pTbH4iIhkyMbGBmfOnMHDDz+MAQMGICsrS3SkNsPiIyKSKaVSiYMHDyI0NBTDhw/Hrl27REdqEyw+IiKZ27ZtG6ZMmYLRo0fj008/FR2n1XEDOxERYeXKlfDw8MCUKVOg0+nw8ssv4+DBg2jfvj28vb1Fx2tRLD4iIgIALFy4EB4eHpg7dy6OHz+O5ORkBAYGYu/evaKjtSju4yMiolrefvttvPbaawAAW1tb5OXloX379oJTtRwWHxER3aHT6dCjRw8UFxcD+PUCmMWLF2Pu3Lm1XldQUoHkY3nIvlaMYr0BzmoVvDs4I/oRL7g72oqI3mQsPiIiuqOkpATz58/H5s2bceXKFVRWVsLW1hbl5eVQKBQ4+cstLM/IwYFz+QCACkPNnfeqVUpIAPx7aRDn1x0DOpnmqTAsPiIiqldeXh7WrFmDt99+GzNmzMDD0XOwMCUbekM1GmsOhQJQq6wQH+qNSUM6t1nepmLxERFRo0pKSrBo8zdIPl+N8qqau7/hv+yslYgP7W1y5cd9fERE1KjzNw1IPl/TYOlV3biMi++NQcHOxbUeL6+qwcKUbJzKu9UWMZuMxUdERI1anpEDvaG6wedv7PsXbDv2qPc5vaEaCRk5rRWtWVh8RETUoIKSChw4l9/gml7p9wegVDtA/cCAep+XJCD9x3wUllS0YkrjsPiIiKhByccavm1RTUUZbn29Du0CYxv9DAWA5OOmc/sjFh8RETUo+1pxrS0Lv3crcy0cB4yAylnT6GfoDTXIvnq7NeI1C4uPiIgaVKw31Pt45fWfob94Es6DRjfxc6paMtY94VmdRETUIGd1/TWhv3QahqLryEuYAgCQKvWAVIOrBc+j45Sl9XyOdavmNAaLj4iIGuTdwRm2qmt1pjsdHwqBQ2/fO39ffGQLDEXX4RYyq85nqFVKeHd0avWsTcWpTiIialDUI171Pq60VsPKsd2dvxTWaihUNrCyd6nzWglA1MD6P0cEjviIiKhB7R1t4ddTg9Qfrjd6TJnr8In1Pq5QAAG9NCZ1cDVHfERE1KhZ/t2hVlk1671qlRXi/Lu3cKJ7w+IjIqJGDejkivhQb9hZG1cZv57V6Y3+XqZ1lwZOdRIR0V39dtA0785ARESycirvFhIycpD+Yz4U+HVz+m9+ux9fQC8N4vy7m9xI7zcsPiIiMlphSQWSj+ch++ptFOur4Ky2hndHJ0QN5B3YiYiITAovbiEiIllh8RERkayw+IiISFZYfEREJCssPiIikhUWHxERyQqLj4iIZIXFR0REssLiIyIiWWHxERGRrLD4iIhIVlh8REQkKyw+IiKSFRYfERHJCouPiIhkhcVHRESywuIjIiJZYfEREZGssPiIiEhWWHxERCQrLD4iIpKV/wcIFfoBGijQGQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "\n",
    "def cree_graphe_oriente_nx(dictionnaire: dict) -> nx.DiGraph:\n",
    "    \"\"\"\n",
    "    Cette fonction premet de transformer une représentation en dictionnaire en\n",
    "    une représentation «complexe» d'un objet graphe orienté.\n",
    "\n",
    "    - Précondition : l'entrée est un dictionnaire\n",
    "    - Postcondition : la sortie est un graphe orienté (DiGraph) de Networkx\n",
    "    \"\"\"\n",
    "    G = nx.DiGraph()  # pour un graph non oriente :  G = nx.Graph()\n",
    "    for sommets in dictionnaire.keys():\n",
    "        G.add_node(sommets) # Creation des sommets\n",
    "    for sommet in dictionnaire:\n",
    "        for sommets_adjacents in dictionnaire[sommet]:\n",
    "            G.add_edge(sommet, sommets_adjacents) # Creation des arcs\n",
    "    return G\n",
    "\n",
    "\n",
    "gr = {1: [2, 3], 2: [], 3: [2, 4], 4: [3]}\n",
    "G=cree_graphe_oriente_nx(gr)\n",
    "# Pour une representation circulaire : nx.draw_circular(G,with_labels=True)\n",
    "nx.draw(G,with_labels=True) # Pour une representation classique\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XsMJsY5S7ced"
   },
   "source": [
    "**Exercice 2 : Modifier l'implémentation pour modéliser un graphe non orienté (primitives d'ajout)** \n",
    "\n",
    "Vous allez modifier notre première implémentation pour modéliser un graphe non orienté.\n",
    "\t\n",
    "\n",
    "  Dans la version d'implémentation fournie ci-dessous, on a remplacé la primitives ajouterArc par ajouterArete, mais on a pas modifié le code de cette primitive. Vous devez le faire vous même : dans le cas d'un graphe non orienté, ajouter une arrête SD-SA revient à ajouter SD dans la liste d'ajacence de SA, et SA dans la liste d'adjacence de SD. Le code doit donc faire le travail correctement.\n",
    "\n",
    "  Dans cet exercice nous n'incluerons que les primitives d'ajout de sommets et d'arêtes, les primitives pour retirer seront traitées dans un second temps.  \n",
    "  \n",
    "  Compléter également la fonction existeArete\n",
    "\n",
    "En modifiant l'implémentation de l exemple précédant, créez le dictionnaire G correspondant au graphe ci-dessous.Les instructions données en fin de code devraient afficher le dictionnaire correct, si vos primitives ont été modifiées comme attendu.\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Ungerichteter_Graph_mit_4_Knoten_und_3_Kanten.svg/220px-Ungerichteter_Graph_mit_4_Knoten_und_3_Kanten.svg.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3gCVKTmu8GNF"
   },
   "outputs": [],
   "source": [
    "def  creerGrapheVide() -> dict:\n",
    "     return {}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G.keys(),'vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArete(G : dict , sd , sa ) -> dict : #sa et sd peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G ,'le graphene contient pas le sommet d arrivee'\n",
    "    G[sd].append(sa)\n",
    "    #completer\n",
    "\n",
    "def existeSommet(G : dict , s ) -> bool:\n",
    "    return s in G\n",
    "def existeArete(G : dict , sd  , sa ) -> bool: #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G and sa in G[sd] # completer\n",
    "\n",
    "G=creerGrapheVide()\n",
    "# complétez ici\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Correction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3gCVKTmu8GNF"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: [2], 2: [1, 3, 4], 3: [2], 4: [2]}\n"
     ]
    }
   ],
   "source": [
    "def  creerGrapheVide() -> dict:\n",
    "     return {}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G.keys(),'vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArete(G : dict , sd , sa ) -> dict : #sa et sd peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G ,'le graphe ne contient pas le sommet d arrivee'\n",
    "    G[sd].append(sa)\n",
    "    G[sa].append(sd)\n",
    "def existeSommet(G : dict , s ) -> bool:\n",
    "    return s in G\n",
    "\n",
    "\n",
    "G=creerGrapheVide()\n",
    "for i in range(1,5):\n",
    "    ajouterSommet(G,i)\n",
    "ajouterArete(G,1,2)\n",
    "ajouterArete(G,2,3)\n",
    "ajouterArete(G,2,4)\n",
    "print(G)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visualiser un graphe non orienté**  \n",
    "De même que précédemment, la bibliothèque networkx permet de visualiser un graphe non orienté."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: [2], 2: [1, 3, 4], 3: [2], 4: [2]}\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3de1DU9/3v8dfCoqBIUINKkIpIdBUFEYymJNFcfiHj1B47jSU9SU6bnFa8JUabTJqYTpvmappL0zQqaU9nOml/EUpiNI0nNqma2KZGAREBbyRekItHIIig4O7yPX+k2m5BRNzd7+5+n48Z/8jusr4yo7x8v/l8v2szDMMQAAAWEWZ2AAAA/IniAwBYCsUHALAUig8AYCkUHwDAUig+AIClUHwAAEuh+AAAlkLxAQAsheIDAFgKxQcAsBSKDwBgKRQfAMBSKD4AgKXYzQ4AAL1pbOtUUclx7W9oVWuHSzGRdjlGxWh+5mgNjx5odjwEIRufxwcgEO2padHr26r18cGTkqROV9eF5yLtYTIkzZ4Qp8WzUpSeGGtSSgQjig9AwPnDjiN6ZtN+dbjc6u07lM0mRdrDtXKOQ/fMTPJbPgQ3Vp0AAspXpbdPZ51dl3ytYUhnnW49s2mfJFF+6BMmPgABY09Ni+76zQ6ddbo9Hm9870V1HNmjLmeHwgcPVczMb2tIeo7Ha6IiwlWwYKbSRrP2RO8oPgABY8Gbxfpw34lu681zJ48qYug1stkj5GyqUcN/P6YR83+mgaNSLrzGZpNyJo3U2nuy/JwawYbLGQAEhMa2Tn188GSPP9MbEDdGNnvEP//LJptscn1Z7/Eaw5C2HjipprZO34dFUONnfAACQlHJ8V6fb9q8Wu17/yrD1akBI8cpalz3yc4mqaj0uPJuGuejlAgFFB+AgLC/odXjkoX/NDxnsYb9V546a/er49he2cIjur2mw9Wl/fWnfRkTIYBVJ4CA0NrhuuRrbGHhikxMlft0o07v3nSR93F6OxpCDMUHICDERF7GAqqrq9vP+P71Pt0nQeDfUXwAAoJjVIwG2rt/S3K3t6i96mN1nTsro8uts1+UqH3fx4ock97ttZH2MDnih/gjLoIYP+MDEBDuzBytVz462P0Jm02nd/9fNW1eLRldsl81QkNv/aEGjZ/Z7aWGpDunjfZ9WAQ1ig9AQLg6eqBmjY/rdh1f+KCrNOru5y/59TabdPOEOG5cjUti1QkgYCyZnaJIe3i/vjbSHq7Fs1Mu/UJYHsUHIGCkJ8Zq5RyHoiIu71tTVESYVs5xcLsy9AmrTgAB5fyNpp/ZtF8dTrd6u6cin86A/uBenQACUvnxFt3/UoG+jLxGEXa7Onr4PL6bJ8Rp8ewUJj1cFooPQEDq7OxUfHy8Ptm5W3+vc2l//Wm1djgVExkhR/wQ3TmNT2BH/7DqBBCQNm/erLS0NE1OGaPJnFmBF3G4BUBAWrdunXJzc82OgRDEqhNAwGlvb1dCQoIOHjyoESNGmB0HIYaJD0DAef/99zVjxgxKDz5B8QEIOAUFBbrrrrvMjoEQxaoTQEBpbW1VYmKijh49qthYLlOA9zHxAQgoGzZs0KxZsyg9+AzFByCgrFu3jjUnfIpVJ4CA0dTUpOTkZNXW1io6OtrsOAhRTHwAAsb69euVk5ND6cGnKD4AAYOL1uEPrDoBBISGhgY5HA7V19crKirK7DgIYUx8AAJCUVGR5s6dS+nB5yg+AAGBi9bhL6w6AZiupqZGGRkZqqur04ABA8yOgxDHxAfAdIWFhZo3bx6lB7+g+ACYjovW4U+sOgGYqrq6WtnZ2aqtrZXdzmdjw/eY+ACYqrCwUPPnz6f04DcUHwBTcdE6/I3iA2CayspKNTc3Kzs72+wosBCKD4BpCgoKlJubq7AwvhXBf/jTBsAUhmFw0TpMQfEBMEVZWZlcLpeysrLMjgKLofgAmOL8oRabzWZ2FFgM1/EB8DvDMDR27Fht3LhRaWlpZseBxTDxAfC7zz77TIMGDdKUKVPMjgILovgA+N35W5Sx5oQZWHUC8Cu3263ExERt3bpVEyZMMDsOLIiJD4Bfbd++XSNHjqT0YBqKD4Bf8UkMMBurTgB+43Q6lZCQoJ07dyopKcnsOLAoJj4AfrNlyxYlJydTejAVxQfAb1hzIhCw6gTgF52dnYqPj9fevXuVkJBgdhxYGBMfAL/YvHmz0tLSKD2YjuID4BesOREoWHUC8Ln29nYlJCTo0KFDiouLMzsOLI6JD4DPvf/++5oxYwalh4BA8QHwOdacCCSsOgH4VGtrqxITE3X06FHFxsaaHQdg4gPgWxs2bNCsWbMoPQQMig+AT7HmRKBh1QnAZ5qampScnKza2lpFR0ebHQeQxMQHwIfWr1+vnJwcSg8BheID4DPr1q1Tbm6u2TEAD6w6AfhEQ0ODHA6H6uvrFRUVZXYc4AImPgA+UVRUpLlz51J6CDgUHwCfKCgo4DQnAhKrTgBeV1NTo4yMDNXV1WnAgAFmxwE8MPEB8LrCwkLNmzeP0kNAovgAeB0XrSOQseoE4FXV1dXKzs5WbW2t7Ha72XGAbpj4AHhVYWGh5s+fT+khYFF8ALyKi9YR6Cg+AF5TWVmp5uZmZWdnmx0FuCiKD4DXFBQUKDc3V2FhfGtB4OJPJwCvMAyDi9YRFCg+AF5RVlYml8ulrKwss6MAvaL4AHjF+UMtNpvN7ChAr7iOD8AVMwxDY8eO1caNG5WWlmZ2HKBXTHwArthnn32mQYMGacqUKWZHAS6J4gNwxc7foow1J4IBq04AV8TtdisxMVFbt27VhAkTzI4DXBITH4Arsn37do0cOZLSQ9Cg+ABcET6JAcGGVSeAfnM6nUpISNDOnTuVlJRkdhygT5j4APTbli1blJycTOkhqFB8APqNNSeCEatOAP3S2dmp+Ph47d27VwkJCWbHAfqMiQ9Av2zevFlpaWmUHoIOxQegX1hzIlix6gRw2drb25WQkKBDhw4pLi7O7DjAZWHiA3DZ3n//fc2YMYPSQ1Ci+ABcNtacCGasOgFcltbWViUmJuro0aOKjY01Ow5w2Zj4AFyWDRs2aNasWZQeghbFB+CysOZEsGPVCaDPmpqalJycrNraWkVHR5sdB+gXJj4AfbZ+/Xrl5ORQeghqFB+APlu3bp1yc3PNjgFcEVadAPqkoaFBDodD9fX1ioqKMjsO0G9MfAD6pKioSHPnzqX0EPQoPgB9UlBQwGlOhARWnQAuqaamRhkZGaqrq9OAAQPMjgNcESY+AJdUWFioefPmUXoICRQfgEvionWEEladAHpVXV2t7Oxs1dbWym63mx0HuGJMfAB6VVhYqPnz51N6CBkUH4BecdE6Qg3FB+CiKisr1dzcrOzsbLOjAF5D8QG4qIKCAuXm5iosjG8VCB38aQbQI8MwuGgdIYniA9CjsrIyuVwuZWVlmR0F8CqKD0CPzh9qsdlsZkcBvIrr+AB0YxiGkpKS9N577yktLc3sOIBXMfEB6GbHjh0aPHiwpkyZYnYUwOsoPgDdnD/UwpoToYhVJwAPbrdbiYmJ2rp1qyZMmGB2HMDrmPgAeNi+fbtGjhxJ6SFkUXwAPPBJDAh1rDoBXOB0OpWQkKCdO3cqKSnJ7DiATzDxAbhgy5YtSk5OpvQQ0ig+ABew5oQVsOoEIEnq7OxUfHy89u7dq4SEBLPjAD7DxAdAkrR582alpaVRegh5FB8ASaw5YR2sOgGovb1dCQkJOnTokOLi4syOA/gUEx8Avf/++5oxYwalB0ug+ACw5oSlsOoELK61tVWJiYk6evSoYmNjzY4D+BwTH2BxGzZs0KxZsyg9WAbFB1gca05YDatOwMKampqUnJys2tpaRUdHmx0H8AsmPsDC1q9fr5ycHEoPlkLxARbGmhNWxKoTsKiGhgZNnDhRdXV1ioqKMjsO4DdMfIBFFRUV6Rvf+AalB8uh+ACLYs0Jq2LVCVhQTU2NMjIyVFdXpwEDBpgdB/ArJj7AggoLCzVv3jxKD5ZE8QEWxJoTVsaqE7CY6upqZWdnq7a2Vna73ew4gN8x8QEWU1hYqPnz51N6sCyKD7CYdevWKTc31+wYgGkoPsBCKisr1dzcrOzsbLOjAKah+AALKSgoUG5ursLC+KsP6+JPP2ARhmGooKCA05ywPIoPsIiysjK5XC5lZWWZHQUwFcUHWMT5Qy02m83sKICpOM8MhKDGtk4VlRzX/oZWtXa4FBNp1/o9jfrDz5eaHQ0wHRewAyFkT02LXt9WrY8PnpQkdbq6/vWk65wGRkZq9oQ4LZ6VovTEWJNSAuai+IAQ8YcdR/TMpv3qcLnV299qm02KtIdr5RyH7pmZ5Ld8QKBg1QmEgK9Kb5/OOrsu+VrDkM463Xpm0z5JovxgOUx8QJDbU9Oiu36zQ2ed7guPGS6nmv6yWh1HytTV0SZ7bLyGzvpfihrneaIzKiJcBQtmKm00a09YB6c6gSD3+rZqdbjcHo8ZXW7Zh1ytUf/zeSUuL1DsTffo5IZVcrWc8Hhdh8ut1duq/RkXMB3FBwSxxrZOfXzwZLef6YUNiFTsjXfLHjtSNluYBqVcJ/tVI9XZ4FlyhiFtPXBSTW2dfkwNmIviA4JYUcnxPr3O3f6lnM21GhD3tW7P2SQVlfbtfYBQQPEBQWx/Q6vnJQs9MNwuNW58UdFTblXE8MRuz3e4urS//rSvIgIBh+IDglhrh6vX5w2jS41/fkkKt2vYfy3s5X2c3o4GBCwuZwCCUF1dnYqLi3X4wJeSru7xNYZhqGnTr+Rub9GI+T+TLfzif91jIiN8lBQIPBQfEOBOnjypkpIS7dq1S8XFxSouLlZnZ6emT5+u2Iy5stuGy2V0v/9m8+bX5Wyq0ci7nlZYxMCLvn+kPUyO+CG+/F8AAgrX8QEBpKWlRSUlJRcKbteuXWppaVFWVpbHrzFjxshms6mxrVPZq7Z0+zmf69T/U+2a+6XwCNnCwi88PuyOJYpOvdnjtQPtYfr00Vs0PPri5QiEEooPMElbW5t2797tMcnV19crIyNDWVlZmj59urKysjRu3LhePzh2wZvF+nDfiV5vU3YxNhm6PXWU8u/ho4pgHRQf4Adnz57Vnj17PCa5I0eOaMqUKRcKLisrSw6HQ+Hh4Zd+w3/T051b+sx1TmO/eFe/e/FnGjt27OV/PRCEKD7Ay86dO6eKigqPSe7AgQOaOHHihYKbPn26UlNTFRHhnUMll3OvzvOiIsL06O3jVb+9UC+++KIeffRRLV++3GuZgEBF8QFXwOVyad++fR6TXGVlpZKTkz0mubS0NEVGRvo0y5V8OsPnn3+uxYsXq76+Xvn5+br++ut9mhUwE8UH9FFXV5cOHTrkMcmVlZVp9OjRHpPc1KlTNXjwYFMylh9v0ept1dp64KRs+uri9PMi7WEyJN08IU6LZ6d0uzG1YRhat26dVqxYoXnz5um5555TbCw3r0boofiAHhiGocOHD3tMcqWlpRo+fLjHJDdt2jRdddVVZsftpqmtU0Wlx7W//rRaO5yKiYyQI36I7pw2+pKnN7/88ks99thj2rhxo1555RV95zvfkc3W/XIJIFhRfLA8wzBUW1vrMckVFxdr0KBBHpNcZmamhg8fbnZcv/n000+Vl5enhIQErV69WsnJyWZHAryC4oPlnDhxwmOSKy4ulmEYHpNcVlaWRo0aZXZU0zmdTr388st64YUX9Mgjj+hHP/oRh18Q9Cg+hLTm5maPKa64uFhtbW0ek1xWVpZGjx7NOq8XX3zxhZYsWaKamhrl5+crOzvb7EhAv1F8CBmtra0qLS31mOROnjypzMxMj0kuOTmZkusHwzD0pz/9SQ899JDmzp2r559/XkOHDjU7FnDZKD4EpTNnzqisrMzj53I1NTVKT0/3mObGjx/f611PcPlaWlr0+OOPa/369Xr55Zd111138Q8JBBWKDwGvs7NT5eXlHpNcdXW1UlNTPX4uN2nSJNnt3HfdX3bs2KG8vDyNHDlSa9as0bhx48yOBPQJxYeA4nQ6VVVV5THJVVVVafz48R6T3OTJkzVwIDdVNpvT6dQvf/lLrVq1SitWrNDDDz+sAQMGmB0L6BXFB9O43W4dOHDAY5IrLy/XmDFjPCa59PR0DRo0yOy46MWRI0e0ZMkSHTlyRPn5+brhhhvMjgRcFMUHvzAMQ59//rnHJLd7926NHDnSY5LLyMjQkCF8NlwwMgxDb7/9tpYtW6Y5c+Zo1apVGjZsmNmxgG4oPnidYRg6duyYx7VyJSUliomJ8ZjkMjMzORUYgk6dOqWVK1eqqKhIL774ou6++24OvyCgUHy4YvX19d3uehIeHn6h5M7f9WTEiBFmR4Uf7dy5UwsWLNDVV1+tNWvW6NprrzU7EiCJ4sNlamxs7HbXk87OTo+LwbOyspSQkGB2VAQAl8ulV199Vc8995weeughPfLIIxxKgukoPlxUS0uLSkpKPIqupaXlwgXh54tuzJgxrLLQq6NHj2rp0qWqrq5Wfn6+brrpJrMjwcIoPkiS2tratHv3bo9Jrr6+XlOnTvWY5FJSUrggHP1iGIbWr1+vBx98UDk5OXrhhRcsddNvBA6Kz4I6OjpUVlbmMckdOXJEU6ZM8Thh6XA4FB4ebnZchJjW1lY98cQTKiws1AsvvKB7772XjQH8iuILcefOnVNFRYXHJHfgwAE5HA6PSS41NZULj+FXu3btUl5enoYOHao1a9Zo/PjxZkeCRVB8IcTlcmnfvn0epysrKiqUnJzsMcmlpaUpMjLS7LiAXC6XXnvtNT3zzDN64IEH9OMf/5jDL/A5ii9IdXV16dChQx6TXFlZmRISEjwOnkydOlXR0dFmxwV6dezYMT3wwAM6cOCA1q5dq9mzZ5sdCSGM4gsChmHo8OHDHpNcSUmJhg8f7jHJTZs2TVdddZXZcYF+e/fdd/XAAw/otttu0y9+8QtdffXVZkdCCKL4AoxhGKqtrfWY5IqLixUVFeUxyWVmZvJNASHp9OnT+slPfqK33npLq1at0ve+9z0Ov8CrKD6TnThxwmOS27Vrl7q6urrd9SQ+Pt7sqIBflZSUaMGCBRoyZIjWrl0rh8NhdiSECIrPj5qbm1VSUuIxyZ0+fbrbXU8SExP5Fy6grw6/vP7663rqqae0ZMkSPfbYYxzMwhWj+HyktbVVpaWlHpPcyZMnNW3aNI+fyyUnJ1NywCUcP35cDz74oCoqKrR27VrdcsstZkdCEKP4vODMmTMqKyvzmOSOHTum9PR0j2lu/PjxXBAOXIGNGzfqgQce0KxZs/TSSy8pLi7O7EgIQhTfZers7FR5ebnHJFddXa3U1FSPSW7SpEmy2+1mxwVCTltbm37605/qzTff1PPPP6/77ruPrQkuC8XXC6fTqaqqKo9JrqqqStdee63HJDdlyhQuugX8rLS0VHl5eRo0aJDWrl2riRMnmh0JQcLvxdfY1qmikuPa39Cq1g6XYiLtcoyK0fzM0RoebV55uN1uHThwwGOSKy8v15gxYzwmufT0dA0aNMi0nAD+xe12a/Xq1XryySe1aNEiPf7444qKijI7FgKc34pvT02LXt9WrY8PnpQkdbq6LjwXaQ+TIWn2hDgtnpWi9MRYn2YxDEOff/65xyS3e/dujRgxwmOSy8jIUExMjE+zALhytbW1WrZsmfbs2aM1a9botttuMzsSAphfiu8PO47omU371eFyq7ffzWaTIu3hWjnHoXtmJnnl9zYMQ8eOHfOY5EpKShQTE3Nhkjt/QfiwYcO88nsCMMd7772npUuX6sYbb9TLL7+sESNGmB0JAcjnxfdV6e3TWWfXpV/8T1ERYVo5Z2K/yq++vr7bXU/CwsI0ffp0j7uejBw58rLfG0Dga2tr05NPPqnf//73evbZZ3X//ffzGZLw4NPi21PTort+s0NnnW6Px1tL3lP73r/q3MkjGjxxlq7+xvJuXxsVEa6CBTOVNvria8/GxkaPSa64uFgdHR0eF4NPnz5d11xzDae+AIspKytTXl6eIiIilJ+fr9TUVLMjIUD4tPgWvFmsD/ed6LbePHPgU8lm09nDpTKc53osPptNypk0UmvvyZIktbS0qKSkxOP2Xs3NzcrMzPQouqSkJEoOgKSvDr/k5+frpz/9qRYsWKAnnniCwy/wXfE1tnUqe9UWj0Ms/+nLT96Uu7Wxx+KTpHB1aVrNO9qz8++qq6tTRkaGxySXkpLCCgPAJdXV1emhhx5SaWmpVq9erdtvv93sSDCRz66wLio5fsXvYRhdis24Q+/8+EdyOBxcEA6gX6655hoVFhZq06ZNysvL0/XXX6+XX35Zo0aNMjsaTOCzcWl/Q2uv015fdNnsih49QZMnT6b0AFyxOXPmqKKiQomJiZoyZYreeOMNdXVd2fcpBB+fFV9rh8tL7+P0yvsAgCQNHjxYq1at0l//+lf97ne/04033qiKigqzY8GPfFZ8MZHemdBiIiO88j4A8O/S0tL06aef6t5779XNN9+sxx57TGfOnDE7FvzAZ8XnGBWjgfae397ocstwnZO63JLRJcN1TkaXu9vrIu1hcsQP8VVEABYXFhamhQsXqry8XIcPH9bkyZP1wQcfmB0LPmbKqc6W7X/Uqb+/5fHYVdnfVeyNd3s8NtAepk8fvcXUe3gCsI4PPvhAixcv1nXXXadXXnlF8fHxZkeCD5hyHV9f/Od1fADgD2fOnNFTTz2l3/72t/r5z3+uvLw8LpsKMabcuaUv+nLnFgDwlYqKCuXl5amrq0v5+flKS0szOxK8xKf/jElPjNXKOQ5FRVzeb/PVvTodlB4A00yePFnbt2/Xfffdp1tvvVWPPvqo2tvbzY4FL/D5/H7PzCStnDNRURHhutSdxGy2rya9/t6gGgC8KSwsTAsWLNDevXtVU1OjyZMna9OmTWbHwhXy2+fxlR9v0ept1dp64KRskjp6+Dy+myfEafHsFCY9AAHpL3/5ixYtWqTMzEz98pe/1DXXXGN2JPSD3z+BvamtU0Wlx7W//rRaO5yKiYyQI36I7pxm7iewA0BfnD17Vk8//bTeeOMN/exnP9PChQsVHh5udixcBr8XHwCEgsrKSuXl5cnpdCo/P19Tp041OxL6iDO6ANAPqamp+uSTT/TDH/5Qt99+ux5++GG1tbWZHQt9QPEBQD+FhYXpBz/4gSoqKnTixAmlpqbqz3/+s9mxcAmsOgHASz766CMtWrRI6enpevXVV5WQkGB2JPSAiQ8AvOS2225TeXm5Jk6cqKlTp+q1116T2335N/CAbzHxAYAP7Nu3T3l5eTp79qzeeOMNZWRkmB0J/8TEBwA+MHHiRG3btk2LFi3SHXfcoRUrVnD4JUBQfADgI2FhYbr//vtVUVGhpqYmTZo0SRs3bjQ7luWx6gQAP9myZYsWLlyo1NRU/epXv1JiYqLZkSyJiQ8A/OSWW25ReXm50tPTlZGRoVdffZXDLyZg4gMAE+zfv18LFy5UW1ub8vPzlZmZaXYky2DiAwATOBwObd26VUuXLtWcOXP00EMP6fTp02bHsgSKDwBMYrPZ9P3vf1+VlZU6deqUJk2apHfffdfsWCGPVScABIht27Zp4cKFmjBhgl577TV97WtfMztSSGLiA4AAMXv2bO3Zs0eZmZmaNm2aXnnlFblcLrNjhRwmPgAIQAcPHtSiRYv05ZdfKj8/X9OnTzc7Ushg4gOAADR+/Hh99NFHWr58uebOnasHH3xQra2tZscKCRQfAAQom82me++9V5WVlWpvb9ekSZP0zjvviEXdlWHVCQBB4pNPPlFeXp5SUlL061//WmPGjDE7UlBi4gOAIHHTTTeprKxMM2bMUGZmpl566SUOv/QDEx8ABKFDhw5p0aJFamxsVH5+vmbMmGF2pKDBxAcAQejaa6/Vhx9+qEceeUTz5s3T0qVLderUKbNjBQWKDwCClM1m0913363KykqdO3dOqamp+tOf/sThl0tg1QkAIeJvf/ub8vLylJSUpNdff11JSUlmRwpITHwAECJuuOEG7d69W9nZ2crKytIvfvELOZ1Os2MFHCY+AAhBn3/+uRYvXqyGhgbl5+dr5syZZkcKGBQfAIQowzC0bt06rVixQt/61rf07LPPKjY21uxYpmPVCQAhymaz6bvf/a6qqqrkdrs1adIkFRQUWP7wCxMfAFjE3//+dy1cuFCjR4/W6tWrNXbsWLMjmYKJDwAsIjs7W6WlpZo9e7amT5+u559/3pKHX5j4AMCCvvjiCy1evFi1tbXKz8/X17/+dbMj+Q3FBwAWZRiGCgsLtXz5cn3zm9/Uc889p6FDh5ody+dYdQKARdlsNuXm5qqqqkphYWFKTU3VW2+9FfKHX5j4AACSpH/84x/Ky8tTfHy8Vq9erXHjxpkdySeY+AAAkqTrr79eJSUluvXWW3Xdddfp2Wef1blz58yO5XVMfACAbg4fPqylS5fqyJEjys/P1w033GB2JK+h+AAAPTIMQ2+//baWLVumOXPmaNWqVRo2bJjZsa4Yq04AQI9sNpvuvPNOVVVVaeDAgUpNTdUf//jHoD/8wsQHAOiTzz77THl5eYqLi9OaNWuUkpJidqR+YeIDAPTJjBkzVFxcrDvuuEMzZ87U008/HZSHX5j4AACX7ejRo1qyZIm++OILrV27VjfddNMlv6axrVNFJce1v6FVrR0uxUTa5RgVo/mZozU8eqAfUn+F4gMA9IthGHrnnXe0bNky5eTk6IUXXtDw4cO7vW5PTYte31atjw+elCR1urouPBdpD5MhafaEOC2elaL0RN9/bBKrTgBAv9hsNn37299WVVWVBg8erNTUVL355pseh1/+sOOI7vrNDn2474Q6XV0epSdJHf987C9VJ3TXb3boDzuO+D43Ex8AwBt27dqlvLw8DR06VGvWrNHO5gF6ZtM+nXV2XfqL/ykqIkwr50zUPTOTfJaT4gMAeI3L5dJrr72m5/L/W0O+9RO5Fd7j65zNtar7P0s12JGtq+c+7PFcVES4ChbMVNpo36w9WXUCALzGbrdr+fLlylnxktyG7aKva/7LWg2Mv7bH5zpcbq3eVu2riBQfAMC7Gts6tbOmXbL1XDHtVYLMvLMAAAIHSURBVB8rLHKwIsek9/i8YUhbD5xUU1unT/JRfAAAryoqOX7R57o6z6hl+x819Jb/3et72CQVlV78fa4ExQcA8Kr9Da3dTm+e1/LJm4pOv132mLhe36PD1aX99ad9EY/iAwB4V2uHq8fHz534Qh1H9yhm+v/o4/s4vRnrArtP3hUAYFkxkT1XS8exvXKdOqHjq++TJBnnOiSjS/WNyxR/36s9vE+ET/JRfAAAr3KMitFAe0O3dWf01BwNnvivW5u17nxHrlMnNCxnSbf3iLSHyRE/xCf5WHUCALzqzszRPT4eFhGp8OihF37ZIiJlsw9Q+KCrur3WkHTntJ7f50ox8QEAvOrq6IGaNT5OH+47od5ukRJ74909Pm6zSTdPiPPZjauZ+AAAXrdkdooi7T3fteVSIu3hWjzbd5/1R/EBALwuPTFWK+c4FBVxeTXz1b06HT67XZnEqhMA4CPnbzT9zKb96nC5e1172mxfTXor5zh8eoNqiZtUAwB8rPx4i1Zvq9bWAydl01cXp593/vP4bp4Qp8WzU3w66Z1H8QEA/KKprVNFpce1v/60WjuciomMkCN+iO6cxiewAwDgMxxuAQBYCsUHALAUig8AYCkUHwDAUig+AIClUHwAAEuh+AAAlkLxAQAsheIDAFgKxQcAsBSKDwBgKRQfAMBSKD4AgKVQfAAAS/n/GJ1N8MNsvqQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def cree_graphe_non_oriente_nx(dictionnaire: dict) -> nx.Graph:\n",
    "    \"\"\"\n",
    "    Cette fonction premet de transformer une représentation en dictionnaire en\n",
    "    une représentation «complexe» d'un objet graphe orienté.\n",
    "\n",
    "    - Précondition : l'entrée est un dictionnaire\n",
    "    - Postcondition : la sortie est un graphe orienté (Graph) de Networkx\n",
    "    \"\"\"\n",
    "    Gnx = nx.Graph() \n",
    "    for sommets in dictionnaire.keys():\n",
    "        Gnx.add_node(sommets) # Creation des sommets\n",
    "    for sommet in dictionnaire.keys():\n",
    "        for sommets_adjacents in dictionnaire[sommet]:\n",
    "            Gnx.add_edge(sommet, sommets_adjacents) # Creation des arcs\n",
    "    return Gnx\n",
    "\n",
    "G=creerGrapheVide()\n",
    "for i in range(1,5):\n",
    "    ajouterSommet(G,i)\n",
    "ajouterArete(G,1,2)\n",
    "ajouterArete(G,2,3)\n",
    "ajouterArete(G,2,4)\n",
    "print(G)\n",
    "G1=cree_graphe_non_oriente_nx(G)\n",
    "# Pour une representation circulaire : nx.draw_circular(G,with_labels=True)\n",
    "nx.draw(G1,with_labels=True) # Pour une representation classique\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "3TbSjZiF8Un_"
   },
   "source": [
    "**Exercice 3 : Modifier l'implémentation pour modéliser un graphe non orienté (primitives de suppression)** \n",
    "\n",
    "Vous allez compléter l'implémentation pour modéliser un graphe non orienté.\n",
    "\t\n",
    "\n",
    "  Comme dans l'exercice 2 ci-dessus, dans la version d'implémentation fournie ci-dessous, on a remplacé la primitive supprimerArc par supprimerArete, mais on a pas modifié le code de cette primitive. Vous devez le faire vous même : dans le cas d'un graphe non orienté, supprimer une arrête SD-SA revient à modifier les listes d'adjacence des deux sommets SD et SA. Le code doit donc faire le travail correctement.\n",
    "  \n",
    "  Dans cet exercice nous n'incluerons que les primitives de suppression, nous allons générer pour vous un objet graphe qui sera utilisé pour tester votre code. Vous devez coder supprimerSommet et supprimerArete et utiliser ces 2 primitives pour supprimer le sommet 'A' et l’arête 'B-C' du graphe généré par le système.\n",
    "\n",
    "Modifiez les primitives supprimerSommet et supprimerArete. Puis utilisez les pour supprimer le sommet A et l'arrête B-C du graphe suivant :\n",
    "\n",
    "**G={'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B','D'], 'D': ['B','C']}**\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "hQm-aZvc9Lbc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B', 'D'], 'D': ['B', 'C']}\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3de1iUdf4+8HsOwABCeCBEsUVBQSlSaVOD8oAKYZkHMFNMc1VWFFF3y1r126ZZ1loxqWS7paX9TIw8IognDmqpKaKpHMRDyaZ5ROQwA8PM7w+DFUEFZOYzM8/9uq69LoKBvTHj5v2Z53mPzGAwGEBERCQRctEBiIiITInFR0REksLiIyIiSWHxERGRpLD4iIhIUlh8REQkKSw+IiKSFBYfERFJCouPiIgkhcVHRESSwuIjIiJJYfEREZGksPiIiEhSWHxERCQpLD4iIpIUpegAVNvVEi0SjxQi91IxijU6OKuU8G3rjIgAD7RuYSc6HhGRxZPxhWjNw7ELRVieXoCM/CsAAK1OX/MxlVIOA4B+Pq6I7uuNJzu4CEpJRGT5WHxm4JsD57EoORcaXRXu929DJgNUSgXmhvkisrenyfIREVkTPscn2O3Sy0F5Ze3Su/T/3sSFT16GQVdZ8z6DASivrMKi5Bx8c+C86cMSEVkBFp9Axy4UYVFyLsor9bXeryv6HdrCU4BMhrKCg3U+r7xSj0XJuTheWGSqqEREVoPFJ9Dy9AJodFV13l9yYg/s2vnA8YlglP68u97P1eiqEJ9eYOyIRERWh8UnyNUSLTLyr9T7nF7piT1w9OsHR7/+KD+XharSG3UeYzAAaXlXcK1Ea4K0RETWg8UnSOKRwnrfr7lwErriy3DwDYJdW28oXdxRejKj3sfKACRm1f91iIiofiw+QXIvFde6ZaFa6YndsO/YAwqHRwAAjt36ouTEvY479ci9eMuoOYmIrA1vYBekWKOr8z59pRalufsAvR4XlkbefqeuEnptKSp+Pwtbt071fJ3KOu8jIqJ7Y/EJ4qyq+0dffvoAZDI53Cctg0xhU/P+K5sWo+TEHrSqp/icVTZ13kdERPfGo05BfNs6w05Z+4+/5OfdcHxiIJSPPApFi5Y1/3MKeAGlp9Jh0Ne+AlSllMPX3cmUsYmILB43twhytUSLwA/21Ps8X0PZKeX4Yc4A7vAkImoETnyCtGlhh75dXCGTNe3zZTKgv48rS4+IqJFYfAJN6+cNlVLRpM9VKRWI7ufdzImIiKwfi0+gJzu4YG6YL+xtGvevwd5GjrlhvvD34Ks0EBE1Fq/qFKz6VRYa9OoMAFQ2fHUGIqKHwYtbzMTxwiLEpxcgLe8KZLh9c3o1lVKOSp0OTiW/YvWcsZz0iIgeAovPzFwr0SIxqxC5F2+hWFMJZ5UNfN2dEObbCn/274pdu3bh8ccfFx2TiMhisfgsyIcffoijR4/i22+/FR2FiMhisfgsyK1bt+Dl5YXMzEz4+vqKjkNEZJF4VacFcXJyQmxsLN577z3RUYiILBYnPgtz8+ZNeHt748cff4S3N+/jIyJqLE58FuaRRx7BtGnTOPURETURJz4LdOPGDXh7e+Pw4cPo2LGj6DhERBaFE58FatmyJaZOnYrFixeLjkJEZHE48Vmoq1evokuXLsjOzsZjjz0mOg4RkcXgxGeh2rRpg8mTJ+PDDz8UHYWIyKJw4rNgly9fhq+vL37++We0b99edBwiIovA4rNws2fPhl6vR1xcnOgoREQWgcVn4S5evAg/Pz+cOnUKbdu2FR2HiMjs8Tk+C+fu7o6xY8fio48+Eh2FiMgicOKzAoWFhfD390deXh5cXV1FxyEiMmuc+KyAh4cHXn75ZXzyySeioxARmT1OfFbil19+Qc+ePXH69Gm0atVKdBwiIrPFic9K/OlPf8Lw4cOhVqtFRyEiMmuc+KzImTNn0KtXLxQUFMDFxUV0HCIis8SJz4p4eXlhyJAhWLp0qegoRERmixOflcnLy0NQUBDOnj0LJycn0XGIiMwOJz4r4+Pjg8GDB2P58uWioxARmSVOfFbo1KlT6N+/P86ePQtHR0fRcYiIzAonPivUrVs39O3bFytWrBAdhYjI7HDis1LHjx9HSEgIzpw5AwcHB9FxiIjMBic+K+Xv74/evXvjP//5j+goRERmhROfFcvKysLQoUNRUFAAlUolOg4RkVngxGfFevbsie7du2PlypWioxARmQ1OfFbu4MGDiIiIQEFBAWxtbUXHISISjhOflevVqxe6deuGr7/+WnQUIiKzwIlPAvbv34/IyEjk5+fDxsZGdBwiIqE48UlAYGAgOnXqhG+++UZ0FCIi4TjxSURGRgYmTZqEnJwcKJVK0XGIiIThxCcRffv2hbu7O9atWyc6ChGRUJz4JGTXrl2IiYnBiRMnoFAoRMchIhKCE5+EBAcHo2XLlkhMTBQdhYhIGE58EpOSkoLXX38dx48fh1zO33uISHr4k09iQkNDYW9vj02bNomOQkQkBCc+Cdq6dSvmz5+Po0ePQiaTiY5DRGRSnPgk6IUXXoBMJsPWrVtFRyEiMjkWnwTJZDLMnz8fCxcuBAd+IpIaFp9EDRs2DBqNBtu3bxcdhYjIpFh8EiWXyzFv3jwsWLCAUx8RSQqLT8LCw8NRVFSE3bt3i45CRGQyLD4JUygUmDt3Lt555x1OfUQkGSw+iRs9ejQuXbqEjIwM0VGIiEyCxSdxSqUSc+fOxcKFC0VHISIyCRYfYezYsTh37hz27dsnOgoRkdGx+Ag2NjZ46623OPURkSRwZRkBACoqKtC5c2esX78evXr1Eh2HiMhoOPERAMDW1hZz5szh1EdEVo8TH9XQaDTw9vbG5s2bERAQIDoOEZFRcOKjGiqVCm+88Qbeffdd0VGIiIyGEx/VUl5ejk6dOiE1NRX+/v6i4xARNTtOfFSLvb09/v73v3PqIyKrxYmP6igtLUWnTp2wZ88e+Pn5iY5DRNSsOPFRHY6Ojpg1axYWLVokOgoRUbPjxEf1unXrFry8vLB37174+PiIjkNE1Gw48VG9nJycEBMTg/fee090FCKiZsWJj+6pqKgI3t7eOHjwILy8vETHISJqFpz46J5cXFwwbdo0vP/++6KjEBE1G058dF/Xr19H586dceTIEXh6eoqOQ0T00Djx0X21atUKUVFRWLx4segoRETNghMfPdDVq1fh4+OD7OxsdOjQQXQcIqKHwuKjBnn99deh0WiwdOlS0VGIiB4Ki48a5Pfff0fXrl1x8uRJuLu7i45DRNRkLD5qsFmzZkEmk+Hjjz8WHYWIqMlYfNRgv/32Gx5//HHk5OTAzc1NdBwioibhVZ3UYO3atcOYMWPw0UcfiY5CRNRknPioUS5cuIDu3bsjLy8Pbdq0ER2HiKjROPFRo3To0AHh4eH45JNPREchImoSTnzUaOfPn0dAQABOnz6NVq1aiY5DRNQonPio0Tw9PTFs2DB8+umnoqMQETUaJz5qkoKCAvTu3RtnzpzBI488IjoOEVGDceKjJvH29kZYWBiWLVsmOgoRUaNw4qMmy83NxXPPPYczZ87AyclJdBwiogbhxEdN5uvri+DgYMTHx4uOQkTUYJz46KGcPHkSwcHBOHPmDBwdHUXHISJ6IE589FD8/PwQFBSEzz//XHQUIqIG4cRHDy07OxthYWE4c+YM7O3tRcchIrovTnz00Lp3746nn34aX3zxhegoREQPxImPmsWRI0fw0ksvoaCgACqVSnQcIqJ74sRHzSIgIABPPvkkVq1aJToKEdF9ceKjZnPgwAG8/PLLOH36NGxtbUXHISKqFyc+aja9e/eGj48PVq9eLToKEdE9ceKjZrVv3z68+uqryMvLg42Njeg4RER1cOKjZhUUFARPT0+sXbtWdBQionpx4qNml5aWhqioKJw6dQpKpVJ0HCKiWjjxUbPr168f3NzckJCQIDoKEVEdnPjIKHbu3InY2Fj8/PPPUCgUouMQEdXgxEdGMXDgQDg7O+P7778XHYWIqBZOfGQ0ycnJmDNnDo4dOwa5nL9jEZF54E8jMprnn38ednZ22Lx5s+goREQ1WHxkNDKZDPPnz8fChQvBgwUiMhcsPjKqoUOHQq/XY9u2baKjEBEBYPGRkclkMsybNw8LFizg1EdEZoHFR0Y3YsQIlJaWIjU1VXQUIiIWHxmfXC7H/PnzOfURkVlg8ZFJRERE4Pr169izZ4/oKEQkcSw+MgmFQoG5c+diwYIFoqMQkcSx+MhkXnnlFfz3v/9FRkaG6ChEJGEsPjIZpVKJf/zjH1i4cKHoKEQkYSw+Mqlx48ahoKAAP/zwg+goRCRRLD4yKRsbG059RCQUl1STyWm1WnTu3BmJiYl4+umnRcchIonhxEcmZ2dnhzlz5nDqIyIhOPGREBqNBl5eXkhKSkKPHj1ExyEiCeHER0KoVCq8/vrrnPqIyOQ48ZEwZWVl8PLyQmpqKvz9/UXHISKJ4MRHwjg4OGD27NlYtGiR6ChEJCGc+EiokpISdOrUCenp6ejWrZvoOEQkAZz4SKgWLVpg1qxZnPqIyGQ48ZFwxcXF8PLywv79+9GlSxfRcYjIynHiI+GcnZ0RExOD9957T3QUIpIATnxkFoqKiuDt7Y1Dhw6hU6dOouMQkRXjxEdmwcXFBVOnTsX7778vOgoRWTlOfGQ2rl27hi5duiArKwuOrdsi8Ughci8Vo1ijg7NKCd+2zogI8EDrFnaioxKRBWPxkVmZ8tYiHKtwQ5FDewCAVqev+ZhKKYcBQD8fV0T39caTHVwEpSQiS8biI7PxzYHzeHdbDsordJDJ730KL5MBKqUCc8N8Ednb03QBicgqsPjILHxz4DwWJeegvFL/4Af/wd5GjrlhXVl+RNQoLD4S7tiFIoz+zwGUV1bVvK8wfiL0ZUWATA6ZXAE7j65oFTINSmfXWp9rb6NAwpTe8PfgsScRNQyv6iThlqcXQKOrqvN+1/D/w2N/S4RHzBrIHVxwfefndR6j0VUhPr3AFDGJyEqw+EioqyVaZORfwf3OHWRKWzj6BqLy6q91PmYwAGl5V3CtRGvElERkTVh8JFTikcIHPkZfqUFpzl7YtfOp9+MyAIlZD/46REQAoBQdgKQt91JxrVsW7nTl+3cBuQKGinIoHF3w6KgF9T5Oo9Mj9+ItY8YkIivC4iOhijW6e37MdeQ82Ht2h0FfhfLTB/H72jfRbtJnULRoWc/XqTRmTCKyIjzqJKGcVQ/+3UsmV8DB5xlAJoem8OQ9vo5Nc0cjIivF4iOhfNs6w055/7+GBoMBZfkHoNeUwKZ1hzofVynl8HV3MlZEIrIyPOokocIDPPDJrvx6P3YlcQEgkwMyGZTOrmj9wizYuv6pzuM0Wi1uHduJkp5uaNGihbEjE5GF4w3sJNyUNYex89TvaMpfRJkMCHhUAX3mv5GZmYkJEyZg+vTp8PT0bO6YRGQleNRJwv2pJBd6XdPuw1MpFfi/8N7YsGEDDh8+DAAICAjAyJEjkZmZCf5eR0R3Y/GRMAaDAR988AH+88E8zAjygL1N4/463t7V6VuzrszT0xNLlizBL7/8ggEDBmDy5MkICAjA119/Da2WN7gT0W086iQh9Ho9Zs+ejd27d2P79u1o3779H4uqc6HRVd1/k0sDX51Br9cjNTUVcXFxOHbsGKKiojB16lS0bdu2+b8hIrIYLD4yuYqKCkyYMAGFhYXYsmULXFz+t2D6eGER4tMLkJZ3BTLcvjm9WvXr8fX3cUV0P+9GLabOycnBp59+inXr1uHFF19EbGwsAgICmvG7IiJLweIjk7p16xZGjhwJR0dHrF27Fvb29vU+7lqJFolZhci9eAvFmko4q2zg6+6E8J4P9wrs169fxxdffIFly5bhsccew8yZMzFs2DAolbzAmUgqWHxkMpcvX0ZYWBgCAgKwfPlyoWWj0+mwceNGqNVqXLhwAdOmTcOkSZPQqlUrYZmIyDR4cQuZxNmzZxEYGIghQ4ZgxYoVwicspVKJiIgI7Nu3Dxs2bMCJEyfg5eWFqVOnIicnR2g2IjIuFh8ZXXZ2Np599lnMnj0b77zzDmQymehItQQEBGD16tU4deoUHn30UfTv3x8hISFISUmBXt/wV4QnIsvAo04yqvT0dIwaNQrx8fEIDw8XHadBNBoNEhISEBcXh7KyMsyYMQPjx4/nVhgiK8HiI6NJTExEdHQ0EhIS0L9/f9FxGs1gMGDv3r1Qq9VIT0/Ha6+9xq0wRFaAR51kFPHx8YiNjcWOHTsssvQAQCaT4bnnnsP333+PI0eOALh9LDpixAhkZGRwKwyRheLER83KYDDg7bffxrp165CamoqOHTuKjtSsSkpKsHr1aqjVajg4OCA2NhajR4+GSqUSHY2IGojFR81Gp9Nh2rRpOHLkCJKTk/Hoo4+KjmQ01Vth1Go1srOzuRWGyILwqJOaRXl5OSIiInDu3DmkpaVZdekBgFwux/PPP4/t27cjLS0Nly9fRteuXTFu3LiaY1EiMk8sPnpoRUVFCAkJgb29PZKSkuDkJK0Xhe3atSs+++wznD17Fv7+/hgxYgSCgoLw3XffQafTiY5HRHfhUSc9lN9++w0hISEYOHAgPvroI8jl/F1Kp9Nh06ZNUKvV+PXXX7kVhsjM8KcUNVleXh4CAwMRGRmJjz/+mKX3B6VSifDwcOzdu7fWVpi//vWvOHXqlOh4RJLHn1TUJAcPHkTfvn3x9ttvY86cOWa3jcVcVG+FycnJQdu2bTFgwACEhIQgOTmZW2GIBOFRJzVaSkoKxo8fj1WrVmHIkCGi41gUrVaLdevWQa1Wo7S0lFthiARg8VGjrFmzBq+//jo2btyIPn36iI5jse7eCjNhwgRMnz7d6u57JDJHPOqkBluyZAnmzZuHtLQ0lt5DunsrjFwux1NPPcWtMEQmwImPHkiv1+ONN95ASkoKUlNT4eHhITqSVareCvPpp59CpVJh5syZ3ApDZAQsPrqvyspKTJw4EefOncOWLVt4Sb4J6PV67NixA3FxccjOzsaUKVMwdepUuLu7i45GZBV41En3VFJSghdffBE3b97Ejh07WHomIpfLERoaWrMV5urVq+jWrRvGjRuHw4cPi45HZPFYfFSvq1evIjg4GB4eHtiwYQMcHBxER5Kkrl27Ij4+vmYrzMiRIxEYGIj169dzKwxRE/Gok+o4f/48QkJCEBERgYULF/IePTOi0+mwefNmxMXF4ZdffsG0adMwefJkTuNEjcCJj2o5fvw4goKCMH36dLz77rssPTOjVCoxcuRI7N27F5s2bcKpU6fg5eWFqKgoboUhaiAWH9XIzMzEoEGD8PHHHyMmJkZ0HHqAnj174uuvv0ZOTg7c3d0xYMAADB48mFthiB6AR50EANi4cSOioqLw7bffIjg4WHQcagKtVouEhATExcWhtLQUMTExmDBhArfCEN2FxUf4/PPP8c477yApKQk9e/YUHYceksFgwL59+6BWq5GWlsatMER34VGnhBkMBixYsAD/+te/sHfvXpaelZDJZHj22WeRmJiIrKwsyOVy/PnPf8bw4cO5FYYInPgkq6qqCjExMThw4ABSUlLg5uYmOhIZUWlpac1WGDs7O8TGxuKVV17hVhiSJBafBGk0GkRGRqKoqAgbNmyAs7Oz6EhkItVbYdRqNbKyshAVFcWtMCQ5POqUmJs3byI0NBQKhQLbtm1j6UlM9VaYlJQUZGRk1GyFiYyMxE8//SQ6HpFJsPgk5OLFi+jbty+eeOIJfPvtt7CzsxMdiQTy9fWt2QrTvXt3hIeHcysMSQKPOiXi9OnTCAkJwaRJk/DWW2/xxnSqo3orjFqtxrlz52q2wrRu3Vp0NKJmxYlPAg4fPoy+ffti7ty5+Mc//sHSo3pVb4XJzMzE5s2bkZOTA29vb0RFReHkyZOi4xE1GxaflduxYwfCwsKwYsUK/OUvfxEdhyxE9VaY3NxctGvXDgMHDsTgwYOxbds2boUhi8ejTiu2du1azJo1Cxs2bEBgYKDoOGTBqrfCqNVq3Lp1q2YrjJOTk+hoRI3G4rNScXFx+Pjjj5GSkgI/Pz/RcchKGAwG7N+/H3FxcUhLS8P48eMxffp0dOrUSXQ0ogbjUaeVMRgMePPNN/Hvf/8b+/btY+lRs5LJZAgKCqrZCqNUKvH0009j2LBhSE9P51YYsgic+KxIZWUlJk+ejLy8PCQlJfFqPDKJO7fC2NraIjY2FmPGjOFWGDJbLD4rUVpailGjRkEmkyEhIQGOjo6iI5HE6PV67Ny5E2q1GkeOHMGUKVMwdepUtGvXTnQ0olp41GkFrl27hoEDB8LV1RUbN25k6ZEQcrkcISEhSE5ORkZGBq5fvw4/Pz9uhSGzw+KzcL/++iuCgoLQr18/rFq1CjY2NqIjEcHX1xfLly/HuXPn0KNHD0REROCZZ57B+vXrUVlZKToeSRyPOi3YiRMnEBYWhtmzZ2PmzJmi4xDdk06nw5YtW6BWq3H27FluhSGhOPFZqH379iE4OBiLFy9m6ZHZUyqVGDFiBDIyMrBlyxbk5uZyKwwJw+KzQFu2bMGIESOwZs0ajBkzRnQcokbp0aMHvvrqK+Tm5qJ9+/YYOHAgBg0ahKSkJG6FIZPgUaeF+fLLLzF//nxs2bIFTz31lOg4RA9Nq9Vi/fr1iIuL41YYMgkWn4UwGAx477338OWXXyI1NRWdO3cWHYmoWVVvhVGr1dizZw9effVVxMTEcCsMNTsedVqAqqoqzJgxA9999x3279/P0iOrVL0V5rvvvkNWVhZsbGxqtsKkpaVxKww1G058Zk6r1eLVV1/F5cuXsWnTJjzyyCOiIxGZTGlpKdasWQO1Ws2tMNRsWHxmrLi4GMOHD0erVq2wZs0a/sdOknX3VpjJkycjOjqaW2GoSXjUaaYuXbqEfv36wdfXF+vWrWPpkaTduRUmMzMTN27cgJ+fH8aOHYtDhw6JjkcWhsVnhgoKChAYGIjhw4dj2bJlUCgUoiMRmQ0fH5+arTA9e/bEqFGj0KdPHyQkJHArDDUIjzrNTFZWFl544QX885//xJQpU0THITJ7d2+FiY6OxpQpU7gVhu6JE58Z2b17N0JDQxEfH8/SI2qgu7fC5Ofnw9vbG1OmTMGJEydExyMzxOIzEwkJCRgzZgwSExMxbNgw0XGILFKPHj2watUq5ObmwsPDA4MGDcLAgQO5FYZq4VGnGVi6dCk+/PBDJCcn44knnhAdh8hqVFRU1GyFuXnzJmJiYvDaa69xK4zEsfgEMhgMmDdvHhITE5GamgpPT0/RkYisksFgwA8//AC1Wo3du3dzK4zE8ahTEJ1Oh0mTJmHXrl3Yv38/S4/IiGQyGQIDA7F+/XocPXoUtra23AojYZz4BCgrK8Po0aNRWVmJxMREvmI6kQClpaX45ptvoFarYWNjgxkzZmDMmDGwt7cXHY2MjMVnYtevX8eLL76ITp06YeXKlXzFdCLBDAZDzVaYw4cPcyuMBPCo04QKCwvx7LPP4plnnsHXX3/N0iMyAzKZDIMHD8a2bduQmZmJoqIiPP744xgzZgy3wlgpTnwmkpOTg9DQUMyYMQN/+9vfRMchovsoKirCl19+iWXLlqFt27aIjY3FyJEj+cuqlWDxmcCPP/6I4cOHY8mSJYiMjBQdh4gaqKqqqmYrTEFBAaZNm8atMFaAR51GlpSUhJdeeglfffUVS4/IwigUCgwfPhzp6elISkqq2QozefJkboWxYCw+I/rqq68wefJkbN26FaGhoaLjENFD6N69O1atWoW8vDw89thjNVthtm7dyq0wFoZHnUZgMBjw4YcfYsWKFdi+fTt8fHxERyKiZla9FUatVuPGjRuYMWMGJkyYAGdnZ9HR6AFYfM1Mr9dj9uzZ2LNnD7Zv385Looms3J1bYXbt2lWzFcbLy0t0NLoHHnU2o4qKCkRGRiIrKwuZmZksPSIJuHMrTHZ2NlQqFXr16oWXXnoJe/bs4VYYM8SJr5ncunULI0aMQIsWLbB27VpufyCSsDu3wiiVSsyYMQNjx47lzwUzweJrBpcvX0ZYWBgCAgIQHx/PV0wnIgC3j0F37dqFuLg4/PTTTzVbYdq3by86mqTxqPMhnT17FoGBgXjhhRewYsUKlh4R1ZDJZBg0aBC2bduGffv2obi4GE888QTGjBmDgwcPio4nWZz4HkJ2djaGDBmC+fPn469//avoOERkAYqKirBy5UosXbqUW2EEYfE1UVpaGl5++WV89tlnGDlypOg4RGRhqqqqsHXrVsTFxaGgoADR0dGYMmUK2rRpIzqa1eNRZxMkJiZi9OjRWL9+PUuPiJpEoVBg2LBhNVthCgoK0LlzZ26FMQEWXyPFx8dj5syZ2LFjB/r16yc6DhFZge7du2PlypU1W2EGDx6M4OBgboUxEh51NpDBYMDbb7+NdevWITU1FR07dhQdiYisVEVFBb777jvExcXhxo0biImJwWuvvcatMM2ExdcAOp0O0dHROHr0KJKTk+Hq6io6EhFJgMFgwI8//gi1Wo2dO3dyK0wz4VHnA5SXlyMiIgLnz5/Hnj17WHpEZDIymQzPPPMMEhIScOzYMahUKvTu3RtDhw7lVpiHwInvPoqKijB06FB06NABq1atgq2trehIRCRxZWVlNVth5HI5YmNjuRWmkVh89/Df//4XoaGhGDRoEJYsWQK5nMMxEZmP6q0warUahw4d4laYRuBP83rk5uYiMDAQ48aNw0cffcTSIyKzU70VJikpqdZWmFdeeQUHDhwQHc+sceK7y8GDBzFs2DAsXrwY48ePFx2HiKjBbt68iZUrV+LTTz+Fm5sbYmNjER4ezq0wd2Hx3SElJQXjx4/HqlWrMGTIENFxiIiapHorjFqtRn5+PqKjoxEVFcWtMH/gGd4fVq9ejddeew1btmxh6RGRRaveCpOWlobk5GScOXMGnTt3xqRJk/Dzzz+Ljicciw/AkiVLMH/+fKSlpaF3796i4xARNZsnn3wSK1euRH5+Pjw9PRESEoLg4GBs2bIFVVVVouMJIemjTr1ejzfeeAPbt2/H9u3b4eHhIToSEZFRVW+FUavVuHbtGgqh3PEAAAiVSURBVGbMmCG5rTCSLb7KykpMnDgR586dw9atW9GyZUvRkYiITMZgMODAgQOIi4vDzp07MW7cOMTExMDb21t0NKOTZPGVlJQgPDwcdnZ2WLduHW/8JCJJu3DhAuLj4/HFF1+gT58+iI2NxYABAyCTyRr9ta6WaJF4pBC5l4pRrNHBWaWEb1tnRAR4oHULOyOkbzzJFd+VK1cwZMgQ+Pv7Y8WKFVAqlaIjERGZhYfZCnPsQhGWpxcgI/8KAECr+9+rSqiUchgA9PNxRXRfbzzZwcVY30KDSKr4zp8/j5CQEERERGDhwoVN+m2GiMjaGQwG7N69G2q1GgcPHsSkSZMQHR19z+sgvjlwHouSc6HRVeF+jSKTASqlAnPDfBHZ29M44RtAMld1Hj9+HEFBQYiJicG7777L0iMiugeZTIaBAwdi69at2L9/P0pKSuDv71/vVpjbpZeD8sr7lx4AGAxAeWUVFiXn4JsD5433DTyAJCa+jIwMjBo1CkuXLsWoUaNExyEisjjVW2GWLl0KV1dXxMbGokufQRi36gjKK+veFlF6Mh3FP21C5bVCyG3tYePWCY/0GQVVBz8AgL2NAglTesPfw/THnlZffBs3bkRUVBTWrVuHAQMGiI5DRGTRqqqqkJSUhLi4OJxxHwD5n3oAqH2CVnxoI24eSETrkGlQdewJmUKJ8rNHoL1wEi0HTARw+9gzpJsbVkQ+ZfLvwaqL7/PPP8c777yDpKQk9OzZU3QcIiKrcbVEiz7v70Klvvb79ZpSFC4fj9ZDZsLRN+i+X8NOKccPcwaY/GpPq3yOz2AwYMGCBfjXv/6FvXv3svSIiJpZ4pHCel+5RvtbLgy6Cjh06fPAryEDkJhVaIR092d11/JXVVVh+vTpOHToEPbv3w83NzfRkYiILF5VVRXKy8tRXl6OsrIyHMy7UOuWhZrHlRdD7uAMmVzxwK+p0emRe/GWMeLel1UVn0ajwdixY3Hz5k2kpaVJagUPEUmPwWBAZWUlysrKUFZWVlNKd799v4819O2KigrY29vDwcEBDg4OUPSfBrj71cmksHeGvqwYBn1Vg8qvWFNpjD+a+7Ka4rt58yZeeukluLm5Ydu2bbCzM48NAUQkPXq9vtZ01NCCaUopKRQKODg41CqlhrzdsmXLRj3ezs6u1m1gMxOOYlP2b3W+d7t2vpApbVGW/+MDn+MDAGeV6V8r0CqK7+LFi3j++efx3HPPIS4ujq+YTkT1ash01BwFpdVqoVKp6pTHg0qmZcuWaN++fYNLzN7eXtiLzPq2dYad8lKd4065yhEuz47F9R0rIJMroOrYAzK5Eprz2dD8ehwt+0+seaxKKYevu5Opo1v+VZ35+fkIDQ3F5MmT8eabb/LGdCILYzAYoNFomvVY7l5fC0CtEmrKpNSQt1UqldX/LLpaokXgB3vqfZ4PAEpOpuHWT5tRee0CZLb2sGvrDec+L0Pl0bXmMaKu6rToie+nn37C0KFDsWjRIkycOPHBn0BEDabT6Yz+vFFZWRk0Gg3s7OwaPR05Ozujbdu2jSolUdORNWrTwg59u7hiZ87v9W5saeHXHy38+t/z82UyoL+Pq5DF1WZVfI3Z6r1jxw5ERkbiyy+/xIsvvigoMZFpGQwGaLVaox3R3fl2VVXVPUvofiXj5ubW6OmIT09Ypmn9vLH39NV6N7c8iEqpQHQ/MS+BZBZHnY3d6r127VrMnj0b33//PQIDAwWlJvqfqqoqox7RVb9dXl4OW1vb+xZJcx3Z2djYWP1xHT28/+3qrP/Isz72NnLMDesqbFG18OJr7Fbv3na/Yffn/0RKSgr8/OpeSktUzWAwoKKiwmhHdHf+s06nM3oRVU9HCsWDLxEnMiVLe3UGocXXlN8UoKvA7AEdMeP57sYLRkZVfam3MS7tvvttpVJpkunI1taW0xFJ2vHCIsSnFyAt7wpkuH1zerXqk7v+Pq6I7uctZDH1nYQV37ELRRj9nwO1zoYL4ydCX1YEyBWATA7bNh3g+PgAtOgeCpnsf88BiNzqba3uvBHW2Pce3X0jrDFLidMRkWldK9EiMasQuRdvoVhTCWeVDXzdnRDe03xegV3YxS3L0wug0dV9QtQ1/P9g79kdek0pNBdO4Pquf0P7Wz7aDJlZ8xiNrgrx6QVCtnqbml6vr3WptzGfQ5LL5Q0ulTv/uVWrVo0qpbtvhCUi69G6hR2invMSHeO+hBTf1RItMvKv3PcsWK5yhEPnXlA4uuDS6r/D+elhsHX1BHD7xQzT8q7gWolW2G8QlZWVRnve6M6377wRtjGl5OLignbt2jVqOlIqzeoiXyIioxDyky7xSMO3cdu184HCuQ20F07VFB/wv63ed/5mceeNsMa+98hgMMDR0bHRx28uLi6N+hwp3AhLRGRKQoov91LxPe/2r4+iRSvoNbU3eGt0enywYg0WRa6sKaU7b4RtzHRUfSNsY6Yj3ghLRGSZhBRfsUbXqMdX3boGuaruPrc/B/bFkg/+Ums64o2wRER0P0KKz1nV8P9b7cV8VN26BjuPbnU+1q5NS3To0KE5oxERkZUTUnz32up9J722DJoLJ3Bj17/h6NcPto961vq4qK3eRERk2YQUX3iABz7ZlV/vx64kLvjjPj4ZbFp3gPOfh6FFj+frPM4AILynh5GTEhGRtRFSfPfa6u0RvbJBny9yqzcREVk2YVeCTOvnDZWyaVs1RG71JiIiyyas+J7s4IK5Yb6wt2lchNtbvX25royIiJpE6KqO6u3clrTVm4iILJvwlyUCLGurNxERWTazKL5qlrDVm4iILJtZFR8REZGxcb8XERFJCouPiIgkhcVHRESSwuIjIiJJYfEREZGksPiIiEhSWHxERCQpLD4iIpIUFh8REUkKi4+IiCSFxUdERJLC4iMiIklh8RERkaSw+IiISFL+P33zCca9p/gDAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def existeSommet(G : dict,s) -> bool: # s peut être str ou int\n",
    "    return s in G\n",
    "\n",
    "def existeArete(G : dict ,sd,sa) -> bool : # sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G[sd] # completer\n",
    "\n",
    "def supprimerSommet(G : dict,s) -> dict : # s peut être str ou int\n",
    "    pass # remplacez cette ligne par votre implémentation (pensez aux assert)\n",
    "\n",
    "def supprimerArete(G : dict,sd,sa) -> dict : # sd et sa peuvent être str ou int\n",
    "    pass # remplacez cette ligne par votre implémentation (pensez aux assert)\n",
    "\n",
    "G={'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B','D'], 'D': ['B','C']}\n",
    "# insérez ici les instructions pour supprimer A puis supprimer B-C\n",
    "\n",
    "\n",
    "print(str(G))\n",
    "G_nx=cree_graphe_non_oriente_nx(G)\n",
    "# Pour une representation circulaire : nx.draw_circular(G,with_labels=True)\n",
    "nx.draw(G_nx,with_labels=True) # Pour une representation classique\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Correction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "hQm-aZvc9Lbc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'B': ['D'], 'C': ['D'], 'D': ['B', 'C']}\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAARsElEQVR4nO3d/2/c9X3A8ded7cT5gkkTXGKaUApu45BCEpoG57KKwC+stD9MGu06DWlStfIDqGqnTeokpv7QjR/6B8BYK/HD6CZVyrRN2vihVCVo0sVx4pSUZEmcjAI2JeB88RwTn7HPtx/grndxnNjJne34/Xj8ePfx3Ts/RE99Pvd5fd6ZUqlUCgBIRHahFwAA80n4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJKV5oRcAQDrOjo7H3r7BOHFmJEYKk9HW2hxd69viG1/aEOtWL5+XNWRKpVJpXr4JgGQdGRiO5/adjtf6hyIiYnxyqvJea3M2ShGxZ1N7PPVQZ2zduKahaxE+ABrqZz1vxbMvn4jCZDGuVpxMJqK1uSmeeawrnui+q2HrcakTgIb5OHrHY2xi6prHlkoRYxPFePbl4xERDYufMz4AGuLIwHB866c9MTZRrLw2+Py3Y+rScEQmG5lsUyzfsDnWPvp0NLe11/ztipam+PmT3XH/hvpf9nRXJwAN8dy+01GYLE57vf3xH8adf7U3Nnz3pciuXBPnX/nHaccUJovx/L7TDVmX8AFQd2dHx+O1/qGr/6bXvCxWde2OibPvTHuvVIp49eRQnBsdr/vahA+AutvbN3jNY6YmCvHh8f+O5XdsuuL7mYjYe/janzNXbm4BoO5OnBmpGVmoNvSvfx+RbYrSR2PRtGpNfPqbP7ricYXJqTjx3sW6r034AKi7kcLkjO+1//Hfxoq7tkVpqhhjpw7E+//yN3HHX/xDNK3+1BU+Z6Lua3OpE4C6KhaLURwbveZxmWxTrNyUi8hkozB47IrHtLW21Ht5zvgAuDHDw8Nx4MCByOfzkc/no7e3N277yp9GdstXYyo7c2ZKpVKMnToQU4XRaFm3cdr7rc3Z6Oq4pe7rFT4AZq1UKkV/f38lcvv374+33347duzYEblcLr73ve9Fd3d3ROstsfvHv7ri73xDe38UkclGZDLR3NYe677+l7Gs/bPTvysiHn9gQ93/DQbYAZjR6OhoHDx4sBK5/fv3R1tbW+RyucjlcrFr1664//77o7l5+nnUky8dileOv3/VkYaZZDIRj957e7zwxI46/Csu+2zhAyDi47O5t956qxK5fD4fJ0+ejG3btsWuXbsqoevo6JjV513pyS2z1cgntwgfQKIKhUL09fVVIpfP5yObzVbO5nK5XGzfvj2WL7/+7YLm8qzOshUt2Xjmsc2e1QnAjXn33XdrIvfGG2/E5s2bay5b3nnnnZHJZOr6vYttdwbhA1iCJiYm4siRIzU3oVy6dKnmkuWOHTti1apV87Ke3wwOx/P7TserJ4ciEx8Pp5eV9+N7eFN7PLWnsyGXN6sJH8ASMDQ0VDmb279/f/T19cXdd99diVwul4vOzs66n83N1bnR8dh7eDBOvHcxRgoT0dbaEl0dt8TjD9iBHYAZFIvFOHbsWM1NKENDQ9Hd3V2J3M6dO+PWW29d6KUuSsIHsMgNDw9HT09PJXK9vb3R0dFRiVwul4vNmzdHNuthXLMhfACLSKlUipMnT9ZctqweEM/lctHd3R3r1q1b6KXetIQPYAHdyIA410f4AOZJ9YB4OXTlAfFy5OYyIM71ET6ABikPiFffhNLU1FRzp+WNDogzd8IHUCfvvvtuTeTeeOONuPfee2tm5xoxIM7cCB/AdZiYmIjXX3+95iaU6gHxXC4XO3bsiJUrVy70UrmM8AHMwtUGxMtnc4thQJxrEz6Ay1QPiJdDZ0B86RA+IHnlAfFy5AyIL23CByRlamqqsoN4+dLlO++8E1/+8pcroTMgvrQJH7CkjY6ORm9vbyVyPT09ceutt9bcaWlAPC3CBywZpVIpfvvb39bsOXfq1KnYunWrAXEqhA+4aVUPiJcvXRoQ51qED7hpDA4O1owUXD4gnsvlYuPGjUYKuCrhAxal8oB49U0oY2NjBsS5YcIHLAoffPBBZXeCfD4fhw8fNiBOQwgfMO+KxWIcPXq05iaUs2fPRnd3dyVyDz74YLS1tS30UlmChA9ouAsXLsSBAwcqkTt48GB0dHTU3IRiQJz5InxAXU1NTU3bQdyAOIuJ8AE3pDwgXr2D+Jo1a2puQrnvvvsMiLNoCB8wa+UB8eo7Lfv7+ys7iJcvXa5fv36hlwozEj5gRmNjY9HX11dz2dKAODc74QMqZhoQrw6dAXFudsIH8+js6Hjs7RuME2dGYqQwGW2tzdG1vi2+8aUNsW71/J41VQ+Il0M3NjZWEzkD4ixFwgfz4MjAcDy373S81j8UERHjk1OV91qbs1GKiD2b2uOphzpj68Y1DVlDeUC8HLnDhw/HPffcU7NLgQFxUiB80GA/63krnn35RBQmi3G1/22ZTERrc1M881hXPNF91w19Z3lAvPomlHPnzsWDDz5oQJzkCR800MfROx5jE1PXPvgTK1qy8cxjm+cUvwsXLkRPT08lcgbEYWbCBw1yZGA4vvXTnhibKFZeG3z+2zF1aTgi2xSRycay2zbGqi8+Equ3/WFkMr+P0oqWpvj5k91x/4bplz0vHxDP5/MxMDBgQBxmyUQpNMhz+05HYbI47fX2x38YK+7aFlOFD6MwcDTO//InMf67/rjta9+vHFOYLMbz+07HC0/sqBkQL+8gXj0g/vTTTxsQhznwPwUa4OzoeLzWP3TV3/Syrati5ecfjKZVa+LMP/11tO38o1jWfldERJRKEb84+rvYunN3nD72emVA/Dvf+U68+OKLBsThBggfNMDevsFZH7v8jk3R1HZbjA/8TyV8ERGZTCa+/t2/ix9+c7cBcagjv3RDA5w4M1IzsnAtTavXxlThYs1rxcjGpWVrRQ/qTPigAUYKk3M6vnjxXGRbb7nC50zUa0nAJ1zqhDqpHhDvObs24tNfnNXfjb/XH8WL52L5hnunvdfW2lLvZULyhA+uQ/WAeHlIvHoH8a9+/v74z7dLMT45890tU+OXojBwNC788iexasueWPbpu2reb23ORlfH9LNA4MaY44NZKA+IlyPX29sbd9xxR81WPNUD4mdHx2P3j3817Xe+2jm+TLSs2xirtzwcq7d/NTLZpppjlzdnI/+DR+b9GZ6w1AkfXKY8IF79uK/ygHg5crMZEH/ypUPxyvH3rzrSMJNMJuLRe2+PF57YcZ3/CmAmwkfyLl68GL29vb//fe6TAfHqx31dz4D4lZ7cMltXe3ILcGOEj6SUSqV48803a3Yp6O/vj+3bt9fsUlCvAfH5elYnMHvCx5JW3kG8+rJlc3NzzW9zjd5BfCF2ZwBmJnwsKYODgzV3Wh49enRR7CD+m8HheH7f6Xj15FBkIqJwhf34Ht7UHk/t6XR5ExpM+LhpffTRR/H666/X7FJQKBQW9Q7i50bHY+/hwTjx3sUYKUxEW2tLdHXcEo8/MP87sEOqhI+bRvWAeD6fj1//+tc1O4jncrm455577CAOXJXwsShdaUD83Llz0d3dXQndzp077SAOzJnwsShcaUD8M5/5TM2dlnYQB+pB+Jh39RoQB7gewkfDNWpAHOB6CB91dfmAeD6fj1OnTjVsQBxgroSPG1I9IF6+dFk9IJ7L5WLbtm02UwUWDeFjTq42IF4+m1uIAXGA2RI+ZlQeEK++CaU8IF6O3GIbEAe4FuGj4v3334/9+/dXIlceEK++CcWAOHCzE75ETU5OxtGjR2t2KTAgDqRA+BJRPSCez+fj4MGDBsSBJAnfElQ9IF4+mzMgDvAx4VsCygPi5cgZEAeYmfDdZAyIA9wY4VvkxsbG4tChQzU3oRgQB7h+wrfIDAwM1ETOgDhAfQnfAjIgDjD/hG8eXT4gfvjw4ejs7DQgDjCPhK9BygPi1Wdz58+fNyAOsMCEr06uNSCey+Wiq6vLgDjAAhO+62BAHODmJXyzYEAcYOkQvsuUB8Srf5szIA6wdMx7+M6OjsfevsE4cWYkRgqT0dbaHF3r2+IbX9oQ61bP/xD2TAPiu3fvroTOgDjA0jFv4TsyMBzP7Tsdr/UPRUTE+ORU5b3W5myUImLPpvZ46qHO2LpxTcPWUT0gns/n49ixY7Fly5aaszkD4gBL17yE72c9b8WzL5+IwmQxrvZtmUxEa3NTPPNYVzzRfdcNf2/1gHj5bM6AOEDaGh6+j6N3PMYmpq598CdWtGTjmcc2zzl+5QHxcuQMiANwuYaG78jAcHzrpz0xNlGsef3DY/ti5OC/x8S5wcguWxEtt98dt+76ZrRu3FI5ZkVLU/z8ye64f8OVL3saEAfgejQ0fE++dCheOf5+zeXNkd5/i//r2RvrHn06Wj/3QGSammPszb4YHzgWn3rk279fWCbi0Xtvjxee2BEREefPn4+enp5K5AyIA3A9Gha+s6PjsfvHv6q5iWWq8GEMPvfnse5r349VXX9wzc9oypQi98F/RV/+tZoB8VwuF93d3bF27dpGLB2AJaxhE9d7+wanvTb+uxNRmvwoVn5h16w+Y6pYjGxnLv756ScNiANQFw0ryYkzIzVnexERxbGRyK5si0y2aVafUco2x9rP3Rfbt29rxBIBSFDDfhAbKUxOe61pRVtMXRqJ0lTxCn8x0+dM1HNZACSuYeFra51+Mrn8jq7INC+LS/375/A5LfVcFgCJa1j4uta3xfLm2o/Ptq6KNV/5szj/ixfiUv/+mJooRKk4GWP/eyguvPritM9obc5GV8ctjVoiAAma17s6y0aPvRoXD/5HTJwbiMyyFbF8fWe07fqTaN2wuea45c3ZyP/gkQV5hicAS1PDbm65bfXyeOgL7dPm+CIiVm95OFZvefiqf5/JRDy8qV30AKirhk57P72nM1qbZ3cH5+Vam5viqT2ddV4RAKlraPi2blwTzzzWFSta5vY1Hz+rs2vGx5UBwPVq+ER4+UHTC7E7AwBcbt724/vN4HA8v+90vHpyKDIRUbjCfnwPb2qPp/Z0OtMDoGHmfQf2c6PjsffwYJx472KMFCairbUlujpuiccfWJgd2AFIy7yHDwAWkj18AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEiK8AGQFOEDICnCB0BShA+ApAgfAEkRPgCSInwAJEX4AEjK/wMgze+j8CNxjQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def existeSommet(G : dict,s) -> bool: # s peut être str ou int\n",
    "    return s in G\n",
    "\n",
    "def existeArete(G : dict , sd  , sa ) -> bool: #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G and sa in G[sd] and sd in G[sa]\n",
    "\n",
    "def supprimerSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s in G,'le graphe ne contient pas le sommet '\n",
    "    del G[s]\n",
    "    for sommet in G.keys() :\n",
    "        if s in G[sommet] :\n",
    "            G[sommet].remove(s)\n",
    "\n",
    "\n",
    "def supprimerArete(G : dict ,sd , sa ) -> dict: #sd et sa peuvent être str ou int\n",
    "    assert sd in G,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G,'le graphe ne contient pas le sommet d arrivee'\n",
    "    assert sa in G[sd] , 'l arc  n existe pas.'\n",
    "    G[sd].remove(sa)\n",
    "    G[sa].remove(sd)\n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "G={'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B','D'], 'D': ['B','C']}\n",
    "# insérez ici les instructions pour supprimer A puis supprimer B-C\n",
    "supprimerSommet(G,'A')\n",
    "supprimerArete(G,'B','C')\n",
    "\n",
    "print(G)\n",
    "G_nx=cree_graphe_non_oriente_nx(G)\n",
    "# Pour une representation circulaire : nx.draw_circular(G,with_labels=True)\n",
    "nx.draw(G_nx,with_labels=True) # Pour une representation classique\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "l7fLENcD-g_r"
   },
   "source": [
    "**Exercice 4 : Modifier de nouveau l'implémentation pour modéliser un graphe pondéré non orienté** \n",
    "\n",
    "Vous allez modifier de nouveau l'implémentation pour modéliser un graphe pondéré et non orienté.\n",
    "\n",
    "En modifiant de nouveau l'implémentation du graphe, créez le dictionnaire G correspondant au graphe pondéré non orienté ci-dessous.\n",
    "\n",
    "Attention, ici vous devez modifier les primitives mais aussi les instructions pour créer le graphe attendu.\n",
    "\n",
    "Les clé resteront les sommets. La  valeur correspondant à chaque sommet ne sera plus une liste d’adjacence, mais un dictionnaires dont les clés seront les sommets d'arrivée des arêtes, et les valeurs le poids de chaque arête.  \n",
    "Par exemple: pour le graphe ci-dessous :  \n",
    "G1 = {1: {2: 1, 5: 5}, 2: {1: 1, 5: 6, 3: 2}, 3: {2: 2, 4: 3}, 4: {5: 4, 3: 3}, 5: {1: 5, 2: 6, 4: 4}}.  \n",
    "<img src=\"graphe_non_or_pond.png\" width=\"200\" height=\"200\" />\n",
    "\n",
    "Il faut donc modifier :  \n",
    "- `ajouterSommet` (la valeur de la clé s doit être un dictionnaire)   \n",
    "- `ajouterArete` (pour ajouter un dictionnaire, et non plus une liste). \n",
    "- `supprimerArete` devra aussi être modifiée pour tenir comte de la structure différente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n"
     ]
    }
   ],
   "source": [
    "def  creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G: dict) -> bool:\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict,s) : # s est str ou int\n",
    "    pass\n",
    "def ajouterArete(G : dict , sd , sa, pds) -> dict :  # sd et sa sont str ou int\n",
    "    pass\n",
    "def supprimerSommet(G : dict , s ) : # s est str ou int\n",
    "    pass\n",
    "def supprimerArete(G : dict , sd , sa) -> dict :  # sd et sa sont str ou int \n",
    "    pass\n",
    "def existeSommet(G : dict , s ) -> bool:  # s est str ou int\n",
    "    return s in G\n",
    "def existeArete(G : dict , sd , sa ) -> bool :  # sd et sa sont str ou int\n",
    "    return sd in G and sa in G[sd]\n",
    "\n",
    "# Completez également les instructions ci-dessous :\n",
    "G=creerGrapheVide()\n",
    "\n",
    "\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Correction***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Le graphe est vide :  False\n",
      "{1: {2: 1, 5: 5}, 2: {1: 1, 5: 6, 3: 2}, 3: {2: 2, 4: 3}, 4: {3: 3, 5: 4}, 5: {1: 5, 2: 6, 4: 4}}\n",
      "Le sommet existe :  True\n",
      "l arete existe :  True\n",
      "{1: {2: 1, 5: 5}, 2: {1: 1, 5: 6}, 3: {4: 3}, 4: {3: 3, 5: 4}, 5: {1: 5, 2: 6, 4: 4}}\n",
      "l arete existe :  False\n",
      "le sommet existe False\n",
      "{1: {2: 1}, 2: {1: 1}, 3: {4: 3}, 4: {3: 3}}\n"
     ]
    }
   ],
   "source": [
    "def  creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G: dict) -> bool:\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict,s) : # s est str ou int\n",
    "    G[s]={}\n",
    "def ajouterArete(G : dict , sd , sa, pds) -> dict :  # sd et sa sont str ou int\n",
    "    G[sd][sa] = pds\n",
    "    G[sa][sd] = pds\n",
    "    \n",
    "def supprimerSommet(G : dict , s ) : # s est str ou int\n",
    "    assert s in G.keys(),'impossible de supprimer un sommet non existant'\n",
    "    del G[s]\n",
    "    for sommet in G.keys() :\n",
    "        if s in G[sommet] :\n",
    "            del G[sommet][s]\n",
    "def supprimerArete(G : dict , sd , sa) -> dict :  # sd et sa sont str ou int \n",
    "    del G[sd][sa]\n",
    "    del G[sa][sd]\n",
    "def existeSommet(G : dict , s ) -> bool:  # s est str ou int\n",
    "    return s in G\n",
    "def existeArete(G : dict , sd , sa ) -> bool :  # sd et sa sont str ou int\n",
    "    return sd in G and sa in G[sd]\n",
    "# Completez également les instructions ci-dessous :\n",
    "G=creerGrapheVide()\n",
    "for i in range(1,6):\n",
    "    ajouterSommet(G,i)\n",
    "ajouterArete(G,1,2,1)\n",
    "ajouterArete(G,1,5,5)\n",
    "ajouterArete(G,2,5,6)\n",
    "ajouterArete(G,2,3,2)\n",
    "ajouterArete(G,3,4,3)\n",
    "ajouterArete(G,4,5,4)\n",
    "print(\"Le graphe est vide : \", estVideGraphe(G))\n",
    "print(G)\n",
    "print(\"Le sommet existe : \",existeSommet(G,5))\n",
    "print(\"l arete existe : \",existeArete(G,2,3))\n",
    "supprimerArete(G,2,3)\n",
    "print(G)\n",
    "print(\"l arete existe : \",existeArete(G,2,3))\n",
    "supprimerSommet(G,5)\n",
    "print(\"le sommet existe\",existeSommet(G,5))\n",
    "print(G)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Une part importante de ce document est initialement produite par David Roche, visible sur son site : Pixees publié sous licence CC BY SA  \n",
    "Jean-Louis THIROT et Mireille COILHAC  \n",
    "Ce document est sous licence Creative Commons  Attribution - Pas d’Utilisation Commerciale - \n",
    "Partage dans les Mêmes Conditions 4.0 International.***\n"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyOz2rkm7TmUTLQeTaYq/DFI",
   "name": "LesGraphes.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}