{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

Parcours de Graphes

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Pour la suite , on utilisera la classe Graphe ci-dessous par listes d'adjacences

" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import networkx\n", "import matplotlib.pyplot as plt\n", "\n", "class Graphe:\n", " def __init__(self):\n", " self.adj={}\n", " \n", " def ajouter_sommet(self,s):\n", " if s not in self.adj:\n", " self.adj[s]=[] # ici on met les sommets adjacents dans une liste\n", " \n", " def ajouter_arete(self, s1, s2):\n", " self.ajouter_sommet(s1)\n", " self.ajouter_sommet(s2)\n", " if s2 not in self.adj[s1]:\n", " self.adj[s1].append(s2)\n", " if s1 not in self.adj[s2]:\n", " self.adj[s2].append(s1)\n", " \n", " def est_arete(self,s1,s2):\n", " return s2 in self.adj[s1]\n", " \n", " def sommets(self):\n", " \"\"\"renvoie la liste des sommmets du graphe\"\"\"\n", " return list(self.adj)\n", " \n", " def voisins(self,s):\n", " \"\"\" renvoie la liste des voisins d'un sommet s\"\"\"\n", " return self.adj[s]\n", " \n", " def __str__(self): \n", " \"Affichage du graphe en utilisant le module networkx\"\n", " G = networkx.Graph()\n", " for s1 in self.sommets():\n", " for s2 in self.voisins(s1):\n", " G.add_edge(s1,s2)\n", " networkx.draw(G, with_labels=True,node_color=\"skyblue\" ) \n", " return \"\"\n", " \n", " " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']\n", "['a', 'd', 'e', 'h']\n" ] }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAABKGUlEQVR4nO3deVyN6f8/8NdpVaksU8lOlEqWFFps2ZcxYmzJkCYNMcpOGGtFlrJvWcv6MVkHWbOUSqXSJrKmiKicttM59++P+erHONFyzrnP8n4+HvMYo/vc9yuT8zr3fd33dXEYhmFACCGEKAgltgMQQgghkkTFRwghRKFQ8RFCCFEoVHyEEEIUChUfIYQQhULFRwghRKFQ8RFCCFEoVHyEEEIUChUfIYQQhULFRwghRKFQ8RFCCFEoVHyEEEIUChUfIYQQhULFRwghRKFQ8RFCCFEoVHyEEEIUChUfIYQQhULFRwghRKFQ8RFCCFEoVHyEEEIUChUfIYQQhULFRwghRKGosB2AyD8uT4CkvBK8LeajlC+AurIS9DWU0aFBHWiq0mcvQohkcRiGYdgOQeRTNpeHiDfFyCwoAwdA+Rc/aSocgAHQWkcNtgYaMNRSZSsmIUTBUPERsYjLLcb1LO5XZVcZFQ7g0EQLlnoa4g9GCFF4dJ2JiJyw0ls71BKPo8KFbl/OANezuIjLLZZQQkKIIqPiIyKVzeVV+UzvS5/LL7uIJ55ghBDyf6j4iEhFvCmudul9Vs4AkTl01kcIES8qPiIyXJ4AmQVllX79dfpDBI7pheU9W+PIgt/BKy35ZpsnBWUo4gnEGZMQouCo+IjIJOWVgPO9r185A5dtxzH/XCxyMlIQd+7YN9twACTmfVuIhBAiKvQcHxGZt8X8717mtB3nBh29RgAA054D8Tr94TfblDNAbjFfXBEJIYTO+IjolPK/f4lS+yf9il+r1tFAWRG3RvshhJDaoOIjIqOuLJofJ1HthxBChKF3GCIy+hrKUPneIF8VqHAAPQ1l0QQihBAhqPiIyJjXU0M5v3bjcwyADg3qiCYQIYQIQVOWEZG4ffs2PD09YTdjORp37A5wanLqx8BYVx0jW+uIPB8hhHxGZ3ykVp49e4YxY8ZgwoQJmDt3LhaOGQQVpZpd7+SVlIDzLFHECQkh5GtUfKRGPn36BG9vb3Tp0gXt27dHWloaxo8fj8ZaqnBoolXtsT4VDmCCD/BwHgNfX1/QhQhCiLhQ8ZFqEQgEOHjwIExMTPDixQskJCRg2bJl0NTUrNjGUk+jWuX3eXWGMTYdEB0djTNnzuDXX39FYWGhmL4LQogiozE+UmV3796Fp6cnlJWVERAQgO7du393++wiHiJzivHkO+vxGemowaaRBgw1//96fKWlpZg5cybu3LmD0NBQmJiYiOcbIoQoJCo+8kPPnz/HggULcPfuXfj5+WH8+PFQUqr6xYIingCJeSXI/WIFdr0qrMC+Z88eeHt7Y+/evRg+fLgovhVCCKHiI5X79OkT1q5di+3bt2PmzJmYN28etLS0JJohKioKv/76K1xcXLB8+fJqFS4hhAhD7yLkGwKBAIcOHUK7du2QmZmJBw8eYPny5RIvPQDo1q0b7t+/j/DwcPz888/48OGDxDMQQuQLFR/5SmRkJGxsbLB161acPHkSISEhaNasGauZDAwMcPXqVbRt2xbW1tZISkpiNQ8hRLZR8REAwMuXL+Hk5ITRo0djxowZuHfvHmxsbNiOVUFVVRUBAQFYvnw5HBwccPz4cbYjEUJkFBWfguNyufjrr7/QqVMntGnTBmlpaZg4caLUjqU5OzsjLCwMCxcuxNy5c1FeXs52JEKIjJHOdzcidgKBACEhIWjXrh3S09MRFxeHlStXom7dumxH+6HOnTvj/v37SExMxMCBA5Gbm8t2JEKIDKHiU0BRUVGwtbXFpk2bcOzYMRw7dgwtWrRgO1a1NGzYEBcvXkTXrl1hbW2N2NhYtiMRQmQEFZ8CefXqFSZOnIiRI0di2rRpiI6Ohp2dHduxakxZWRm+vr7YsGEDBg0ahAMHDrAdiRAiA6j4FEBRURFWrlyJjh07okWLFkhPT8ekSZOkdhyvukaNGoXw8HD4+PjAw8MDZWVlbEcihEgx+XjnI0IxDIOjR4+iXbt2SE5ORmxsLFavXi0T43jVZWZmhpiYGLx8+RIODg7Izs5mOxIhREpR8cmpmJgY2NnZYf369QgJCcHx48fRsmVLtmOJla6uLk6fPo0BAwbA2toaERERbEcihEghKj45k5WVhUmTJuGXX36Bm5sbYmJi0KNHD7ZjSYySkhKWLVuGXbt2YcSIEdi+fTstcUQI+QoVn5woLi7G6tWr0bFjRzRp0gTp6elwcXGRm3G86ho6dCju3r2L7du3Y8qUKSgpKWE7EiFESijmu6IcYRgGx48fh6mpKR48eICYmBj4+PhAW1ub7Wisa9u2Le7du4eioiLY29vjxYsXbEcihEgBWp1Bht2/fx+enp7gcrkICAhAr1692I4klRiGwYYNG7BhwwaEhITAwcGB7UiEEBbRGZ8Mev36NVxcXPDzzz/DxcUF9+/fp9L7Dg6Hg7lz5yI4OBhOTk7YuHEjjfsRosCo+GRIcXExfHx8YGFhAX19faSnp8PV1RXKyspsR5MJffv2RVRUFEJCQuDk5AQul8t2JEIIC6j4ZADDMDh58iTMzMxw//59REdHY+3atdDR0WE7msxp0aIF7ty5A3V1ddjY2ODJkydsRyKESBiN8Um5uLg4eHp6Ij8/HwEBAejTpw/bkeQCwzDYvn07Vq5ciQMHDmDw4MFsRyKESAid8UmpnJwcuLq6YsiQIXB2dkZcXByVnghxOBx4eHjg1KlT+P3337F69WoIBAK2YxFCJICKT8qUlJTAz88P7du3R4MGDZCeno6pU6fSOJ6Y2NvbIyYmBv/88w9GjhyJgoICtiMRQsSMik9KMAyDU6dOwczMDPfu3UNkZCT8/f2hq6vLdjS517hxY9y8eROGhobo2rUrUlNT2Y5ECBEjGuOTAg8ePICnpyfev3+PgIAA9O3bl+1ICmvfvn1YuHAhdu3aBUdHR7bjEELEgM74WPTmzRu4ublh0KBBGDduHOLj46n0WDZlyhRcuHABs2bNgre3N/h8PtuRCCEiRsXHgtLSUqxbtw7m5ubQ0dFBWloa/vjjD6ioqLAdjQCwtrbG/fv3ERERgaFDhyIvL4/tSIQQEaLikyCGYXD69GmYm5vjzp07iIiIwIYNG1CvXj22o5H/0NfXx5UrV2BmZgYrKyskJCSwHYkQIiI0xichiYmJ8PT0xNu3b7Fp0yb079+f7Uikio4cOYJZs2YhMDAQTk5ObMchhNQSFZ+YvX37FkuXLsXp06fx119/YerUqXRJUwYlJCRg5MiRGD58ONatWwdVVVW2IxFCaogudYpJWVkZNmzYAHNzc2hqaiItLQ3Tp0+n0pNRHTt2RExMDFJTU9G/f3+8ffuW7UiEkBqi4hMxhmFw5swZmJub48aNG7h9+zY2bdqE+vXrsx2N1FKDBg1w4cIF2Nvbw8rKCtHR0WxHIoTUAF3qFKGkpCR4eXnh9evX2LRpEwYOHMh2JCImoaGhmDp1Kvz8/ODq6sp2HEJINdAZnwjk5uZi2rRp6Nu3L0aMGIGEhAQqPTnn6OiI27dvw9/fH3/88QdKS0vZjkQIqSIqvlooKyvDxo0bYWZmBjU1NaSlpWHGjBl044OCaNeuHaKjo/HmzRv07t0bWVlZbEcihFQBFV8NMAyD8+fPw8LCAleuXMGtW7cQGBiIBg0asB2NSJiOjg5OnTqFYcOGwdraGrdv32Y7EiHkB2iMr5qSk5Ph5eWFly9fYuPGjbSOG6lw8eJFTJ48GUuXLoWHhwc4HA7bkQghQtAZXxW9e/cOHh4e6NOnD4YNG4bExEQqPfKVwYMHIyIiArt378bkyZNRXFzMdiRCiBBUfD/A4/EQGBgIU1NTcDgcpKam4s8//6RxPCKUkZERIiMjwePxYG9vj+fPn7MdiRDyH1R83/HPP//AwsIC//zzD27evImtW7eiYcOGbMciUk5LSwshISFwdnZGt27dcPXqVbYjEUK+QGN8QqSkpGDOnDnIzMzExo0bMWTIEBqvITVy48YNODk5Yfbs2Zg7dy79HBEiBeiM7wt5eXn4888/0atXLwwcOBBJSUkYOnQovVmRGuvTpw+io6Nx4sQJjB07Fp8+fWI7EiEKj4oP/47jbdmyBe3atQOfz0dqaio8PT2hpqbGdjQiB5o1a4bbt29DW1sb3bt3R0ZGBtuRCFFoCl98ly5dQseOHXH27Flcv34d27Ztw08//cR2LCJn6tSpg71792LGjBmws7PD+fPn2Y5EiMJS2DG+tLQ0zJkzBxkZGdiwYQOGDRtGlzSJRERGRmL06NFwc3PD0qVLoaSk8J8/CZEohfsbl5eXh1mzZqFHjx7o27cvHj58iJ9//plKj0iMjY0NYmJicOXKFYwYMQL5+flsRyJEoShM8ZWXl2Pbtm0wNTVFaWkpUlJSMHv2bBrHI6wwNDTE9evX0bx5c1hbWyM5OZntSIQoDJm51MnlCZCUV4K3xXyU8gVQV1aCvoYyOjSoA03V7/d3WFgYvLy80KhRI2zatAkdOnSQUGpCfuzgwYOYO3cuduzYgV9//ZXtOITIPakvvmwuDxFvipFZUAYOgPIv0qpwAAZAax012BpowFDr69lU0tPTMXfuXKSmpmLDhg0YPnw4XdIkUik2NhajRo3CuHHjsGbNGigrK7MdiRC5JdWXOuNyixGSkY+M/DLwma9LD/j3v/kMkJFfhpCMfMTl/js34ocPHzB79mzY2dmhZ8+eSE5Oxi+//EKlR6RWly5dEBMTg5iYGAwaNAjv379nOxIhcktqiy8utxjXs7jflF1lyhngehYXAacuo127dvj06ROSk5Mxb948qKurizcsISKgp6eHy5cvo1OnTrCyskJ8fDzbkQiRS1J5qTOby0NIRn6VS+9L/LIS2Kvlo1dnc9EHI0RCjh8/jhkzZmDjxo2YOHEi23EIkSsqbAcQJuJNcY1KDwCU1ergva6OaAMRImFjx46Fubk5HB0dERMTgw0bNtCKIISIiNSd8XF5AmxPzgNfSKqs1AScWumJ9y+fwtjWARyOEn5q3hoDPBZ/tZ0yB/Awb/DDuz0JkXYfP37EhAkTUFhYiBMnTqBRo0ZsRyJE5kldMyTllUDYLSjlvDIEz5mMLj+Pw7IbGeg4cCRSbvwjdB8cAIl5JWLNSYgk1KtXD+fOnUOfPn1gbW2Ne/fusR2JEJkndcX3tpgv9DLny8T7EPDLYTt+KpRVVdG+7zA0bd9Z6D7KGSC3mC/mpIRIhpKSElasWIFt27Zh+PDh2L17N9uRCJFpUld8pXyB0N8vePcGOvqGXz2SoGvQpNr7IURWDR8+HLdv30ZAQADc3NxQWlrKdiRCZJLUFZ+6svBI2j/po+BtNr4cksx/k1Xt/RAiy0xMTBAVFYUPHz6gZ8+eePXqFduRCJE5UtcO+hrKUBEyyNe8gzU4ysqIPL4X/PJypNy8iFcPhT/npMIB9DRo5gsin7S1tXHy5Ek4Ojqia9euCA8PZzsSITJF6orPokEdCLvNVEVVDc7rD+D+6RCs7GWE+H9Ool2PAVBW+/bhdAZAhwZ1xJ6VELZwOBwsXLgQBw4cwJgxYxAYGAgpu0GbEKkldY8zAMCpzAJk5Jf9cLttvw1Et1GTYPWL01e/b6yrhpGt6Vk+ohiePn2KkSNHwtzcHLt374ampibbkQiRalJ3xgcAtgYaQi93ZsbeReG7N+CXlyP23DHkZKTA2Nbhq21UOIBNIw0JJSWEfa1atcLdu3fB4XBgZ2eHp0+fsh2JEKkmlcVnqKUKhyZa35Tfu2dPsHlcH6zoaYQ7h3dgwrog6Oj9/wd6VTiAQxMtGGrSDBdEsWhqauLQoUNwcXFB9+7dERYWxnYkQqSWVF7q/KzKE1UzDHilJehtqIEeLX+SSDZCpNWtW7cwbtw4zJw5EwsXLqRVSQj5D6kuPgDILuIhMqcYT76zHp+Rjhqiju7Co/sR+Pvvv+kvOlF4r169wqhRo9C0aVMcOHAA2trabEciRGpIffF9VsQTIDGvBLlfrMCu98UK7KWlpbCxsYG7uzvc3d3ZjksI60pLSzFjxgzcvXsXoaGhMDExYTsSIVJBZoqvKtLT02Fvb4/w8HCYmZmxHYcQqbBnzx54e3tj7969GD58ONtxCGGdXBUfAAQFBWHz5s2IiopCnTr0LB8hAHDv3j2MHj0aLi4uWL58OZSUpPK+NkIkQu6Kj2EYjBkzBo0bN0ZgYCDbcQiRGm/evMHo0aOhra2N4OBg1K9fn+1IhLBC7j72cTgc7N69G6dPn8aFCxfYjkOI1DAwMMC1a9fQpk0bWFtbIykpie1IhLBC7s74Prt9+zbGjBmDuLg4GBoash2HEKkSHBwMLy8vbN26FWPHjmU7DiESJbfFBwDLli1DVFQULl68SGMahPxHfHw8Ro4ciVGjRsHPzw8qKipsRyJEIuS6+MrLy9GzZ0+MGjUKc+bMYTsOIVLn/fv3GD9+PPh8Po4dOwY9PT22IxEidnJ9GqSiooIjR45g7dq1iIuLYzsOIVKnYcOGuHjxIrp27Qpra2vExsayHYkQsZPr4gOAli1bYvPmzRg/fjy4XC7bcQiROsrKyvD19cWGDRswaNAgHDhwgO1IhIiVXF/q/NLkyZOhoqKCvXv3sh2FEKmVkpKCESNGoH///ti0aRPU1NTYjkSIyMn9Gd9nW7ZsQXh4OE6ePMl2FEKklpmZGWJiYvDy5Us4ODggOzub7UiEiJzCFJ+2tjaOHDkCDw8PvHjxgu04hEgtXV1dnD59GgMGDIC1tTUiIiLYjkSISCnMpc7P1q5di/Pnz+PmzZtQVlZmOw4hUu3ChQtwcXHBihUr8Mcff9DKJ0QuKFzxCQQC9O/fH7169cKyZcvYjkOI1MvIyICjoyO6du2K7du30xy4ROYpzKXOz5SUlHD48GFs374dd+/eZTsOIVKvbdu2uHfvHrhcLnr06EFDBUTmKVzxAUDjxo2xe/duODs74+PHj2zHIUTq1a1bF8eOHcPYsWPRrVs33Lhxg+1IhNSYwl3q/JKHhwfev3+Po0eP0tgFIVV07do1TJgwAfPnz4eXlxf93SEyR6GLr7i4GNbW1pg3bx4mTZrEdhxCZMbz588xcuRIGBsbY+/evdDS0mI7EiFVptDFBwBJSUlwcHBAREQE2rZty3YcQmRGcXEx/vjjD8THxyM0NBRGRkZCt+PyBEjKK8HbYj5K+QKoKytBX0MZHRrUgaaqQo62EJYpfPEBwNatW3Hw4EHcvXuXZqogpBoYhsG2bduwcuVKHDx4EIMHD674WjaXh4g3xcgsKAMHQPkX7zQqHIAB0FpHDbYGGjDUUpV4dqK4qPjw71/e4cOHw8zMDGvXrmU7DiEy5/bt2xg3bhymTZuGxYsX48H7UlzP4n5VdpVR4QAOTbRgqach/qCEgIqvQm5uLjp16oSDBw+iX79+bMchROZkZWXh119/hcWQMTD+eWJF6a0daolRyzahTbdelb6Wyo9IEl1g/z96eno4ePAgJk+ejNzcXLbjECJzmjRpgmMXr6HlwLFVOtP7UjkDXM/iIruIJ55whHyBiu8L/fr1g5OTE1xdXUEnwoRU3/28ciip1mycvJwBInOKRZyIkG9R8f3H6tWr8fr1a+zYsYPtKITIFC5PgMyCMqFfe5Ucj02j7LCiVxv876+Z4JWWCN3uSUEZingCccYkhIrvv9TU1HDkyBH89ddfePjwIdtxCJEZSXklqOxR9gcXT8Fl2wnMOxuDdy+e4MbejUK34wBIzBNeioSIChWfEMbGxli3bh3Gjx+P4mK69EJIVbwt5lc6tmcz1hX1GjWBpm599Hb1QsLlUKHblTNAbjFfjCkJoeKr1OTJk2Fubo558+axHYUQmVDKr/wSpa5B44pf1zdshoLcnBrthxBRoOKrBIfDwc6dO3H+/HmcO3eO7TiESD115crfTvLfvK749cecV9DRa1TptiocurGMiBcV33fUq1cPISEhcHNzw+vXr3/8AkIUmL6GMlQqGeSLPLEP+W9eoyj/A24GBaBD/1+EbldeVoptvqswZMgQBAYGIjU1le6wJiJHxfcDdnZ2mDZtGn777TcIBHQJhpDKWDSog8oqqtOgkdg3fTT8f7ZC/aYt0Of32UK3U1dXxwGfxZgyZQqSk5MxaNAgNG/eHK6urjh+/Djev38vvm+AKAyauaUKysvL0bt3bwwfPhzz589nOw4hUutUZgEy8oU/0lAVxrpqGNlap+K/GYbBo0ePEBYWhsuXL+PWrVto164dBgwYgIEDB6J79+5QVaV5Pkn1UPFV0fPnz2FtbY1//vkHVlZWbMchRCplc3kIyciv9swtwL/Tlk0w1oWhZuVFVlpaisjIyIoifPz4MXr37l1RhEZGRrQ+IPkhKr5qOHHiBLy9vREfH4+6deuyHYcQqRSXW1zlCao/q+lcnbm5ubh69SrCwsIQFhYGdXV1DBgwAAMGDICDgwPq1atXvfBEIVDxVZOrqysEAgH279/PdhRCpNbn8ivj86GkpFzpdgIBH6pKSujbtG6tJ6hmGAbJyckVJXj37l106NChogitra2hoqJSq2MQ+UDFV02fPn1Cly5dsGLFCowbN47tOIRIrf1/n0fSJyUYduha6Xp8yH2JWwc248zhICgpifZeu+LiYty5c6fisuirV6/g4OBQcVm0RYsWIj0ekR1UfDUQGxuLwYMHIzo6Gi1btmQ7DiFSqXfv3vDw8MDQEaOQmFeC3C9WYNf7vxXY1ZUY2NnZYcqUKZg6dapY82RnZ+PKlSsVZ4T169evOBvs06cPDV8oECq+Glq/fj1CQ0MRHh5Ol08I+Y+0tDT07t0bL168gJra91drSEpKgoODAxITE2FoaCiRfAKBAAkJCRUlGB0djS5dulQUoaWlpcjPQIn0oOKrIYFAgEGDBsHGxgYrVqxgOw4hUmX27NlQV1eHr69vlbZfsmQJ0tPTcfLkSTEnE47L5SI8PLyiCHNzc9GvX7+KImzSpAkruYh4UPHVQnZ2Njp37oyTJ0+iR48ebMchRCqUlJSgWbNmiIqKQuvWrav8mg4dOmD9+vUYPny4mBP+2IsXLyoui169ehWGhoYVJdizZ09oamqyHZHUAhVfLZ0/fx4eHh548OAB6tevz3YcQlgXEhKCgwcPIiwsrFqvu3nzJiZOnIjk5GTo6Oj8+AUSwufzERsbW3E2GB8fj+7du1cUYYcOHejZQRlDxScCf/75J3JycnD8+HH6C0AUXs+ePTFr1iyMGjWq2q91dXWFpqYmtmzZIoZkolFQUIAbN25UFGFhYWFFCfbv3x8GBgZsRyQ/QMUnAiUlJejatSs8PT0xZcoUtuMQwpqUlBT07dsXL168qNFUYnl5eWjfvj1OnToFGxsbMSQUvczMzIoSvH79Olq1alVRhHZ2dqhTpw7bEcl/UPGJSHJyMnr37o07d+7AxMSE7TiEsMLLywsaGhrw8fGp8T6OHz+O1atXIzY29od3hEqb8vJyREVFVRRhcnIy7O3tK4rQ1NSUrgpJASo+EdqxYwf27NmDyMhIqKursx2HEIkqLi5Gs2bNEBMTg1atWtV4PwzDYNiwYbC1tYW3t7cIE0rehw8fcO3atYqH6AUCQUUJ9uvXDw0bNmQ7okKi4hMhhmHg6OiINm3aYP369WzHIUSiDh8+jJCQEFy6dKnW+3rx4gUsLS0REREBY2NjEaRjH8MwyMjIwOXLlxEWFobw8HCYmJhg4MCBGDBgALp37y5zZ7iyiopPxN69e4dOnTph3759GDBgANtxCJGYHj16YPbs2XB0dBTJ/gIDAxEaGoobN27I5eXBsrIyREZGVhRhRkYGevXqVVGEbdq0kcvvWxpQ8YnB9evXMXHiRMTHx0NfX5/tOISIXXJyMvr374/nz5+LbH08Pp8PGxsbuLu7w9XVVST7lGb/XWlCTU2togRppQnRouITk0WLFiExMRHnz5+nT21E7s2aNQva2tpYvXq1SPebkJCA/v37IzExEY0aNRLpvqUZwzBISUmpGBu8e/cuLCwsKoqQVpqoHSo+MeHxeLCzs8PEiRMxc+ZMtuMQIjbFxcVo2rQpYmNjxTJp+6JFi/D06VMcO3ZM5PuWFSUlJV+tNPHixQs4ODhUFCFNll89VHxi9PjxY9jY2ODatWvo0KED23EIEYtDhw7h6NGjuHjxolj2X1xcDAsLCwQGBmLo0KFiOYasyc7OxtWrV3H58mVcuXIFurq6FSXYu3dvaGtriz0DlydAUl4J3n6x6ob+/626oakq3RN8U/GJ2aFDh7B27VrExMTQ/H5ELtnZ2WHevHkYMWKE2I5x7do1TJkyBQ8fPpTIm7osEQgESExMrDgbjIqKQpcuXSqKUNQrTWRzeYh4U4zMgrJK11lsraMGWwMNGGqJZrxX1Kj4xIxhGDg7O0NHRwc7duxgOw4hIvXw4UMMHDgQz58/F/uYk4uLC3R1dREQECDW48g6LpeLW7duVRTh27dv0a9fPwwcOBD9+/dH06ZNa7zvuNxiXM/iflV2lVHhAA5NtGCpp1Hj44kLFZ8E5Ofno3Pnzti4caNYPxUTIml//vkndHV1sWrVKrEf6/3792jfvj3OnDmDrl27iv148uLly5e4cuUKLl++jKtXr6JRo0YVq9BXZ6WJ6pTeZ9JaflR8EhIZGYkRI0YgNja2Vp+4CJEWRUVFaNasGeLi4tCiRQuJHPPIkSPw8/NDbGysyB6bUCR8Ph9xcXEVZ4Px8fHo1q1bRRFWttJENpeHkIz8apXeZyocYIKxLgw1pef/FxWfBK1evRrXr1/HlStXoKyszHYcQmrlwIEDOHnyJC5cuCCxYzIMgyFDhqBXr15YuHChxI4rrwoKCnDz5s2KIiwsLET//v0rVpr4/AjJqcwCZOSX1fg4xrpqGNlaepaaouKTID6fDwcHBwwePJj+0hKZZ2tri4ULF0p84dhnz57BysoK9+7dQ5s2bSR6bHmXmZlZsQDv9evX0aJFCwz8eQQaOE4Hw/n2Bpmb+wMRExqMT3m5qGfQBAM8FsPc4ds7b5U5gId5A6m525OKT8JevnwJKysrnDt3jsYpiMxKSkrC4MGD8ezZM1YepN64cSMuXLiAq1ev0gQRYlJeXo7o6Ghce5ILjrEVVNS+nXg/6coZtOjUDXUb6uPhlTP43wpPzD0TBR29rycbUOEA9oaa6G4gHXe2S0f9KpBmzZph+/btcHJyQmFhIdtxCKmRXbt2wdXVlbXZQ/7880/k5+fj4MGDrBxfEaioqMDW1hYdezgILT0AsOj/C3T0GkFJSQkdBjrip+at8Co5/pvtyhkgt5gv7shVRnPesGDUqFG4fPkyPDw8cOjQIbbjEFItXC4XR44cwYMHD1jLoKKigj179mDQoEEYMmQIzYkrRqV8QaVfizt/HHeCd+DD65cAgLJiLrgf31d7P5JGZ3ws2bRpE6KjoxESEsJ2FEKq5cSJE7C1tUXz5s1ZzdG5c2dMmjQJnp6erOaQd+rKwmviw+uX+HvVbAxf4IelNx7hr1tPYGDUDqhk9Kyy/bBBepIoGC0tLRw9ehSenp7IzMxkOw4hVbZr1y64u7uzHQMAsHz5cty7d09s06URQF9DGcpChlHLSorA4XCgVf8nAMD9M0fw5kma0H2ocAA9Dem5k52Kj0WdO3fG4sWL4eTkBB6Px3YcQn4oISEBWVlZGDx4MNtRAACamprYtWsXpk2bhk+fPrEdR+6UlZUh6dIplJaWfvM1g9YmsHeehh2TB2NNfzPkPE5Fi47Cb9hjAHRoUEfMaauO7upkmUAgwJAhQ2BlZSXyJV0IETUPDw/o6+vjr7/+YjvKV3777Tfo6elhw4YNbEeRC0VFRdi7dy/8/f1hZmaGkat24INqzZ/Do+f4yDfevHmDTp064dixY+jVqxfbcQgRisvlolmzZkhMTJS62Ydyc3NhYWGB8+fPw8rKiu04Mis/Px/bt29HYGAgbGxssHjxYlhbW8vdzC10qVMKGBgYYN++fZg4cSLy8vLYjkOIUMeOHYO9vb3UlR4A6Onpwd/fH25ubjRsUAPv3r3D0qVLYWRkhOTkZFy7dg2hoaGwtrYGABhqqcKhiRZUqvnI5Oe5OqWp9AAqPqkxePBgjBo1Cm5ubqCTcCKNpOmmFmGcnZ2hp6dHqzdUQ1ZWFmbPng1jY2O8ffsWUVFRCA4Ohrm5+TfbWuppwKGJFvhlpQDz40cTpHWCaoCKT6r4+fnhyZMn2Lt3L9tRCPlKfHw8cnJyMGjQILajVIrD4WDnzp1Yu3Yt3Sn9A5mZmXB3d4eFhQUYhkFSUhJ27doFIyOj776uIDkKZ5dORRsdNShz8M0ZoArn3+nJjHXVMMFYVypLD6AxPqmTmpqKnj174tatWzA1NWU7DiEAgGnTpsHQ0BDLli1jO8oP+fv7IywsDGFhYTSd2X8kJyfDz88PFy9exB9//IFZs2ZBT0+vSq9lGAa2traYOXMmnJycUMQTIDGvBLlfrMCuJyMrsIMhUmfXrl1Mx44dmZKSErajEMIUFhYy9evXZ169esV2lCrh8XhMp06dmEOHDrEdRWrExMQwjo6OjL6+PuPj48N8/Pix2vs4ffo006FDB4bP54shoWRJeS0rJjc3NxgZGdEKDkQqHDt2DD169ECTJk3YjlIlKioq2Lt3L+bNm4fc3Fy247Dq1q1bGDhwIBwdHdGrVy88ffoUixYtgq6ubrX2w+fzsXjxYvj6+kJJSfZrQ/a/AznE4XCwZ88enDp1imakIKyT9ptahOnSpQsmTJiA2bNnsx1F4hiGwcWLF9GjRw9MmTIFo0ePxuPHjzFr1qwqr7b+X8HBwWjYsKHUTFxQWzTGJ8Vu3rwJJycnxMfHw8DAgO04RAHFxcXB0dERmZmZMrd4MpfLRfv27bFr1y4MGDCA7ThiJxAI8Pfff8PHxwc8Hg+LFy/G6NGja72CRmlpKUxMTBASEgI7OzsRpWUXFZ+UW7JkCWJjY3HhwgW5uMRAZIu7uzuaNWuGJUuWsB2lRi5duoTp06cjKSkJWlpabMcRCx6Ph6NHj8LX1xc6Ojrw9vbGsGHDRPZ+ERgYiGvXruHs2bMi2Z80oOKTcjweDz169MC4ceNoFnoiUYWFhWjevDmSk5PRuHFjtuPU2IQJE9C4cWP4+/uzHUWkSkpKsH//fqxbtw6tWrWCt7c3HBwcRHona2FhIdq2bYsrV67AwsJCZPtlGxWfDMjMzES3bt0QFhaGzp07sx2HKIjdu3fj4sWLCA0NZTtKrbx9+xYWFha4ePEiLC0t2Y5Ta58+fcLOnTuxceNGWFpawtvbGzY2NmI51ooVK/D48WMcPnxYLPtnDWv3k5JqCQ4OZtq1a8d8+vSJ7ShEQVhaWjIXL15kO4ZI7N+/n7G0tGR4PB7bUWrs/fv3zIoVKxg9PT1mzJgxTHx8vFiP9/btW6ZBgwbMkydPxHocNtCgkYyYMGECrKys4OXlxXYUogBiY2Px/v179O/fn+0oIjFp0iTUr18fgYGBbEeptjdv3mDBggVo27Ytnj17hjt37uD48ePo1KmTWI/r4+MDJycntG7dWqzHYQNd6pQhBQUF6Ny5M9atW4dRo0axHYfIsalTp6JFixbw9vZmO4rIPH78GN27d0dMTAxatWrFdpwfev78Ofz9/XHkyBE4OTlh3rx5aNGihcSObWlpiZSUFLm8o5yKT8ZERUVh+PDhuH//Ppo1a8Z2HCKHCgoK0KJFC6SkpMDQ0JDtOCLl5+eHmzdv4uLFi1I7nVl6ejr8/Pxw9uxZ/P777/Dy8kKjRo0kmsHFxQVNmzbFqlWrJHpcSaFLnTKmW7du8PT0hLOzM/h8PttxiBw6cuQIHBwc5K70AGDOnDnIycnBkSNH2I7yjYSEBIwdOxY9evRAq1at8PjxY6xdu1bipZecnIwLFy5g7ty5Ej2uJFHxyaD58+dDSUkJfn5+bEchcoZhGOzatQtTp05lO4pYqKqqYs+ePZgzZw7ev3/PdhwAQGRkJIYNG4bBgweja9euyMzMxLJly1C/fn1W8ixZsgQLFiyo9rRmsoQudcqoV69eoUuXLjh9+rTYbmUmiicmJgZjx47F48eP5XrCBE9PT3z8+BEHDhxg5fgMw+DatWtYs2YNnj17hvnz58PFxQV16tRhJc9n9+7dw+jRo/Ho0SNoaEjnkkKiQMUnw0JDQzFnzhzEx8fL9aczIjm///47jIyMsGjRIrajiNWnT59gbm6OoKAg9OvXT2LHFQgEOHfuHHx8fFBQUIBFixZh/PjxUFVlf4VyhmHQp08fTJw4Ea6urmzHESsqPhn3xx9/oLCwEMHBwVI7WE9kw+ebWlJTUyU+rsSGCxcuYNasWUhMTKzx5M1VVV5ejpMnT8LHxweqqqrw9vaGo6OjVJ1VX758GbNmzcLDhw9rPb+ntJOeP3VSIxs3bkR8fDyCg4PZjkJkXEhICPr27asQpQcAQ4cOhZWVFVauXCm2Y5SVlWHv3r1o164dtm/fDn9/f8TGxmLUqFFSVXoCgQCLFi3CmjVr5L70ANDMLfLgwYMHzE8//cRkZGSwHYXIKIFAwHTs2JEJCwtjO4pE5eTkMHp6esyDBw9Eul8ul8sEBAQwTZs2ZQYOHMiEh4eLdP+iduzYMcbKyooRCARsR5EI6fnIQWqsY8eOWLp0KZycnMDj8diOQ2RQTEwMCgsL0bdvX7ajSJSBgQF8fX3h5uYmkseD8vPz4evri9atW+PWrVsIDQ3FpUuX0LNnTxGkFQ8ej4clS5bAz89PYYZLqPjkxMyZM6Gnp4dly5axHYXIoF27dsHNzU2qLr9JypQpU6ClpYUtW7bUeB/v3r3DkiVLYGRkhJSUFFy/fh2nTp2ClZWVCJOKx759+9CyZUuF+tBDN7fIkbdv36JTp04IDg6Gg4MD23GIjMjPz0fLli2RlpYml9NTVcWjR49ga2uL2NjYak0LlpWVhfXr1+PgwYMYM2YM5s+fL1NzWxYVFaFt27Y4ffo0rK2t2Y4jMYr38U6O6evrY//+/Zg0aZLUPJxLpF9wcDD69++vsKUHAMbGxvDy8sL06dNRlXOBJ0+ewN3dHRYWFlBSUkJSUhJ27twpU6UHAFu2bIGtra1ClR5AxSd3Bg4ciDFjxsDV1bVKf4GJYmPkfKaW6pg3bx5evHiB48ePV7pNcnIynJ2d0a1bN+jr6+PRo0fYsGEDmjRpIsGkovHhwwesX78eq1evZjuKxFHxySEfHx+8ePECu3btYjsKkXJRUVEoKiqiS+MA1NTUsGfPHnh5eSEvL++rr92/fx+Ojo7o27cv2rdvj8zMTKxatQo//fQTS2lrb926dRgxYgRMTEzYjiJxNMYnp9LT02Fvb4+bN2/C3Nyc7ThESrm4uMDU1BTz589nO4rUmDlzJoqKirB3717cunULPj4+SE1Nxbx58+Dq6ir2h90l4fXr17CwsEBCQgKaNm3KdhyJo+KTY0FBQQgMDER0dDTrcwAS6fPx40e0bNkSjx49gr6+PttxpEZBQQHatGkDfX19lJaWYuHChZg4cSLU1NTYjiYy06ZNQ926deHv7892FFZQ8ckxhmEwZswYGBoaYvPmzWzHIVJm69atuH379nfHtBQJn89HaGgofHx8kJeXh9LSUmRkZKBu3bpsRxOpjIwM2NjYID09HQ0bNmQ7DitojE+OcTgc7N69G2fOnMGFCxfYjkOkyOebWtzd3dmOwjoej4eDBw+iffv2WL9+PVasWIGnT5/C3t4evr6+bMcTuWXLlsHLy0thSw+gMz6FcPv2bYwZMwZxcXFyubgoqb6IiAhMmjQJjx49UpjZOv6rpKQE+/btw7p162BkZITFixfDwcGh4s8jOzsbHTt2xNWrV9GhQweW04pGfHw8hgwZIpdnstVBxacgli1bhnv37uHSpUtQUlIClydAUl4J3hbzUcoXQF1ZCfoayujQoA40VelCgLybPHkyzM3NMW/ePLajSFxhYSF27dqFjRs3wsrKCosXL0b37t2Fbrtnzx4EBQXh7t27UFZWlnBS0Rs8eDCGDRsGDw8PtqOwiopPQZSXl6Nnz55wnDwVrfuNRGZBGTgAyr/4v6/CARgArXXUYGugAUMt9tcII6L34cMHtGrVChkZGdDT02M7jsTk5eVhy5Yt2Lp1K/r27YvFixf/8ExOIBCgd+/eGD16NGbOnCmhpOJx8+ZNTJkyBWlpaXJ1o05NUPEpkCtpr3DvAwNV9TrADy5vqXAAhyZasNST31WYFdXmzZsRGRmJo0ePsh1FInJycrBx40YEBQVhxIgRWLBgAYyNjav8+rS0NNjb2yM+Ph7NmjUTY1LxYRgGtra2mDFjBiZMmMB2HNbRNS0FEZdbjISSOlCto/FV6eU+e4zN4/vgL/uWuHt0d8XvlzPA9Swu4nKL2YhLxIRhGOzevVshZmp5/vw5PDw8YGZmhpKSEsTHxyMoKKhapQcA7dq1w6xZs6o8nZk0Onv2LIqKijB+/Hi2o0gFKj4FkM3l4XoW96vLmp/dOrgFrbvYYcWdZ7Ab//Wb4efyyy6ipY7kRUREBHg8Hnr37s12FLFJT0+Hi4sLLC0toa2tjdTUVGzevBnNmzev8T4XLFiAzMxM/O9//xNhUsng8/lYvHgxfHx8FHL1DWHoT0EBRLwpFlp6APAh+xUMjCqfsqicASJz6KxPXnyel1Me7+R88OABxowZgx49eqB169Z4/Pgx/Pz8RDL59ufpzGbNmoUPHz6IIK3kBAcHo0GDBhgyZAjbUaQGjfHJOS5PgO3JeeAL+b+8Z6ojnsZFQFlFFUrKyphx5Dr0Whh9s50yB/Awb0B3e8q4vLy8ikKQ5Tkm/ysiIgJr1qzBgwcPMGfOHEydOlVst+pPnz4d5eXl2L179483lgKlpaUwMTFBcHAw7O3t2Y4jNeidTM4l5ZWgss/2brtD0bJzdwxf4IsVd58LLT0A4ABIzCsRW0YiGYcPH8aQIUPkovQYhsGVK1fQp08fODs7Y/jw4Xjy5Almz54t1ufTfH19cfHiRYSHh4vtGKK0c+dOWFhYUOn9hwrbAYh4vS3mV3qZs6rKGSDlRQ7q5hZBR0cH2tra0NbWhooK/fjIis8ztezYsYOV44vquVGBQIBz585hzZo1+PTpExYtWoTx48dL7GdRV1cXW7Zsgbu7Ox48eCDVc+AWFhbC19cXYWFhbEeROvTOJedK+QKR7CchJRUb1s1HQUEBCgsLUVhYCHV19YoS/FyIXxajsF9X9nVFf65I3O7cuQOBQICePXtK9LjZXB4i3hQLfW700UfgdnZRlZ4bLS8vx4kTJ+Dr6ws1NTV4e3tjxIgRrNysMWLECBw6dAg+Pj5YuXKlxI9fVRs3bkT//v3lZtYZUaLik3PqyqJ5Y+jXqycCJyVX/DfDMCgqKkJhYWFFGX5Zil/++tmzZ9/9ekFBAVRUVGpVnF9+XV1dXSTfszz5/AiDJG9qicstrvRuYuD/l2BGfhmeFpQJfW60tLQUhw4dwtq1a9G4cWOsX78eAwYMYP3mnK1bt6Jjx44YO3asVC77lZubi82bNyMmJobtKFKJik/O6Wso49FH1OpypwoH0NP4eromDocDLS0taGlpoVGjRrXKyDAMSkpKvluMn//98uXL7369sLAQAGpVnF/+Xp06dVh/k62t9+/f49y5cwgICJDYMX9Uev/1+dEZALDU0wCXy8WePXuwfv16WFhYYP/+/ejRo4cYE1dP48aNsWrVKri5ueHOnTtS95iAj48PnJyc0Lp1a7ajSCUqPjln0aAObmcX1WofDIAODcQ3lsHhcKChoQENDQ2R3HpeWlr63WL8/Ovs7Gw8evTou2es5eXltb6U+/nfmpqarJTooUOHMGzYMInNxv+950a/53P5XTp+GIGrlqJHjx44c+YMunTpIp6gtTR16lQEBwdj586dmD59OttxKjx//hyHDh1CSkoK21GkFj3OoABOZRYgI7+sRq9lBAI8jriGrmoF+P333+Viot7qKCsr++5ZaFUu9X7+dWlpaUUp1rZMtbS0qnSWwTAMTE1NsXv3bomN79Xm500g4OPTk4dwbm8IMzMzEScTvZSUFPTq1Qvx8fFSs5K5i4sLmjZtilWrVrEdRWpR8SmAbC4PIRn5NbrcqcIBrJgc/OXpgY8fP2LTpk1wcHAQfUgFUF5eXqvi/PL3ioqKULdu3R8W57t373Du3Dn4+flBR0dH6LZ169YV2Qea7z03CgAfc7Jw3t8bz+LvQcAI0HGgI35ZuParbWTtudHly5cjISEBoaGhbEdBcnIy+vTpg4yMDOjq6rIdR2pR8SmI6o65AF9PVM0wDP7++2/MmzcPHTt2hL+/P9q0aSO+wOS7+Hw+Pn369MPiDAkJQf369dG6detKi5XL5UJDQ0Mk46KpJaqIeFMi9OdMwOdji1NfGFnbY4DHInCUlJGV8gAtO3+9JJAKB7A31ER3A00J/WnWTmlpKTp16oQ1a9Zg5MiRrGZxdHSEvb095syZw2oOaUfFp0CqU36Vrc5QUlKCgIAArF+/HlOmTIG3tzd9spRS7969Q5s2bZCZmYkGDRpUup1AIACXy631WWhBQQEGzfdD5yGjhR7neUIMDntNxKKwh1D+wXN35vXV8XNL7Vp9/5J0584djBs3Dg8fPkS9evVYyXDv3j2MHj0ajx49goYGraryPVR8Cia7iIfInGI8+c56fEY6arBppAFDzcqfq8rOzsaSJUvwzz//YOXKlZgyZYrCjf9Ju40bNyI+Ph6HDx+W2DFPPsnHkwLhk5onhp3GrYNbMSPk6g/300ZHFb8aydYHqj/++AMcDoeVSQIYhkGfPn0wceJEuLq6Svz4soaKT0EV8QRIzCtB7hczaejVYCaN2NhYeHl5oaCgAAEBAXI9678s+XxTy969eyU6XdXZZ4VI+VAq9GvPE2JwePZvWHQ5Se7O+ADg48ePMDc3x/HjxyU+Rdjly5cxa9YsPHz4kGZUqgLZGD0mIqepqoTuBpr4uaU2fjXSxc8ttdHdQLPaNxR06dIF4eHh8Pb2houLC0aOHInMzEwxpSZVFR4eDmVlZdjZ2Un0uPoaylCp5ImNZu0tof2TAS5vWYWyYi54pSV49iDq2w355dDgy96KIPXq1cPmzZvh5uaG0lLh5S8OAoEAixYtwpo1a6j0qoiKj9Qah8PB6NGjkZqaCisrK1hbW2PBggUoKChgO5rCYmOmFuDf50Yru4SkpKyMSQHBeP/yKfyGdIbf4I5IDDv9zXYChsFvfW0watQo/PPPP+Dz+WLNLEojR46EiYkJ/Pz8JHbMkydPQllZmfUba2QJXeokIpednY3Fixfj8uXLWLVqFSZPnkzjfxL0+aaWp0+fon79+hI/fm2e4wMAY1019PsJOHbsGIKCgpCVlYXJkydjypQpMjETyatXr9C5c2fcunULpqamYj0Wj8eDmZkZdu7cib59+4r1WPKEzviIyBkaGmL//v04d+4c9u/fD2tra5lZxkUeHDhwAL/88gsrpQcAtgYalV7u/BEVDmDTSAM6OjqYOnUqoqKicOnSJXC5XHTv3h0ODg4ICQlBcbH0Xgpt2rQpli9fDjc3NwgEopkkvjL79u1Dy5YtqfSqic74iFgxDIOTJ09i/vz5sLKygr+/P1q1asV2LLnFMAxMTExw4MAB2Nraspajts+NClNaWoqzZ88iKCgIMTExGDduHFxdXWFpaSmi1KIjEAhgb2+PSZMmwd3dXSzHKCoqQtu2bXH69GlYW1uL5Rjyis74iFhxOByMGTMGqamp6NSpE6ysrLBo0aKKyaSJaN28eRNqamqwsbFhNYelngYcmmhV+czvR6UHAOrq6hg9ejQuXbqE+Ph4GBgYYOTIkejcuTO2bt2KDx8+iCh97SkpKWH37t1YsmQJXr9+LZZjbNmyBba2tlR6NUBnfESiXr9+jcWLFyMsLAyrV6/G5MmTpW5me1k2btw42NnZYebMmWxHASC650YrIxAIcP36dQQFBeHixYsYMmQIXF1d0adPH6n4uVq6dClSUlJw6tQpke73w4cPMDY2xp07d2BiYiLSfSsCKj7CipiYGHh6eqK4uBiBgYFSteSMrHr79i2MjY3x7Nkz1mYPqYyonhv9nry8PISEhCAoKAgFBQVwcXHB5MmT0axZM5HsvyZKSkrQsWNHrF27FiNGjBDZfhctWoR3795hz549ItunIqHiI6xhGAbHjx/HggUL0K1bN6xbtw4tW7ZkO5bM8vf3R3JyMg4cOMB2FFYxDIO4uDgEBQXh+PHj6Nq1K1xdXTF8+HCoqalJPE94eDicnZ2RnJwMHR2dWu/v9evXsLCwQEJCgtSsCCFrqPgI64qKirBhwwYEBgbC3d0dixYtQt26ddmOJVMEAgFMTExw6NAh1sf3pElRURH+/vtvBAUFITk5Gc7OznB1dZX4qulubm5QU1PDtm3bar2vadOmoW7duvD39xdBMsXE/kVwovA0NTWxdOlSJCQk4OXLlxV3JYr7VnB5cuPGDWhoaKB79+4/3liBaGpqwtnZGTdu3EBERAQ0NDQwYMAAdO/eHXv27JHYTVbr1q1DaGgoIiIiarWfjIwMnDx5EgsXLhRRMsVEZ3xE6kRHR8PT0xNlZWUICAiQ+LyHsmjMmDHo2bMnZsyYwXYUqVdeXo7Lly8jKCgIN27cwIgRI+Dq6go7OzuxznRz4sQJrFy5EnFxcTW+5Dp+/Hi0b98e3t7eIk6nWKj4iFRiGAZHjx7FwoULYWNjg3Xr1qFFixZsx5JKb968gYmJiVTe1CLt3rx5g8OHDyMoKAgMw2DKlCn47bff0KhRI5Efi2EYDB8+HN26dcOSJUuq/fr4+HgMGTIEGRkZNBRQS3Spk0glDocDJycnpKWlwczMDJaWlli6dCk+ffrEdjSpc+DAAYwcOZJKrwYMDAwwd+5cpKSkYN++fUhPT4epqSlGjBiBc+fOoby8XGTH4nA42LZtGwIDA5Genl7t1y9evBhLliyh0hMBOuMjMuHVq1dYuHAhbty4AR8fH0ycOFEqntNim0AgQNu2bXHkyBF069aN7ThyobCwECdOnMDevXvx/PlzTJo0CVOmTEHbtm1Fsv/Nmzfj1KlTuHHjRpV/hm/evIkpU6YgLS2NlTtT5Q29cxCZ0LRpUwQHB+PUqVPYsWMHunXrhrt377Idi3XXr19H3bp10bVrV7ajyA1tbW24uroiMjISV69eRVlZGezs7NCrVy8cOnQIRUVFtdq/h4cHSkpKsG/fviptzzAMFi1ahFWrVlHpiQpDiIzh8/lMcHAw07RpU2bcuHHM8+fP2Y7Eml9//ZXZtm0b2zHkXmlpKfO///2PGTx4MFO/fn3G3d2diY6OZgQCQY32l5CQwOjp6THZ2dk/3Pb06dNMhw4dGD6fX6NjkW/RpU4is7hcLvz9/bFlyxZ4eHhgwYIF0NLSYjuWxOTk5KBdu3Z4/vw5dHV12Y6jMF69eoUDBw5g3759qFu3LlxdXeHs7IyGDRtWaz+LFy/G48ePceLECXB5AiTlleDtFzPb6Gsow7yeKrpbdsK6deswdOhQMX1HioeKj8i8ly9fYuHChQgPD4evry8mTJigEON/vr6+ePz4MYKCgtiOopAEAgFu3ryJoKAgXLhwAYMGDYKrqyv69u1bpZ+/4uJiODiOhfMyfxRpNhQ6l2k5n4/spGgsGD0IjbWqP5cpEY6Kj8iNyMhIzJo1CxwOBwEBAXI9g4lAIECbNm1w7NgxGt+TAh8+fMCRI0cQFBSEvLw8uLi4wMXFBc2bN6/0NXG5xbj6shDlDAMlpe8s1MwwUFHi/HD1ClJ18v+xmCgMGxsb3Lt3DzNmzMDo0aMxYcIEvHz5ku1YYnH16lXo6urSkjRSon79+vDw8EBcXBxCQ0ORm5uLzp07Y+DAgThx4gRKS0u/2v7zeoUCjlKlpXfyrxkI2+YDcDgoZ4DrWVzE5UrvAryyhIqPyBUlJSVMnDgR6enpMDIyQqdOnfDXX3+By+WyHU2kdu3aBXd3d7HONEJq5vP6gK9evcKkSZOwa9cuNG3aFJ6enkhKSkI2l1ftRXoBVJRfdhFPPMEVCBUfkUtaWlpYuXIl4uPj8ejRI7Rr1w4hISFyMf9ndnY2rl+/DicnJ7ajkO/Q0NCAk5MTrl27hqioKGhra2Pw4MHwOf4Pymv4c1jOAJE5dNZXWzTGRxTC3bt34enpCWVlZQQGBsr0w94+Pj54+vQprcUmgwpKediR/AEM59tzjtdpiTi10hPvXmTCxK4fOBwOGjZrhQEei7/aTpkDeJg3ENk6hoqI/uSIQrCzs0NUVBSmT5+OUaNGYeLEiXj16hXbsapNIBBgz549cHd3ZzsKqYGUjzwoC7njs5xXhsOzJ6HzkDFYdiMDFv2H4+H180L3wQGQmFci5qTyjYqPKAwlJSX89ttvSEtLQ4sWLdCxY0esWLGi1jNxSFJYWBjq16+PLl26sB2F1MDbYr7Qsb2XiffBL+fBboI7lFVVYdFvOJqadRa6j3IGyC3mizmpfKPiIwqnbt26WL16NeLi4pCSkoJ27drhyJEjkIWr/rt376abWmSQQCDA8+fP8So7R+jXC969gY6+4Vf/X+sZVr66eilf9seq2UTFRxRWixYtcPz4cRw5cgQbN26EnZ0doqOj2Y5VqdevX+PGjRt0U4sU4/P5ePz4Mc6ePQs/Pz/89ttvsLKygo6ODuzs7JCe/FDo67R/0kfB2+yvPnzl51R+KV5dmd66a0OF7QCEsM3e3h7R0dE4dOgQHB0d0bdvX/j6+qJJkyZsR/vKvn37MHr0aGhra7MdReHxeDw8fvwYKSkpX/2TkZEBfX19mJmZwczMDL1798b06dNhamoKXV1d3HtThDvZRd9c7mzewRpKKiqIOLob3ce4IjX8El4mx6O11beLMKtwAD2N7zzwTn6I7uok5AuFhYXw8/PDzp074enpiblz50JDg/3ZMvh8PoyMjHDq1Cka35OgkpISPHr06KtyS01NRWZmJpo2bVpRcJ//MTEx+e56eVyeANuT88AX8q77KuUB/l7lhfcvn8LErh8A4KfmremuTjGg4iNEiKdPn2LBggWIiorC2rVrMXbsWFbH1S5evIilS5fi/v37rGWQZ1wuF2lpaRXF9rnkXrx4gdatW39TcMbGxqhTp06NjnUqswAZ+WU1zmqsq4aRrXVq/HpCxUfId926dQuenp7Q0NBAQEAAa1OEjRgxAkOHDoWbmxsrx5cX+fn5SE1N/arcUlJSkJOTA2Nj428Krk2bNlBVFe3k0NlcHkIy8qs9cwvw72XOCca6MNSkCatrg4qPkB/g8/k4ePAglixZgv79+8PX1xeNGzeW2PGzsrLQvn17vHjxgsb3quj9+/fflFtKSgo+fPgAU1PTr8rN1NQUrVq1goqK5G55+DxXZ3XKT4UDmqhaRKj4CKmiwsJC+Pj4YM+ePfDy8sLs2bMlMv63atUqZGVlYefOnWI/lixhGAZv3779ptxSUlJQUlLyTbmZmZmhefPmUrNkVXXKj0pPtKj4CKmmzMxMzJ8/H/fv38e6deswevRosY3/8fl8tGrVCmfOnEHnzsIfaJZ3DMMgKytLaMFxOByYm5t/VW5mZmZo3LixTDzrmF3EQ2ROMZ4UlAldj48BYKSjBptGGnR5U4So+AipofDwcHh6eqJu3boICAgQy92WFy5cwPLlyxETEyPyfUubzw95/7fcUlNToaWl9U25mZmZQU9PTyYK7keKeAIk5pUg94sV2PU0lNGhQR26e1MMqPgIqQU+n48DBw5gyZIlGDRoEHx8fGBoaCiy/f/yyy/4+eef8fvvv4tsn2wrLy9HZmbmN+WWlpaGhg0bflNwpqamaNCgAduxiRyh4iNEBAoKCuDj44O9e/di9uzZmD17do1vd//s1atX6NChA168ePHdZ8OkVVlZGTIyMr4qt88PeTdu3Pibs7d27dpBR4du0yfiR8VHiAg9efIE8+fPR1xcHNatW4dff/21SpfiuDwBkvJK8PaLS12Jd24gJ+4Wtm5cL4HkNVdcXIz09PRvnoF79uwZmjdvLvQhb01NTbZjEwVGxUeIGNy4cQNeXl7Q0dFBQEAALC0thW6XzeUh4k0xMoXc3MArLYa6eh0Y6arD1kADhlrs3tzw6dOnioe8v/wnKysLRkZG3xRc27Ztoa6uzmpmQoSh4iNETPh8Pvbt24dly5ZhyJAhWLNmDRo1alTxdWm9nf3jx49Cn4HLzc2FiYnJNwXXunVrkT/kTYg4UfERImb5+flYs2YN9u3bh7lz58LT0xMphQzrDzC/e/dO6CMChYWFQh/ybtmyJZSVaXJkIvuo+AiRkMePH2PevHl4/akMI/32gVGqfolUd8oqhmGQk5Mj9BEBHo8n9CHvZs2aycUjAoRUhoqPEAnbGfUEeSraNZ5BRNgkxQzD4OXLl9+UW0pKClRVVYUWXKNGjajgiEKi4iNEgr63LE1Bbg7Orl2IZ3H3oKapBbsJ7rAbP/Wb7ZTAoO3r+3j0MLGi3FJTU6Gjo/NNuZmamkJPT08C3xkhsoMWoiVEgpLySiDsHEsgEODgrAkw6z0Y43x3o+DNa+yd9iv0WrSBsa3DV9uWlpbin4TH0M3LRY8ePeDu7g5TU1PUq1dPIt8DIbKOio8QCXpbzBd6Q8ur5HhwP75H36lzAQANmrZEV0dnJF4O/ab4VNXrYLjTZPzcklZqIKQmqPgIkaBSvkDo73/MfonC3Bys6GlU8XsCAR8tO3ev1n4IIT9GxUeIBKkrC7+hRdegCeo3bo65Z6JrtR9CyI/R3x5CJEhfQxkqQgb5mrW3hLqWNsIPbAavpBgCPh85j1PxMjn+m21VOICeBj1PR0hNUfERIkEWDepA2G3USsrKmBQYgtfpD7Hu5y5Y5WCCv1d6ofRTwTfbMgA6NKjdBNiEKDJ6nIEQCTuVWYCM/LIav17Yc3yEkKqjMz5CJMzWQEPo5c6qUOEANo3EP18nIfKMio8QCTPUUoVDE61ql9/nuTqrOl0ZIUQ4Kj5CWGCpp1Gt8pPk6gyEyDsa4yOERdlFPETmFOOJkPX4VDj/3shipKMGm0YadKZHiIhQ8REiBYp4AiTmlSD3ixXY9TSU0aFBHWiq0oUZQkSJio8QQohCoY+ShBBCFAoVHyGEEIVCxUcIIUShUPERQghRKFR8hBBCFAoVHyGEEIVCxUcIIUShUPERQghRKFR8hBBCFAoVHyGEEIVCxUcIIUShUPERQghRKFR8hBBCFAoVHyGEEIVCxUcIIUShUPERQghRKFR8hBBCFAoVHyGEEIVCxUcIIUShUPERQghRKFR8hBBCFMr/A37q4oDGneXtAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# construction du graphe g1:\n", "g1= Graphe()\n", "g1.ajouter_arete(\"a\",\"b\")\n", "g1.ajouter_arete(\"a\",\"c\")\n", "g1.ajouter_arete(\"b\",\"d\")\n", "g1.ajouter_arete(\"c\",\"d\")\n", "g1.ajouter_arete(\"b\",\"e\")\n", "g1.ajouter_arete(\"e\",\"f\")\n", "g1.ajouter_arete(\"f\",\"g\")\n", "g1.ajouter_arete(\"f\",\"c\")\n", "g1.ajouter_arete(\"d\",\"a\")\n", "g1.ajouter_arete(\"e\",\"d\")\n", "g1.ajouter_arete(\"g\",\"h\")\n", "g1.ajouter_arete(\"h\",\"b\")\n", "\n", "print(g1)\n", "print(g1.sommets())\n", "print(g1.voisins(\"b\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

  • parcours en largeur

    • " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def parcours_en_largeur(g,s_depart):\n", " \"\"\" fonction qui retourne le parcours en largeur du graphe g à partir du sommet s_depart\n", " entrée : g type graphe et s_départ chaine de caractère\n", " sortie : une liste de cahinae de caractère\n", " précondition : s_depart est un sommet de g\"\"\" \n", " pass\n", "\n", "#tests\n", "print(g1)\n", "for s in g1.sommets():\n", " print(\"à partir de \",s,\"->\",parcours_en_largeur(g1,s))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

  • detection de cycles

    • \n", "

    A quel moment dans un parcours sait-on que l'on a un cycle ?

    " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def detection_cycle(g,s_depart):\n", " \"\"\" fonction qui detecte la presence d'un cycle dans un graphe g à partir d'un sommet s_depart\"\"\"\n", " pass\n", "\n", "#tests\n", "detection_cycle(g1,\"c\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

  • parcours en profondeur

    • " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def parcours_en_profondeur(g,s_depart):\n", " \"\"\" fonction qui retourne le parcours en profondeur du graphe g à partir du sommet s_depart\n", " entrée : g type graphe et s_départ chaine de caractère\n", " sortie : une liste de chaine de caractère\n", " précondition : s_depart est un sommet de g\"\"\"\n", " pass\n", "\n", "#tests\n", "for sommet in g1.adj:\n", " print(\"à partir de \",sommet,'->',parcours_en_profondeur(g1,sommet))\n", "print(g1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

    bonus 1
  • Trouver un chemin entre deux sommets

    • \n", "L'idée est d'utiliser une pile qui contient un tuple ( sommet, [une liste] ),
    ce tuple sera initialisé à (s_depart,[s_depart])
    puis ( successeur, [chemin pour arriver au successeur])
    \n", "et on s'arrete quand le successeur est s_arrivée.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def unchemin(g,s_depart,s_arrivee):\n", " \"\"\" fonction qui retourne un chemin dans un graphe g entre deux sommets s_depart et s_arrivée.\n", " le chemin sera donné dans une liste qui contiendra les sommets parcourus\"\"\"\n", " pile=[(s_depart,[s_depart])] \n", " pass\n", "\n", "\n", "# tests\n", "unchemin(g1,\"f\",\"c\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

    bonus 2
  • Tous les chemins entre 2 sommets

    • " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def touschemin(g,s_depart,s_arrivee):\n", " \"\"\" fonction qui retourne tous les chemins entre deux sommets \"\"\" \n", " pile=[(depart,[depart])]\n", " TousChem=[] # liste qui contiendra tous les chemins\n", " pass\n", " \n", "\n", "\n", "\n", "\n", "#tests\n", "touschemin(g1,\"g\",\"f\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

    bonus 2 bis
  • Tous les chemins entre 2 sommets

    • " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def pluscourtchemin(g1,s_depart,s_arrivée):\n", " \"\"\" retourne le plus court des chemins entre deux sommets\"\"\"\n", " pass\n", "\n", "\n", "\n", "#tests\n", "pluscourtchemin(g1,\"g\",\"f\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

    bonus 3
  • Tous les cycles d'un graphe

    • " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def touslescycles(g):\n", " \"\"\" retourne une liste de tous les graphes d'un cycle\"\"\" \n", " TouslesCycles=[]\n", " pass\n", " \n", "#test \n", "touslescycles(g1)" ] } ], "metadata": { "interpreter": { "hash": "cd8ac7ed5329ff1f59a8356dfddf06d159cf18414acbfd7b13d1d5cd1cbb5d7d" }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.7" } }, "nbformat": 4, "nbformat_minor": 2 }