{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Algo - Graphe - Composantes connexes\n", "\n", "Les graphes sont un outil tr\u00e8s utilis\u00e9 pour mod\u00e9liser un ensemble de relations entre personnes, entre produits, entre consommateurs. Les utilisations sont nombreuses, syst\u00e8mes de recommandations, mod\u00e9lisation de la propagation d'une \u00e9pid\u00e9mie, mod\u00e9lisation de flux, plus court chemin dans un graphe.\n", "\n", "Un graphe est d\u00e9crit par un ensemble *V* de noeuds (ou *vertices* en anglais) et un ensemble d'arcs (ou *edges* en anglais) reliant deux noeuds entre eux. Chaque arc peut \u00eatre orient\u00e9 - un seul chemin d'une extr\u00e9mit\u00e9 \u00e0 l'autre est possible - ou pas.\n", "\n", "L'algorithme propos\u00e9 dans ce notebook calcule les composantes connexes dans un graphe non orient\u00e9. Un [graphe connexe](https://fr.wikipedia.org/wiki/Graphe_connexe) v\u00e9rifie la propri\u00e9t\u00e9 suivante : pour tout couple de noeuds, il existe un chemin - une s\u00e9quence d'arcs - reliant ces deux noeuds. Si un graphe est connexe, il contient une seule composante connexe, s'il ne l'est pas, alors on peut le diviser en sous-graphe connexe de telle sorte qu'il n'existe aucun arc reliant deux noeuds appartenant \u00e0 des sous-graphes distincts.\n", "\n", "Un graphe est enti\u00e8rement d\u00e9fini par sa [matrice d'adjacence](https://fr.wikipedia.org/wiki/Matrice_d%27adjacence) $M=(m_{ij})$ : $m_{ij} = 1$ si les noeuds $V_i$  et $V_j$ sont reli\u00e9s entre eux, 0 sinon. Si le graphe est orient\u00e9 alors $m_{ij} = m_{ji}$ : la matrice est sym\u00e9trique."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "// look up into all sections and builds an automated menu //\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Enonc\u00e9\n", "\n"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q1 : construire une matrice d'adjacence sym\u00e9trique al\u00e9atoire\n"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": ["def random_adjacency_matrix(n, alpha=0.3):\n", "    # alpha est le taux de remplissage, plus il est faible, plus la probabilit\u00e9\n", "    # d'avoir plusieurs composantes connexes est grande.\n", "    # ...\n", "    return None"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q2 : calculer les valeurs propres et les trier par ordre croissant\n", "\n", "Il faudra recommencer avec plusieurs valeurs de *alpha* diff\u00e9rentes pour avoir une id\u00e9e de ce qu'il se passe."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q3 : que fait l'algorithme suivant\n", "\n", "On cr\u00e9e un tableau ``T=list(range(n))`` o\u00f9 ``n`` est le nombre de noeuds.\n", "\n", "Pour tous les arcs $V=(E_i, E_j)$ faire ``T[i] = T[j] = min(T[i], T[j])``.\n", "\n", "Recommencer tant qu'une valeur de ``T`` est mise \u00e0 jour."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q4 : construire un algorithme qui retourne les composantes connexes d'un graphe\n"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## R\u00e9ponses"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q1 : construire une matrice d'adjacence sym\u00e9trique al\u00e9atoire\n", "\n", "On change un peu l'\u00e9nonc\u00e9 et on remplace les valeurs nulles sur la diagonale par l'oppos\u00e9 du degr\u00e9 de chaque noeud. Le degr\u00e9 d'un noeud est le nombre d'arc reli\u00e9 \u00e0 ce noeud. De cette fa\u00e7on, la somme des coefficients sur une ligne est nulle. Donc il existe un vecteur propre associ\u00e9 \u00e0 la valeur propre 0."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["array([[-2.,  0.,  1.,  0.,  1.],\n", "       [ 0., -3.,  1.,  1.,  1.],\n", "       [ 1.,  1., -2.,  0.,  0.],\n", "       [ 0.,  1.,  0., -2.,  1.],\n", "       [ 1.,  1.,  0.,  1., -3.]])"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["import numpy\n", "\n", "def random_symmetric_adjacency_matrix(n, alpha=0.3):\n", "    rnd = numpy.random.rand(n, n)\n", "    rnd = (rnd + rnd.T) / 2  # sym\u00e9trique\n", "    rnd2 = rnd.copy()  # copie\n", "    rnd2[rnd <= alpha] = 1\n", "    rnd2[rnd > alpha] = 0\n", "    for i in range(n):\n", "        rnd2[i, i] = 0  # 0 sur la diagonale\n", "        rnd2[i, i] = - rnd2[i, :].sum()\n", "    return rnd2\n", "\n", "random_symmetric_adjacency_matrix(5, alpha=0.5)"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 11/11 [00:01<00:00,  9.19it/s]\n"]}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAEWCAYAAAB2X2wCAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy89olMNAAAACXBIWXMAAAsTAAALEwEAmpwYAAAtlklEQVR4nO3deXwU9f3H8dcnCSSEI9wIJCEIiEQQxITDo1oRq3jgiVBRUOqt7c9e0npVpda72oq1HoCKB6CiVPE+Kx4kEeQIIDdJuMIVjhByfX9/7ELXSMgCm8zu5v18PPJgd+ebmc/M7r6ZfOc7M+acQ0REIl+M1wWIiEhoKNBFRKKEAl1EJEoo0EVEooQCXUQkSijQRUSihAJd6oSZPWVmd9TBck41s/zaXk6wzGeimW01s9n+1643sw1mttPMWvn/PbKG+aT628XWTeWHzsxWmdnpXtdRH8V5XYBEHzMbDfzKOXfS3tecc9d5V5GnTgIGA8nOuV1m1gB4FBjgnPve36ZJTTNxzq0Jpl0wzOwzYLJz7tlQzE/Ch/bQ6wEzq7P/uOtyWRGiE7DKObfL/7wdkAAs9K4kiVYK9Ajl/7P2T2aW6/9zfqKZJfinnWpm+WZ2q5mtByaaWbyZPWZma/0/j5lZfJX2fzazTf55XxawrCQze8HMCs1stZndbmYx/mmjzWyWmf3dzDYDU4CngIH+LoJt/naTzGxcwDyvNrNlZrbFzGaYWYeAac7MrjOzpWa2zczGm5lVsx0a+ee91cxygcwq0zuY2ev+2lea2a8PsE0bmdkj/nUsMrMvzayRf9p5ZrbQX89nZtajpmWY2Rjg2YBt8QqwxP9r28zsk4D17XqgGswszd8uLuA9ec7M1plZgZmN29sd439PvjSzh/3bZaWZneWf9lfgZOAJf01P7Gc77F3WKDNb4/9M3BYwvep7WW03l5n1M7NsM9tuvm6mR6vb/hICzjn9ROAPsApYAKQALYFZwDj/tFOBcuABIB5oBNwDfAO0BdoAXwH3Vmn/qL/9KcAuoLt/+gvAW0BTIA34ARjjnzba/7s34+vCa+R/7csq9U4KqO80YBPQ17+8fwJfBLR1wNtAcyAVKATOrGY73A/8178NUvzbJN8/LQbIAe4EGgJHAiuAX1Qzr/HAZ0BHIBY4wV/fUf7tMRhoAPwRWOaf5wGXUXVb+LefA+KqrG/XGmr40e8B04F/A4397+ls4NqAZZYBV/vncT2wFjD/9M/wdYlV99nau6xn/O9nb2AP0KPqexnw+cmv8tk83f/4a+By/+Mm+LqaPP/+ROuP5wXo5xDfON+X5rqA50OA5f7HpwKlQELA9OXAkIDnv8DXFbC3fTnQOGD6VOAOfyCUAukB064FPvM/Hg2sqVLbj0LM/9q+EACeAx4MmNbEH0Bp/ucOOKlKLWOr2Q4rCAh74Br+F+j991Pbn4CJ+5lPDLAb6L2faXcAU6u0LfBvtwMuo+q24ACBXkMN+34PX7fNHqBRwPQRwKcBy1wWMC3R/7tH+J9/RnCBnhzw2mxgeNX3MuDzU12gfwHcDbT2+jtTH37U3xnZ8gIerwY6BDwvdM6VBDzv4G9TXfut7n/9vIHTW+PbK636ux2rqSMYHYDv9j5xzu30d9d0xBcGAOsD2hdT/QHBDvx0O+zVCeiwt9vHLxbfHn1VrfH1bS+vZhn75uucqzSzPH+9ZQexjJocqIZAnfC9J+sCeqJi+PF22Lf9nHPF/nYHe1A12PfgQMbg++twsZmtBO52zr19CPORICjQI1tKwONUfH9W71X1Mppr8QXBwmratzCzxgGhnoqv+2ITvtDqBOQGTCs4wLJquoTn3loAMLPGQKsq8wzWOnzbIXC99soDVjrnugUxn01ACdAF+L7KtLVAr4B6zb/MAnx7ysEu43BqCJTnX25r51z5ISzncC+xugvfXv9eR1S7IOeWAiP8x1wuBF4zs1ZVdh4kRHRQNLLdaGbJZtYSuA3fAcnqvALcbmZtzKw1vj7fyVXa3G1mDc3sZOAcYJpzrgJfl8dfzaypmXUCfruf3w20AUg2s4YHqOVKM+tjvgOz9wHfOudWHXh192sq8Ccza2Fmyfj68veaDeww38HhRmYWa2Y9zSyz6kycc5XABOBR/0HOWDMb6K9vKnC2mQ0y37DD3+EL1K8OZhk1qaGGwHbrgA+AR8ysmZnFmFkXMzslyEVtwNfXf6jmAkPMrKWZHQH8X3UNzWykmbXxr9s2/8uVh7FsOQAFemR7Gd8XewW+P9PHHaDtOCAbmAfMx9flEdh+PbAV397oS/j65xf7p92Mb69sBfClf7kTDrCsT/DtMa83s01VJzrnPsLXL/06vj3sLsDwA8zvQO7G1x2yEt+2eDFgORX4/mPq45++Cd+ok6Rq5vV7fNsmC9iC76ByjHNuCTAS38HbTcC5wLnOudJDWEZN9lvDftpdge8gbC6+9+01oH2Qy3gcuNg/AuYfh1Dji/j+gliFb5sfaEfiTGChme30L3e4c273ISxTgrD3qLdEGDNbhe/A1kchmNep+E40ST7ceYmId7SHLiISJRToIiJRQl0uIiJRQnvoIiJRwrNx6K1bt3ZpaWleLV5EJCLl5ORscs612d80zwI9LS2N7OxsrxYvIhKRzGx1ddPU5SIiEiUU6CIiUUKBLiISJcLq4lxlZWXk5+dTUlJSc2M5ZAkJCSQnJ9OgQQOvSxGREAqrQM/Pz6dp06akpaVh+79BjRwm5xybN28mPz+fzp07e12OiIRQjV0uZjbBzDaa2YJqppuZ/cN8txObZ2Z9D7WYkpISWrVqpTCvRWZGq1at9FeQSBQKpg99Er4rplXnLKCb/+ca4F+HU5DCvPZpG4tEpxq7XJxzX5hZ2gGaDAVecL5rCHxjZs3NrL3/ms0iIvWac45NO0tZs2UXa7YUs2bzbk47ui29kg/1CsvVC0Ufekd+fOurfP9rPwl0M7sG3148qampVSdHrW3btvHyyy9zww03eF2KiNSCkrIK8rfuJm9LsS+0txSzenPxvue7yyr2tTWDlk0ahm2gB8059zTwNEBGRka9uSrYtm3bePLJJxXoIhHKOcfmXaWs2eIP6c3FrPaHdd6WYtZvLyHwOoeNGsSS2jKR1FaJnNSt9b7HqS0T6di8EQkNYmulzlAEegE/vrdlMod2b8iwMXnyZP7xj39QWlpK//79efLJJ0lKSuL6669n5syZtG/fnvvuu48//vGPrFmzhscee4zzzjuPSZMmMX36dIqKiigoKGDkyJHcddddjB07luXLl9OnTx8GDx7Mhg0buPDCCzn//PMBuOyyyxg2bBhbt25lxowZFBcXs3z5ci644AIefPBBAD744APuuusu9uzZQ5cuXZg4cSJNmjRh7NixzJgxg7i4OM444wwefvhhpk2bxt13301sbCxJSUl88cUXHm5Nkciwp7yCgq2794X06s3/29vO21LMrtKKH7Vv1yye1JaJnNBlb2A3IrVlY1JbJtK6SUNPjlWFItBnADeZ2atAf6AoFP3nd/9nIblrtx92cYHSOzTjrnOPOWCbRYsWMWXKFGbNmkWDBg244YYbeOmll9i1axennXYaDz30EBdccAG33347H374Ibm5uYwaNYrzzjsPgNmzZ7NgwQISExPJzMzk7LPP5v7772fBggXMnTsXgM8//5y///3vnH/++RQVFfHVV1/x/PPPM3nyZObOncucOXOIj4+ne/fu3HzzzTRq1Ihx48bx0Ucf0bhxYx544AEeffRRbrzxRqZPn87ixYsxM7Zt2wbAPffcw/vvv0/Hjh33vSYiPs45vs8v4sulhQGBvZu1Rbt/tJcdHxfjC+qWiQzs0mrf406tEklukVhre9mHo8ZAN7NXgFOB1maWD9wFNABwzj0FzASGAMuAYuDK2iq2Lnz88cfk5OSQmem7x+/u3btp27YtDRs25MwzfYN9evXqRXx8PA0aNKBXr16sWrVq3+8PHjyYVq1aAXDhhRfy5Zdf7tsT3+uUU07hhhtuoLCwkNdff52LLrqIuDjfWzFo0CCSknx9a+np6axevZpt27aRm5vLiSeeCEBpaSkDBw4kKSmJhIQExowZwznnnMM555wDwIknnsjo0aMZNmwYF154Ya1tK5FIsnnnHqbPKWBqdh4/bNgJQJumvr3sfp1b7gvs1FaJdGqZSJum8RE3IiyYUS4japjugBtDVpFfTXvStcU5x6hRo/jb3/72o9cffvjhfW9uTEwM8fHx+x6Xl5fva1f1A1DdB+KKK65g8uTJvPrqq0ycOHHf63vnCxAbG0t5eTnOOQYPHswrr7zyk/nMnj2bjz/+mNdee40nnniCTz75hKeeeopvv/2Wd955h+OPP56cnJx9/8mI1CcVlY4vlhYyNSuPjxZtoKzC0TulOfdd0Iuzj21PUqPoOls6rM4UDQeDBg1i6NCh3HLLLbRt25YtW7awY8eOoH//ww8/ZMuWLTRq1Ig333yTCRMm0LRp05/MY/To0fTr148jjjiC9PT0A85zwIAB3HjjjSxbtoyuXbuya9cuCgoK6NChA8XFxQwZMoQTTzyRI488EoDly5fTv39/+vfvz7vvvkteXp4CXeqVNZuLmZqdx2s5+azfXkLLxg25YmAawzJS6H5EU6/LqzUK9CrS09MZN24cZ5xxBpWVlTRo0IDx48cH/fv9+vXjoosuIj8/n5EjR5KRkQH4ukF69uzJWWedxUMPPUS7du3o0aPHT7pj9qdNmzZMmjSJESNGsGfPHgDGjRtH06ZNGTp0KCUlJTjnePTRRwH4wx/+wNKlS3HOMWjQIHr37n3wG0IkwpSUVfDegvVMycrj6xWbiTH42VFtuPPcdE7v0Y6GcdF/LULP7imakZHhqt7gYtGiRfTo0cOTekJh0qRJZGdn88QTT9TYtri4mF69evHdd9/t6zOvS5G+rUXA10W6oGA7U7LX8NbctewoKSelZSOGHZ/CxRnJtE9q5HWJIWdmOc65jP1N0x66Bz766CPGjBnDLbfc4kmYi0S6rbtKeXNuAVOz81m0bjvxcTGc1fMIhmWmMKBzK2JiIutgZqhoD72e0raWSFNZ6Zi1fBNTsvL4YOEGSisq6dUxiWGZKZzXu0PUHeCsTkTtoTvnIm6oUKTx6j9xkUORv7WYadn5vJaTT8G23SQ1asAv+6cyLCOF9A7NvC4vrIRVoCckJLB582ZdQrcW7b0eekJCgteliFSrpKyCD3I3MC07jy+XbQLgpK6tGXvW0QxObxeWJ/WEg7AK9OTkZPLz8yksLPS6lKi2945FIuEmd+12pmbnMX1OAUW7y+jYvBG/GdSNi49PJrlFotflhb2wCvQGDRroLjoi9UzR7jJmzC1gSnYeCwq20zA2hl/0PIJLM1I4oUv9PcB5KMIq0EWk/ijcsYcH31vMjO/Xsqe8kh7tm/GXc9M5/7iONE9s6HV5EUmBLiJ1yjnHtOx8/jpzEbtLKxiWmczwzFR6dtQQ3sOlQBeROrNq0y7+PH0+Xy3fTL+0ltx3YS+6tm3idVlRQ4EuIrWurKKSZ/67gsc/WkrD2Bj+ekFPRmSmqn88xBToIlKr5uVv49bX57No3XbOPOYI7h56DO2aadhsbVCgi0itKC4t59EPfmDCrJW0bhLPUyOP58yeR3hdVlRToItIyH3+QyG3TZ9P/tbd/LJ/KreeeXS9OTXfSwp0EQmZLbtKufftXKbPKeDINo2Zeu1A+nVu6XVZ9YYCXUQOm3OON+cWcM9/ctm5p5xfn9aVG37eVafo1zEFuogclrwtxdz25gK++KGQ41Kbc/+Fx0b1XYHCmQJdRA5JRaVj4qyVPPLBD8QY3H3eMYwc0IlYDUX0jAJdRA5a7trtjH1jHvPyixh0dFvuPb8nHZpH392BIo0CXUSCVlJWweMfL+XpL1bQIrEB/xxxHOcc216Xuw4TCnQRCcpXyzfx5zfms2pzMcMykvnzkB66iFaYUaCLyAEVFZfx15m5TM3Op1OrRF7+VX9O6Nra67JkPxToIrJfzjnemb+Ov8zIZWtxKded0oX/O72bhiKGMQW6iPzE2m27ufOtBXy0aCO9Oibx/FWZHNNBl7cNdwp0EdmnstIx+dvVPPDuYiod3H52D0afkEZcbIzXpUkQFOgiAsAPG3Yw9vV5fLdmGyd3a819F/QipaXu4xlJFOgi9VxpeSXjP13Gk58to0l8HH+/tDfn9+mooYgRSIEuUo/t2lPOdZNz+O/STVxwXEduP7sHrZrEe12WHCIFukg9ta24lNETs5hfUMRDFx/LJRkpXpckhymoIx1mdqaZLTGzZWY2dj/TU83sUzObY2bzzGxI6EsVkVBZX1TCsH9/Te667fzrsr4K8yhR4x66mcUC44HBQD6QZWYznHO5Ac1uB6Y65/5lZunATCCtFuoVkcO0atMuRj73LduKy3j+yn4M7NLK65IkRILpcukHLHPOrQAws1eBoUBgoDugmf9xErA2lEWKSGjkrt3OFRNmU+kcr1w9gF7JGlseTYLpcukI5AU8z/e/FugvwEgzy8e3d37z/mZkZteYWbaZZRcWFh5CuSJyqLJWbeHSp7+mYawx9dqBCvMoFKqzBUYAk5xzycAQ4EUz+8m8nXNPO+cynHMZbdq0CdGiRaQmny7eyOXPfUubpvFMu/4EurZt4nVJUguCCfQCIPCISbL/tUBjgKkAzrmvgQRAV+8RCQNvzS3g6hey6dq2CdOuHUhHXbc8agUT6FlANzPrbGYNgeHAjCpt1gCDAMysB75AV5+KiMde+HoV/zdlLhlpLXjl6gEaYx7lajwo6pwrN7ObgPeBWGCCc26hmd0DZDvnZgC/A54xs1vwHSAd7ZxztVm4iFTPOcc/P1nGox/+wOk92vHEL4/TVRLrgaBOLHLOzcR3sDPwtTsDHucCJ4a2NBE5FJWVjnvfyWXirFVc1DeZBy7qpYtr1RM6U1QkipRVVHLra/N4Y04BV53YmdvP7kGMbtpcbyjQRaJESVkFN738HR8t2sjvzziKG3/eVRfYqmcU6CJRYHtJGVc/n83sVVu49/yeXD6gk9cliQcU6CIRbtPOPYyaMJsl63fw2KV9GNqn6nl/Ul8o0EUiWP7WYq54bjZri3bzzKgMft69rdcliYcU6CIRatnGHVz+3Gx27iln8pj+ZKS19Lok8ZgCXSQCzcvfxqgJs4mNiWHqtQPp0b5Zzb8kUU+BLhJhvlq2iatfyKZlk4ZMHtOfTq0ae12ShAkFukgEeX/hem5+eQ5prRN5cUx/2jVL8LokCSMKdJEIMTU7j7Gvz6N3SnMmjs6keWJDr0uSMKNAF4kAz/53BePeWcTJ3Vrz78uPJ7GhvrryU/pUiIQx5xwPf7CE8Z8u5+xe7Xn00t7Ex+kiW7J/CnSRMFVR6bjjrQW8/O0aRvRLZdz5PYnVdVnkABToImGotLyS306dy9vz1nHDqV34wy+667osUiMFukiYKS4t57rJ3/HFD4X8ecjRXPOzLl6XJBFCgS4SRoqKy7hy0mzm5m3jwYuOZVhmSs2/JOKnQBcJExu3l3D5c7NZuWkXT17WlzN7tve6JIkwCnSRMLB1VynDn/6G9dtLmHhlJid21T3W5eAp0EU8tqe8gmtfzCF/225e+lV/MnWRLTlEutGgiIecc9z62jxmr9rCw5f0VpjLYVGgi3josY+W8ubctfzhF905r3cHr8uRCKdAF/HI6zn5PP7xUi45PpkbTtXQRDl8CnQRD3yzYjNj35jHCV1a8dcLeumkIQkJBbpIHVteuJNrX8yhU6vG/Gvk8TSM09dQQkOfJJE6tHnnHq6cmEVcjDFxdCZJjRp4XZJEEQ1bFKkjJWUVXPNiDhu2l/DKNQNIaZnodUkSZRToInWgstLx+2nfk7N6K09e1pe+qS28LkmikLpcROrAox/+wNvz1jH2rKMZ0kun9EvtUKCL1LKp2Xk88ekyRvRL4dqfHel1ORLFFOgiteirZZv48xvzOblba+4Z2lPDE6VWBRXoZnammS0xs2VmNraaNsPMLNfMFprZy6EtUyTyLNu4g2sn53Bkm8aMv6wvDWK1/yS1q8aDomYWC4wHBgP5QJaZzXDO5Qa06Qb8CTjRObfVzNrWVsEikaBwxx5GT8wiPi6WCaMzaZag4YlS+4LZZegHLHPOrXDOlQKvAkOrtLkaGO+c2wrgnNsY2jJFIkdJWQVXv5DNpp17eG5UBsktNDxR6kYwgd4RyAt4nu9/LdBRwFFmNsvMvjGzM/c3IzO7xsyyzSy7sLDw0CoWCWOVlY7fTp3L9/nbeHz4cfROae51SVKPhKpTLw7oBpwKjACeMbPmVRs55552zmU45zLatGkTokWLhI8H31/CzPnruW1ID35xzBFelyP1TDCBXgAE3tgw2f9aoHxghnOuzDm3EvgBX8CL1BuvzF7DU58v5/IBnRhzUmevy5F6KJhAzwK6mVlnM2sIDAdmVGnzJr69c8ysNb4umBWhK1MkvH3xQyG3v7mAU7u34a5z0zU8UTxRY6A758qBm4D3gUXAVOfcQjO7x8zO8zd7H9hsZrnAp8AfnHOba6tokXCyZP0ObnjpO7q1bcITv+xLnIYnikfMOefJgjMyMlx2drYnyxYJlY3bS7jgya8or6zkzRtPpH1SI69LkihnZjnOuYz9TdPFuUQOUXFpOb96IZutxaVMvXagwlw8p78NRQ5BRaXjN6/OZUFBEf8ccRw9OyZ5XZKIAl3kUPxt5iI+zN3AneekM6hHO6/LEQEU6CIH7cWvV/HslysZfUIao0/U8EQJHwp0kYPw6eKN3DVjIaf3aMsd56R7XY7IjyjQRYKUu3Y7N738HT3aN+Px4ccRG6Ox5hJeFOgiQVhfVMJVk7Jo1qgBE0Zn0jheA8Qk/CjQRWqwa085Y57PYkdJGc+NyqRdswSvSxLZL+1miBxARaXj16/MYdG67Tw3OpP0Ds28LkmkWgp0kQO49+1cPl68kXvP78nPu+u+LRLe1OUiUo2Js1Yy6atV/Oqkzlw+oJPX5YjUSIEush8f5W7g3rdzOSO9HX8a0sPrckSCokAXqWJBQRE3vzKHnh2TeGx4Hw1PlIihQBcJsK5oN2Oez6Jl44Y8OyqDxIY6zCSRQ59WEb8dJWVcOTGL4j0VvHZ9f9o21fBEiSwKdBGgvKKSm16ew9KNO5l0ZSbdj2jqdUkiB01dLlLvOee4a8ZCPv+hkHHn9+TkbrqBuUQmBbrUe8/+dyUvfbuG607pwoh+qV6XI3LIFOhSr723YB33vbuIs3u154+/6O51OSKHRYEu9dbcvG3835S59ElpziPDehOj4YkS4RToUi/lbSnmV89n0aZpPM9ckUFCg1ivSxI5bAp0qXeKdpdx1aQsSssrmTg6k9ZN4r0uSSQkNGxR6pWyikpueCmHVZt38cJV/enaVsMTJXoo0KXecM5x+/QFzFq2mYcv6c3ALq28LkkkpNTlIvXGk58tZ0p2Hr8+rSsXH5/sdTkiIadAl3rhP9+v5aH3lzC0TwduGXyU1+WI1AoFukS9nNVb+N2078lMa8GDFx+LmYYnSnRSoEtUW715F1e/kEPH5o14+vIM4uM0PFGilwJdota24lKunJSFc44JozNp0bih1yWJ1CqNcpGotKe8gmtezCF/y25euro/nVs39rokkVqnQJeo45zjT6/PZ/bKLTw+vA+ZaS29LkmkTgTV5WJmZ5rZEjNbZmZjD9DuIjNzZpYRuhJFDs7jHy/ljTkF/G7wUQzt09HrckTqTI2BbmaxwHjgLCAdGGFm6ftp1xT4DfBtqIsUCdb0Ofk89tFSLj4+mZtO6+p1OSJ1Kpg99H7AMufcCudcKfAqMHQ/7e4FHgBKQlifSNC+XbGZP742j4FHtuK+C3ppeKLUO8EEekcgL+B5vv+1fcysL5DinHvnQDMys2vMLNvMsgsLCw+6WJHqLC/cyTUv5pDaMpGnRh5PwzgN4JL657A/9WYWAzwK/K6mts65p51zGc65jDZtdJsvCY3NO/dw1aQs4mKMiaP7kZTYwOuSRDwRTKAXACkBz5P9r+3VFOgJfGZmq4ABwAwdGJW6UFLmG564vqiEZ0ZlkNoq0euSRDwTTKBnAd3MrLOZNQSGAzP2TnTOFTnnWjvn0pxzacA3wHnOuexaqVjEr7LS8ftp35Ozeit/v7QPfVNbeF2SiKdqDHTnXDlwE/A+sAiY6pxbaGb3mNl5tV2gSHUe+XAJb89bx9izjmZIr/ZelyPiuaBOLHLOzQRmVnntzmrannr4ZYkc2NSsPMZ/upwR/VK59mdHel2OSFjQUACJOLOWbeLP0+dzcrfW3DP0GA1PFPFToEtEWbphB9dNzqFLmyaMv6wvDWL1ERbZS98GiRiFO/Zw5aQsEhrEMuHKTJolaHiiSCAFukSE3aUV/OqFbDbvLGXCqEw6Nm/kdUkiYUdXW5SwV1npuGXKXOblb+PfI4+nV3KS1yWJhCXtoUvYu/+9xby3cD23n53OGccc4XU5ImFLgS5hbfI3q3n6ixWMGtiJq05M87ockbCmQJew9dmSjdw1YyGnHd2WO85J1/BEkRoo0CUsLVq3nZtenkP3dk3554jjiNPwRJEa6VsiYWd+fhGXPfstTeLjmDA6k8bxOnYvEgwFuoSVr5ZtYvjTX9OoQSwvX92fI5ISvC5JJGJo10fCxrvz1/GbV+eS1jqRF65SmIscLAW6hIVXZq/htunz6ZPSnAmjM2me2NDrkkQijgJdPOWc48nPlvPQ+0s4tXsbnrysL4kN9bEUORT65ohnKisd495ZxIRZKzm/TwceuqS3LrYlchgU6OKJsopK/vjaPKbPKeDKE9O44+x0YmI0zlzkcCjQpc7tLq3ghpdy+HRJIb8/4yhu/HlXnTQkEgIKdKlT24pLGfN8Nt+t2cpfL+jJZf07eV2SSNRQoEudWV9UwqgJs1m5aRfjf9lX9wEVCTEFutSJlZt2MfLZb9lWXMrEKzM5sWtrr0sSiToKdKl1CwqKGDVhNg545ZoBHJvc3OuSRKKSAl1q1VfLN3HNCzkkNWrAC2P60aVNE69LEolaCnSpNe8tWM+vX5lDp1aJvDCmH+2TdNs4kdqkQJda8ersNfx5+nx6pzRnwqhMWjTWqfwitU2BLiHlnONfny/nwfeW8LOj2vDUSJ3KL1JX9E2TkKmsdNw3cxHPfrmS83p34OFLetMwTqfyi9QVBbqERFlFJbe+Po83vitg9Alp3HmOTuUXqWsKdDlsu0sruOnl7/h48UZ+O/gobj5Np/KLeEGBLoelqLiMMc9nkbNmK/ee35PLB+hUfhGvKNDlkG3Y7juVf3nhTv454jjOObaD1yWJ1GtBHbEyszPNbImZLTOzsfuZ/lszyzWzeWb2sZlpNy3Krdq0i4v+9RVrthQzcXQ/hblIGKgx0M0sFhgPnAWkAyPMLL1KszlAhnPuWOA14MFQFyrhY0FBERc/9RW79pTzytUDOKmbrssiEg6C2UPvByxzzq1wzpUCrwJDAxs45z51zhX7n34DJIe2TAkX36zYzIinv6FhbAzTrjuB3inNvS5JRPyCCfSOQF7A83z/a9UZA7y7vwlmdo2ZZZtZdmFhYfBVSlh4f+F6rpgwm3ZJCbx2/Ql0bavrsoiEk5Ce9WFmI4EM4KH9TXfOPe2cy3DOZbRp0yaUi5ZaNjUrj+sn55DevhnTrh1Ih+a6LotIuAlmlEsBkBLwPNn/2o+Y2enAbcApzrk9oSlPwsFTny/n/ncXc3K31jw18ngax2twlEg4CuabmQV0M7PO+IJ8OPDLwAZmdhzwb+BM59zGkFcpnqiodNz/7iKe+e9Kzu3dgUd0Kr9IWKsx0J1z5WZ2E/A+EAtMcM4tNLN7gGzn3Ax8XSxNgGn+MwTXOOfOq8W6pZYtWredsa/P4/v8Iq4Y2Im/nHuMTuUXCXNB/e3snJsJzKzy2p0Bj08PcV3ikT3lFTzxyTL+9dlykho14B8jjuPcY9vrVH6RCKDOUNkne9UWbn19HssLd3HhcR2545x0XcdcJIIo0IWde8p58L3FvPjNajokNWLSlZmc2r2t12WJyEFSoNdzny7eyG3T57NuewmjT0jj92d01ygWkQilb249tXnnHu55O5e35q6lW9smvHbdCRzfqYXXZYnIYVCg1zPOOd6au5a7/7OQnXvK+c2gbtzw8y7Ex8V6XZqIHCYFej1SsG03t02fz2dLCumT0pwHLz6Wo9o19bosEQkRBXo9UFnpePGb1Tz43mIqHdx5TjqjTkgjVuPKRaKKAj3KLdu4g1tfn0/O6q2c3K01913Qi5SWiV6XJSK1QIEepUrLK3nq8+U88ckyEuNjeeSS3lzYt6NOEBKJYgr0KDQ3bxtjX5/H4vU7OOfY9tx17jG0aRrvdVkiUssU6FGkuLScRz74gYmzVtK2aQLPXJHB4PR2XpclInVEgR4lvly6iT9Nn0felt1c1j+VW886mmYJDbwuS0TqkAI9whUVlzHunVym5eTTuXVjXr1mAAOObOV1WSLiAQV6hHLO8e6C9dz51kK2Fpdy/ald+M2gbiQ00AlCIvWVAj0Cbdhewh1vLuCD3A307NiMSVdm0rNjktdliYjHFOgRxDnHq1l53DdzEaXllYw962h+dVJn4mJ1FyERUaBHjFWbdjH2jXl8s2ILA45syf0XHkta68ZelyUiYUSBHuaWF+5kSlYez3+1ioZxMfztwl4Mz0zRCUIi8hMK9DC0u7SCmfPXMSUrj9mrthAXYwzp1Z7bzu5Bu2YJXpcnImFKgR5GFhQU8WrWGt6as5Yde8o5snVj/nTW0VzYN1lneopIjRToHivaXcaM79cyJWsNCwq2Ex8Xw9m92nNpZgr9OrdU14qIBE2B7gHnHFmrtvJq1hpmzl9HSVkl6e2bce/QYzivT0eSGukMTxE5eAr0OlS4Yw9vfJfPlKw8VmzaRdP4OC7qm8yIfqkaRy4ih02BXssqKh3/XVrIlKw8PszdQHmlIzOtBTf8vCtDeh1BYkO9BSISGkqTWpK/tZhp2flMy85jbVEJrRo35KqTOjMsI4WubZt4XZ6IRCEFegiVllfy0aINvJqVx3+XFgJwcrc23H5OOqf3aEfDOJ3RKSK1R4EeAss27mRqdh6v5+SzeVcpHZIS+PVp3bgkI5nkFrrdm4jUDQX6IdpdWsE789cxJWsNWau2EhdjnN6jHcP7pXBytza6AbOI1DkF+kGan+87+WfGXJ38IyLhRYG+HyVlFeRvLWbNlmLytuxmzRbf4+WFO1lRuMt38s+x7RmemUpmWgud/CMiYaFeBnplpWPjjj37gnrNlmLyAx5v3LHnR+0TGsSQ2jKRzq0aM/qENIbq5B8RCUNBBbqZnQk8DsQCzzrn7q8yPR54ATge2Axc6pxbFdpSD86OkrJ9e9h5/qDO8+9152/dTWl55b62ZtC+WQIpLRM55ag2pLRMJLVlIiktE0lp2Yg2TeK1Fy4iYa/GQDezWGA8MBjIB7LMbIZzLjeg2Rhgq3Ouq5kNBx4ALq2Ngvcqq6hk3baSfXvVefu6SHw/W4vLftS+aUIcnVol0r1dUwb3aOcPa19wd2ieQHycbt0mIpEtmD30fsAy59wKADN7FRgKBAb6UOAv/sevAU+YmTnnXAhrBWBK1hr++cky1hWVUFH5v9nHxRjJLRqR0jKRXr3a7wvr1JaJpLRIJClRXSQiEt2CCfSOQF7A83ygf3VtnHPlZlYEtAI2BTYys2uAawBSU1MPqeDWTeI5vlOLfUGd0jKR1FaJHNEsQUMFRaReq9ODos65p4GnATIyMg5p731Qj3YM6tEupHWJiESDYM5FLwBSAp4n+1/bbxsziwOS8B0cFRGROhJMoGcB3cyss5k1BIYDM6q0mQGM8j++GPikNvrPRUSkejV2ufj7xG8C3sc3bHGCc26hmd0DZDvnZgDPAS+a2TJgC77QFxGROhRUH7pzbiYws8prdwY8LgEuCW1pIiJyMHQ9VxGRKKFAFxGJEgp0EZEooUAXEYkS5tXoQjMrBFYf4q+3pspZqPWA1rl+0DrXD4ezzp2cc232N8GzQD8cZpbtnMvwuo66pHWuH7TO9UNtrbO6XEREooQCXUQkSkRqoD/tdQEe0DrXD1rn+qFW1jki+9BFROSnInUPXUREqlCgi4hEibAOdDM708yWmNkyMxu7n+nxZjbFP/1bM0vzoMyQCmKdf2tmuWY2z8w+NrNOXtQZSjWtc0C7i8zMmVnED3ELZp3NbJj/vV5oZi/XdY2hFsRnO9XMPjWzOf7P9xAv6gwVM5tgZhvNbEE1083M/uHfHvPMrO9hL9Q5F5Y/+C7Vuxw4EmgIfA+kV2lzA/CU//FwYIrXddfBOv8cSPQ/vr4+rLO/XVPgC+AbIMPruuvgfe4GzAFa+J+39bruOljnp4Hr/Y/TgVVe132Y6/wzoC+woJrpQ4B3AQMGAN8e7jLDeQ99382pnXOlwN6bUwcaCjzvf/waMMjMIvnGojWus3PuU+dcsf/pN/juIBXJgnmfAe4FHgBK6rK4WhLMOl8NjHfObQVwzm2s4xpDLZh1dkAz/+MkYG0d1hdyzrkv8N0fojpDgReczzdAczNrfzjLDOdA39/NqTtW18Y5Vw7svTl1pApmnQONwfc/fCSrcZ39f4qmOOfeqcvCalEw7/NRwFFmNsvMvjGzM+usutoRzDr/BRhpZvn47r9wc92U5pmD/b7XqE5vEi2hY2YjgQzgFK9rqU1mFgM8Coz2uJS6Foev2+VUfH+FfWFmvZxz27wsqpaNACY55x4xs4H47oLW0zlX6XVhkSKc99Dr482pg1lnzOx04DbgPOfcnjqqrbbUtM5NgZ7AZ2a2Cl9f44wIPzAazPucD8xwzpU551YCP+AL+EgVzDqPAaYCOOe+BhLwXcQqWgX1fT8Y4Rzo9fHm1DWus5kdB/wbX5hHer8q1LDOzrki51xr51yacy4N33GD85xz2d6UGxLBfLbfxLd3jpm1xtcFs6IOawy1YNZ5DTAIwMx64Av0wjqtsm7NAK7wj3YZABQ559Yd1hy9PhJcw1HiIfj2TJYDt/lfuwffFxp8b/g0YBkwGzjS65rrYJ0/AjYAc/0/M7yuubbXuUrbz4jwUS5Bvs+Gr6spF5gPDPe65jpY53RgFr4RMHOBM7yu+TDX9xVgHVCG7y+uMcB1wHUB7/F4//aYH4rPtU79FxGJEuHc5SIiIgdBgS4iEiUU6CIiUUKBLiISJRToIiJRQoEu9ZKZrfKP7z6sNiLhRIEuIhIlFOgS9czsTTPL8V9X/Joq09LMbLGZvWRmi8zsNTNLDGhys5l9Z2bzzexo/+/0M7Ov/dft/srMutfpColUQ4Eu9cFVzrnj8V3M7NdmVvWKnN2BJ51zPYDt+K6zv9cm51xf4F/A7/2vLQZOds4dB9wJ3Fer1YsESYEu9cGvzex7fNeBSeGnF7nKc87N8j+eDJwUMO0N/785QJr/cRIwzX8nmr8Dx9RG0SIHS4EuUc3MTgVOBwY653rjuwtQQpVmVa9/Efh879UsK/jf5abvBT51zvUEzt3P/EQ8oUCXaJcEbHXOFfv7wAfsp02q//rbAL8Evgxinnsvczo6JFWKhIACXaLde0CcmS0C7sfX7VLVEuBGf5sW+PrLD+RB4G9mNgfdJEbCiK62KPWamaUBb/u7T0QimvbQRUSihPbQRUSihPbQRUSihAJdRCRKKNBFRKKEAl1EJEoo0EVEosT/A6bmJLvWx6VEAAAAAElFTkSuQmCC\n", "text/plain": ["<Figure size 432x288 with 1 Axes>"]}, "metadata": {"needs_background": "light"}, "output_type": "display_data"}], "source": ["from tqdm import tqdm\n", "import pandas\n", "\n", "N = 2000\n", "obs = []\n", "for alpha in tqdm([0., 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.]):\n", "    total_nb1 = 0\n", "    for i in range(0, N):\n", "        mat = random_symmetric_adjacency_matrix(10, alpha=alpha)\n", "        nb1 = (mat.ravel() == 1).sum()\n", "        total_nb1 += nb1\n", "    obs.append(dict(alpha=alpha, emptyness=total_nb1 / (mat.size - mat.shape[0]) / N))\n", "\n", "df = pandas.DataFrame(obs)\n", "df.plot(x=\"alpha\", y=\"emptyness\", title='proportion de coefficient nuls');"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q2 : calculer les valeurs propres et les trier par ordre croissant"]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"data": {"text/plain": ["array([-1.0000000e+01,  4.4408921e-16, -1.0000000e+01, -1.0000000e+01,\n", "       -1.0000000e+01, -1.0000000e+01, -1.0000000e+01, -1.0000000e+01,\n", "       -1.0000000e+01, -1.0000000e+01])"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["w, v = numpy.linalg.eig(mat)\n", "w"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"text/plain": ["1"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["sum(numpy.abs(w) < 1e-7)"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 11/11 [00:01<00:00,  8.27it/s]\n"]}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAEWCAYAAAB/tMx4AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy89olMNAAAACXBIWXMAAAsTAAALEwEAmpwYAAAlJUlEQVR4nO3deXxV5Z3H8c8vGwGEsAURQkhQZJVFIsG2OlqXqrXSVqcoaNup1S7T2jp1WtvOdOzmWKet3Wbcutgqohatte7aqrQqaABlVxQCBBBCgLAGsvzmj3PQa0wgJDf35Nz7fb9evLi559xzfufem2+e+zz3nMfcHRERiZ+sqAsQEZH2UYCLiMSUAlxEJKYU4CIiMaUAFxGJKQW4iEhMKcDTnJmdZmZVKdzfp83sH6naX7jPEjNzM8tJ5X7lvczsDjP7QXg7pe+9TKQAFxGJKQW4vIuZZUddQ1dhgU75HUn2pwV9+shMCvCImFmlmV1jZovNrNbM7jWz/ITlV5jZG2a2zcweMrPBCcvczL5oZqvMbJeZfd/MjjWzF8xsp5ndZ2Z5zfb3LTPbGu53ZsL9d5jZzWb2qJntAU43s8Fmdr+ZVZvZGjO76hDH0T+sb6eZvQQc22z5KDN7KjyO18zsE61sZ7qZVTS772ozeyi8/WEzWxTuZ72ZXXeImgrM7DdmtsnMNpjZDw7+YTKz68zsroR139X9YmbPmtkPzex5YC8wPOwWWh0+12sSn79m+73OzOaEr+UuM1toZhMSllea2TfMbDGwx8xyzOwCM1tmZjvCfY9utv43zWy5mW03s98dfI8c7J4It/cW8DszyzKza83sTTOrCd8H/cL1883srvD+HWb2spkd3cpxtPretBa6yMLn77jWXo+E9Vp9X5nZFDOrCF/fzWb208NtTwB3178I/gGVwEvAYKAfsAL4fLjsg8BW4ESgG/BLYG7CYx34M9AbGAvsB/4KDAcKgOXAp8J1TwMagJ+G2/onYA8wMlx+B1ALvJ/gD3oPYAHwHSAv3OZq4EOtHMc9wH1AT2AcsAH4R7isJ7Ae+BcgB5gUHteYFrbTA9gFjEi472Xg4oTjOCGscTywGfhouKwkfE5ywp//BNwa7n9g+Dx/Llx2HXBXwj6aP/ZZYF34vOaEz+fOhOfrGGBsK8/FdUA9cBGQC1wDrAFyE17zV4ChQHfg+PC1OCtc/+vAG0BewvpLw/X7Ac8DP2j2uv4ofF27A18B5gFF4X23ArPD9T8H/CV8nrOByUDvdrw3P33w9W32fjwu4f2UWGNVeDuLQ7yvgBeBy8LbRwFTo/4djcM/tcCj9Qt33+ju2wh+uSaG988EfuvuC919P/BN4GQzK0l47I3uvtPdlxH8kj/p7qvdvRZ4jCAsE/2nu+939+eAR4DElvCf3f15d28iCMlCd/+eux9w99XA7cDFzYsPW7UXAt9x9z3uvhT4fcIq5wOV7v47d29w90XA/cA/N9+Wu+8l+KN0SbjtEcAo4KFw+bPuvsTdm9x9MTCb4I9R85qOBs4DvhrWtAW4qaX6D+EOd1/m7g0EIdkEjDOz7u6+KXzOW7PA3ee4ez3BH818YGrC8l+4+3p33wdMBx5x96fC9X9MEMTvS1j/V+H624AfHnx+Qk3Af4Wv6z7g88C33b0qfN9cB1wUfrqoB/oTBG2juy9w952HOI7W3pvtdRKHfl/VA8eZ2QB33+3u8zq4v4ygAI/WWwm39xK0PCBo+aw9uMDddwM1wJCE9Tcn3N7Xws9HJfy83d33JPy8NtzHQesTbg8DBocfs3eY2Q7gW0BLH7cLCVqpiY9fm3B7GFDebFszgUEtbAvgbt4JqBnAg2GwY2blZvZM+PG7liCsBrSwjWEErdlNCfu8laAl3lZvH0/4vE0P97fJzB4xs1FtfGwTUEXrz3Xz17kpXD6klfWbv27V7l6X8PMw4E8Jx70CaCR47e4EngDuMbONZnajmeUe4jhae2+21+HeV5cTfCJZGXbvnN/B/WUEDXx0TRsJ3vAAmFlPgtbThnZur6+Z9UwI8WKCVvtBiZekXA+scfcRbdhuNUELdSiwMmHbidt6zt3PamOdTwGFZjaRIMivTlh2N/Ar4Fx3rzOzn9FygK8n6FIaELagm9tD0I1wUEt/TN51iU53fwJ4wsy6Az8gaDme0soxDD14w4IB0CKC17OlbW8k+MRzcH0LH5/4Og9NuF18iG1BcOyfcffnW6ntu8B3w09yjwKvAb9pZd3WvOv5M7PW/hg3d8j3lbuvAi4Jn7OPA3PMrH+zhoc0oxZ41zQb+Bczm2hm3YDrgfnuXtmBbX7XzPLM7BSCro0/trLeS8CucHCsu5llm9k4Mzup+Yru3gg8AFxnZj3MbAzwqYRVHgaON7PLzCw3/HdS4kBds+3Vh3X9D0Hf61MJi3sB28LwnkLQQm9pG5uAJ4GfmFnvcGDvWDM72N3yCnCqmRWbWQFB91SrzOxoM5sW/hHdD+wm6LpozWQz+3jYbfHV8DGtdQfcB3zYzM4IW8NfC9d/IWGdfzWzonAw8tvAvYfY9y3AD81sWFh7oZlNC2+fbmYnhN1eOwm6LA51HK15FRgbvjfzCbpp2uKQ7yszu9TMCsNPITvCx7SnvoyiAO+C3P1p4D8J+os3EXyz40j6cJt7C9hO0HqbRTAgtbKlFcNQPp+gz3MNwaDjrwkG81ryJYKP128RDGD9LmFbu4Czw9o3huscHHRrzd3AmcAfm7Wgvwh8z8x2EQyE3XeIbXySYKBsOcFxzyEYfMTdnyIIwcUEg2oPH2I7EPyO/FtY/zaCfvcvHGL9PxN0uWwHLgM+Hv5heg93fw24lGCQeivwEeAj7n4gYbW7Cf4grQbeJPgE0JqfE4wZPBk+T/OA8nDZIILnYSdB18pzBN0qR8TdXwe+BzwNrALadNJWG95X5wDLzGx3eBwXh/36cgjmrgkdRJLBgq82HufulyZpe5XAZ8M/6CLvoRa4iEhMKcBFRGJKXSgiIjGlFriISEyl9HvgAwYM8JKSklTuUkQk9hYsWLDV3Qub35/SAC8pKaGiouLwK4qIyNvMbG1L96sLRUQkphTgIiIxpQAXEYkpXcxKRGKnvr6eqqoq6urqDr9yjOTn51NUVERu7qEuFPkOBbiIxE5VVRW9evWipKSE4CKO8efu1NTUUFVVRWlpaZsec9guFDP7rZltMbOlCff1s2CarFXh/307ULeIyBGpq6ujf//+aRPeAGZG//79j+hTRVv6wO8guFJYomuBv4bX9v1r+LOISMqkU3gfdKTHdNgAd/e5BJfRTDSNd6bO+j3w0SPa6xH6y6sbeXDRBnTav4jIO9r7LZSjwwvnQ3CN5xZntwYwsyvD2aYrqqur27WzBxZW8dV7X+GKPyxgy870GrQQkczw7LPPcv75wUxxd9xxB1/60pc6vM0Of43Qg2Zxq01jd7/N3cvcvayw8D1ngrbJrz91Ev/x4dH8fVU1Z/70OR5YWKXWuIhkvPYG+GYzOwYg/H9L8kp6r+ws47OnDOexr5zC8Uf34t/ue5XLf1/BW7VqjYtINCorKxk9ejRXXHEFY8eO5eyzz2bfvn2cdtppb18yZOvWrXTm9Z/a+zXChwjmPrwh/P/PSavoEIYXHsW9nzuZ379QyY1PrOSsm57jO+eP4aLJRWk5oCEih/fdvyxj+cadSd3mmMG9+a+PjD3seqtWrWL27NncfvvtfOITn+D+++9Pah2H05avEc4GXgRGmlmVmV1OENxnmdkqgvkLb+jcMt+RnWV85gOlPP6VUxk9qDf/Pmcx/3LHy2yq1fR5IpJapaWlTJw4EYDJkydTWVmZ0v0ftgXu7pe0suiMJNdyREoG9OSeK6dy57y13PDYSs7+6Vz+4/zRfKJsqFrjIhmkLS3lztKt2zvzc2dnZ7Nv3z5ycnJoamoC6PQzRWN9LZSsLONT7yvhia+eytghvfnG/Uv45G9fYsMOtcZFJBolJSUsWLAAgDlz5nTqvmId4AcV9+/B3Z+dyvenjWXB2u186Ka5zH5pnb6pIiIpd80113DzzTczadIktm7d2qn7SumcmGVlZd7ZEzqs37aXb9y/mBferOEDxw3ghgtPoKhvj07dp4ik1ooVKxg9enTUZXSKlo7NzBa4e1nzddOiBZ5oaL8ezPpsOT/82DgWrQta43fNW0tTk1rjIpJe0i7AIbiewMzyYTxx9alMKu7Lfzy4lEt/M5/12/ZGXZqISNKkZYAfVNS3B3dePoUbPn4Ci6tq+dDP5vKHFyvVGhdJA+k4xnWkx5TWAQ5Ba/ziKcU8cfWplJX04zt/XsYlt89jbc2eqEsTkXbKz8+npqYmrUL84PXA8/Pz2/yYtBvEPBR3548VVXz/4eU0NDnfOGcknzy5hKwsfW9cJE4ybUae1gYxMyrAD9pUu49vPbCEZ16rZkpJP268aDwlA3pGXZaISIsy5lsobXFMQXd+++mT+PE/T2DFWzs55+dz+c0/1tCovnERiZGMDHAI+sYvmlzEU1f/E+8/dgDff3g50299kdXVu6MuTUSkTTI2wA8aVJDPrz9Vxk3TJ7Bqy27O/fnfuX3uarXGRaTLy/gAh6A1/rFJRTx19amcMqKQHz66gotueYE3tqg1LiJdlwI8wcDe+dz+ycn8/OKJrNm6h/N+8Xdufe7NtPqqkoikDwV4M2bGtIlDePLqUzl9ZCH//dhK5iyoirosEZH3UIC3YmCvfG65dDITigr4yZOvU1ffGHVJIiLvogA/BDPjm+eN5q2ddfz2+TVRlyMi8i4K8MOYOrw/Z44eyM3PvEnN7v1RlyMi8jYFeBtce+4o9hxo4Jd/eyPqUkRE3qYAb4PjBvZi+knF3DVvLZVbdREsEekaFOBtdPVZI8jLyeJ/nngt6lJERAAFeJsN7JXPFacM55Elm1i0bnvU5YiIKMCPxJWnDmfAUd24/tEVOrlHRCKnAD8CPbvlcPVZI3i5cjtPLd8cdTkikuEU4EdoetlQhhf25IbHV9LQ2BR1OSKSwRTgRygnO4trzxnF6uo93PPy+qjLEZEMpgBvh7PGHM2Ukn787OnX2b2/IepyRCRDKcDbITjFfhRbdx/gtrmroy5HRDKUArydJhX35cPjj+H2uavZsjO9JlYVkXhQgHfA1z80koamJm56elXUpYhIBlKAd8Cw/j2ZWT6Me19ex6rNu6IuR0QyjAK8g646YwQ983L40eMroy5FRDKMAryD+vXM4wunH8vTK7Ywb3VN1OWISAZRgCfBZ95fyjEF+Vz/6AqaNJu9iKSIAjwJ8nOz+drZI1lcVcsjSzZFXY6IZIgOBbiZXW1my8xsqZnNNrP8ZBUWNx+bNIRRg3px4xMr2d+g+TNFpPO1O8DNbAhwFVDm7uOAbODiZBUWN9lZxrfOG836bfu4a966qMsRkQzQ0S6UHKC7meUAPYCNHS8pvk49vpBTRgzgl39bRe2++qjLEZE01+4Ad/cNwI+BdcAmoNbdn2y+npldaWYVZlZRXV3d/kpj4tpzR1G7r57/e1bzZ4pI5+pIF0pfYBpQCgwGeprZpc3Xc/fb3L3M3csKCwvbX2lMjB1cwMcmDeF3z1eyYce+qMsRkTTWkS6UM4E17l7t7vXAA8D7klNWvH3t7JEA/ETzZ4pIJ+pIgK8DpppZDzMz4AxgRXLKirchfbrzmfeX8qdXNrB0Q23U5YhImupIH/h8YA6wEFgSbuu2JNUVe1847VgKuufqFHsR6TQd+haKu/+Xu49y93Hufpm7709WYXFX0D2XL39wBH9ftZXnXk//wVsRST2didmJLps6jOJ+PfjvR1fQqFPsRSTJFOCdKC8ni3//0EhWvrWLBxZWRV2OiKQZBXgnO3/8MUwoKuAnT75OXb1OsReR5FGAd7Jg/szRvLWzjt8+vybqckQkjSjAU2Dq8P6cOXogNz/zJjW7Nc4rIsmhAE+Ra88dxZ4DDfzybzrFXkSSQwGeIscN7MX0k4q5a95aKrfuibocEUkDCvAUuvqsEeTlZPE/OsVeRJJAAZ5CA3vlc8Upw3lkySYWrdsedTkiEnMK8BS78tThDDiqG9c/ugJ3ndwjIu2nAE+xnt1yuPqsEbxcuZ2nlm+OuhwRiTEFeASmlw1leGFPbnh8JQ2NTVGXIyIxpQCPQE52FteeM4rV1Xu45+X1UZcjIjGlAI/IWWOOZkpJP3729Ovs3t8QdTkiEkMK8IgEp9iPYuvuA9w2d3XU5YhIDCnAIzSpuC8fHn8Mt89dzZaddVGXIyIxowCP2Nc/NJKGpiZuenpV1KWISMwowCM2rH9PZpYP496X17Fq866oyxGRGFGAdwFXnTGCnnk5mj9TRI6IArwL6Nczjy+cfixPr9jCvNU1UZcjIjGhAO8iPvP+Uo4pyOf6R1fQpPkzRaQNFOBdRH5uNl87eySLq2p5ZMmmqMsRkRhQgHchH5s0hFGDenHjEyvZ36D5M0Xk0BTgXUh2lvGt80azfts+7pq3LupyRKSLU4B3MaceX8gpIwbwy7+tonZffdTliEgXpgDvgq49dxS1++q55bk3oy5FRLowBXgXNHZwAeeOG8Tsl9ZRV6++cBFpmQK8i5pZPowde+t5bKm+kSIiLVOAd1EnD+9PSf8ezNJgpoi0QgHeRWVlGTPKi6lYu53XdY0UEWmBArwLu2jyUPKys7h7vlrhIvJeCvAurF/PPM49YRD3L6xi3wENZorIuynAu7gZU4rZVdfAXxZvjLoUEeliFOBd3JTSfhw38ChmqRtFRJpRgHdxZsaMKcW8un4HyzbWRl2OiHQhHQpwM+tjZnPMbKWZrTCzk5NVmLzjwhOL6JajwUwRebeOtsB/Djzu7qOACcCKjpckzRX0yOX88YN5cNEGdu9viLocEeki2h3gZlYAnAr8BsDdD7j7jiTVJc3MKC9mz4FGHnpFg5kiEuhIC7wUqAZ+Z2aLzOzXZtaz+UpmdqWZVZhZRXV1dQd2l9lOLO7DqEG9mDV/Le6asUdEOhbgOcCJwM3uPgnYA1zbfCV3v83dy9y9rLCwsAO7y2xmxszyYpZt3MniKg1mikjHArwKqHL3+eHPcwgCXTrJtElD6J6brcFMEQE6EODu/haw3sxGhnedASxPSlXSot75uVwwYTAPvbqRnXWa7EEk03X0WyhfBmaZ2WJgInB9hyuSQ5o5tZh99Y08uGhD1KWISMQ6FODu/krYvz3e3T/q7tuTVZi0bHxRH8YN6c3d89dpMFMkw+lMzBiaWT6MlW/tYuE6/b0UyWQK8Bi6YMJgjuqWo+ujiGQ4BXgM9eyWw7SJg3l48SZ27D0QdTkiEhEFeEzNLB/GgYYm7l+owUyRTKUAj6kxg3szcWgf7taZmSIZSwEeYzPLi3mzeg/z12yLuhQRiYACPMbOHz+YXvk5OjNTJEMpwGOse142F55YxGNLN1Gze3/U5YhIiinAY25GeTH1jc6cBVVRlyIiKaYAj7njj+7FSSV9mf3SOpqaNJgpkkkU4GlgZvkwKmv28sKbNVGXIiIppABPA+eMG0TfHrnc/dLaqEsRkRRSgKeB/NxgMPPJZZvZsqsu6nJEJEUU4GnikvJiGpqcP1ZoMFMkUyjA08SxhUdx8vD+zH5pHY0azBTJCArwNDJzajFV2/cxd5UmjxbJBArwNHL2mEEMOCpPZ2aKZAgFeBrJy8nioslD+euKzWyq3Rd1OSLSyRTgaWbGlGKaHO59eX3UpYhIJ1OAp5ni/j04ZcQA7n15PQ2NTVGXIyKdSAGehmaWF7Opto5nXtNgpkg6U4CnoTNGH83AXt24e77OzBRJZwrwNJSbncX0k4by7OvVVG3fG3U5ItJJFOBp6uIpxRhwz0sazBRJVwrwNDWkT3dOGzmQeyvWU6/BTJG0pABPYzOmFFO9az9PL98cdSki0gkU4Gns9FEDGVyQz90v6cxMkXSkAE9j2VnG9JOK+fuqrayt2RN1OSKSZArwNDf9pKFkZ5la4SJpSAGe5gYV5HPGqIHMqahif0Nj1OWISBIpwDPAjPJiavYc4IllGswUSScK8Axw6ohCivp215mZImlGAZ4BsrKMS6YUM2/1Nt7YsjvqckQkSRTgGeITZUPJyTJmazBTJG0owDNEYa9ufGjsIO5fWEVdvQYzRdJBhwPczLLNbJGZPZyMgqTzzCgvZsfeeh5dsinqUkQkCZLRAv8KsCIJ25FOdvLw/pQO6Kk5M0XSRIcC3MyKgA8Dv05OOdKZgsHMoVSs3c5rb+2KuhwR6aCOtsB/BnwdaPVyd2Z2pZlVmFlFdbVmiInaRZOHkpedpa8UiqSBdge4mZ0PbHH3BYdaz91vc/cydy8rLCxs7+4kSfr1zOPcEwbxwKIN7D3QEHU5ItIBHWmBvx+4wMwqgXuAD5rZXUmpSjrVjCnF7Kpr4OFXNZgpEmftDnB3/6a7F7l7CXAx8Dd3vzRplUmnmVLaj+MGHsUsfSdcJNb0PfAMZGbMmFLMq+t3sHRDbdTliEg7JSXA3f1Zdz8/GduS1LjwxCK65WTpMrMiMaYWeIYq6JHL+eMH8+dFG9i9X4OZInGkAM9gM8qL2XOgkYde2Rh1KSLSDgrwDHZicR9GDerFrPlrcfeoyxGRI6QAz2BmxszyYpZt3MniKg1misSNAjzDTZs0hO652czSmZkisaMAz3C983OZNnEwf3l1Ezvr6qMuR0SOgAJcmFFezL76Rh5ctCHqUkTkCCjAhfFFfThhSAGz5q3TYKZIjCjABQha4a9t3sXCddujLkVE2kgBLgBcMGEwR3XLYdY8nZkpEhcKcAGgZ7ccPjppMA8v2cSOvQeiLkdE2kABLm+bMWUYBxqauH+hBjNF4kABLm8bM7g3k4r7MGv+WpqaNJgp0tUpwOVdPv2+ElZX7+Hm596MuhQROQwFuLzLBRMG85EJg/nxk6/x3Ouaw1SkK1OAy7uYGT+68ASOH9iLq2YvYv22vVGXJCKtUIDLe/TIy+HWyybT5M7n7lzAvgONUZckIi1QgEuLSgb05OcXT2T5pp18+09LdIamSBekAJdWfXDU0Xz1zBE8sGgDf3hRVysU6WoU4HJIV31wBGeMGsj3H17Oy5Xboi5HRBIowOWQsrKMn06fSFHf7nxx1kI276yLuiQRCSnA5bAKuudy62Vl7K5r4IuzFnKgoSnqkkQEBbi00chBvbjxovEsWLudHzyyPOpyRATIiboAiY+PTBjM4qod3P73NYwv6sNFk4uiLkkko6kFLkfkG+eMYurwfnz7T0tYukETIYtESQEuRyQnO4tfzTiRfj3z+NydC9i+R5eeFYmKAlyO2ICjunHzpZOp3rWfq+5ZRKOuXCgSCQW4tMvEoX343rSx/H3VVn7y5GtRlyOSkRTg0m4XTynmkilD+b9n3+TxpZuiLkck4yjApUOuu2AsE4b24Wv3vcobW3ZHXY5IRlGAS4d0y8nm5pknkp+bzefurGBXXX3UJYlkDAW4dNjgPt355YxJVNbs5Zo/vqorF4qkiAJckuJ9xw7gm+eO4ollmzUdm0iKKMAlaS7/QCnnjz+GHz/xGnM1HZtIp1OAS9KYGTdeNJ4RA3tx1T2ajk2ks7U7wM1sqJk9Y2bLzWyZmX0lmYVJPPXIy+GWyybT2OR8/q4F1NVrOjaRztKRFngD8DV3HwNMBf7VzMYkpyyJs9IBPfnZ9Iks27iTb2k6NpFO0+4Ad/dN7r4wvL0LWAEMSVZhEm9njD6ar5wxggcWbuCueZqOTaQzJKUP3MxKgEnA/BaWXWlmFWZWUV2tga1M8pUzRnD6yEK++5flLFir6dhEkq3DAW5mRwH3A191953Nl7v7be5e5u5lhYWFHd2dxEhWlvGz6ZMY0rc7X7hrIVs0HZtIUnUowM0slyC8Z7n7A8kpSdJJQY9cbrl0Mrs0HZtI0nXkWygG/AZY4e4/TV5Jkm5GH9ObGy48gYq127n+0RVRlyOSNjrSAn8/cBnwQTN7Jfx3XpLqkjQzbeIQLv9AKXe8UMkDC6uiLkckLbR7Tkx3/wdgSaxF0ty1545i6YZavvnAEo4/uhfjhhREXZJIrOlMTEmZ3HA6tr498vj8XQvYsVfTsYl0hAJcUqqwVzduvvREtuzcz1X3vKLp2EQ6QAEuKTepuC/fnTaWua9Xc9NTr0ddjkhsKcAlEpdMKebik4byq2fe4Illb0VdjkgsKcAlMtddMJYJRQWajk2knRTgEpn83GxuvnQy3XKy+NydFeze3xB1SSKxogCXSB2cjm3N1j1cc5+mYxM5EgpwiVwwHdtoHl/2Fv98y4vc9NTrvPhmja4lLnIY7T6RRySZPntKKQcam3hs6SZ+8bdV/Pyvq8jLzmJicR+mlvajfHh/TizuS/e87KhLFekyLJUfWcvKyryioiJl+5N4qt1XT0XlNuav2ca81TUs3VBLk0NutjGhqA/lw/sxdXh/Jg/rS488tUEk/ZnZAncve8/9CnDp6nbV1VNRuZ15a2qYv3obSzbU0tjk5GQZ44sKKB/en/LSfpSV9OOobgp0ST8KcEkbu/c3sGDtduavrmHe6hoWV9XS0ORkZxnjhhQwdXg/ppb2p6ykL73yc6MuV6TDFOCStvYeOBjoQZfLq1U7qG90sgzGDSmgvLQf5aX9Oam0HwXdFegSPwpwyRj7DjSyaN125q2uYd6abbyybgcHGpswgzHH9GZq2OUypbQffXrkRV2uyGEpwCVj1dU3smjdDuavCbpcFq7bwYGGINBHDepNeWk/xg0poFtOFjlZRnaWkZudRXaWkZNt5GRlhf+/czs7y8jNyiI728gNH5OTHTz+4GOys3S1ZUmO1gJcIz6S9vJzszn52P6cfGx/APY3NPLq+lrmra5h/poa7nl5HXUvJH+qNzPe+YMQhn1OVmLIB8uyTEGfCX7zqZMo7t8jqdtUgEvG6ZaTzZSwCwVGcKChiQ079tHY1ER9o9PY5NQ3NoX/Bz83NDXR0Og0hLffWdaUsI7T0NgU/h8uawqXNYbbaLZOQ5PmCM0UeTnJP29SAS4ZLy8ni9IBPaMuQ+SI6VR6EZGYUoCLiMSUAlxEJKYU4CIiMaUAFxGJKQW4iEhMKcBFRGJKAS4iElMpvRaKmVUDa9v58AHA1iSWEwc65sygY05/HT3eYe5e2PzOlAZ4R5hZRUsXc0lnOubMoGNOf511vOpCERGJKQW4iEhMxSnAb4u6gAjomDODjjn9dcrxxqYPXERE3i1OLXAREUmgABcRiakuF+Bmdo6ZvWZmb5jZtS0s72Zm94bL55tZSQRlJlUbjvnfzGy5mS02s7+a2bAo6kymwx1zwnoXmpmbWay/ctaW4zWzT4Sv8zIzuzvVNSZbG97XxWb2jJktCt/b50VRZzKZ2W/NbIuZLW1luZnZL8LnZLGZndihHbp7l/kHZANvAsOBPOBVYEyzdb4I3BLevhi4N+q6U3DMpwM9wttfyIRjDtfrBcwF5gFlUdfdya/xCGAR0Df8eWDUdafgmG8DvhDeHgNURl13Eo77VOBEYGkry88DHgMMmArM78j+uloLfArwhruvdvcDwD3AtGbrTAN+H96eA5xhFutZYQ97zO7+jLvvDX+cBxSluMZka8vrDPB94EdAXSqL6wRtOd4rgP919+0A7r4lxTUmW1uO2YHe4e0CYGMK6+sU7j4X2HaIVaYBf/DAPKCPmR3T3v11tQAfAqxP+LkqvK/Fddy9AagF+qekus7RlmNOdDnBX/A4O+wxhx8th7r7I6ksrJO05TU+HjjezJ43s3lmdk7KquscbTnm64BLzawKeBT4cmpKi9SR/r4fkiY1jhEzuxQoA/4p6lo6k5llAT8FPh1xKamUQ9CNchrBJ6y5ZnaCu++IsqhOdglwh7v/xMxOBu40s3Hu3hR1YXHR1VrgG4ChCT8Xhfe1uI6Z5RB89KpJSXWdoy3HjJmdCXwbuMDd96eots5yuGPuBYwDnjWzSoK+wodiPJDZlte4CnjI3evdfQ3wOkGgx1Vbjvly4D4Ad38RyCe46FM6a9Pve1t1tQB/GRhhZqVmlkcwSPlQs3UeAj4V3r4I+JuHowMxddhjNrNJwK0E4R33vlE4zDG7e627D3D3EncvIej3v8DdK6Ipt8Pa8r5+kKD1jZkNIOhSWZ3CGpOtLce8DjgDwMxGEwR4dUqrTL2HgE+G30aZCtS6+6Z2by3qUdtWRmlfJxjB/nZ43/cIfoEheJH/CLwBvAQMj7rmFBzz08Bm4JXw30NR19zZx9xs3WeJ8bdQ2vgaG0G30XJgCXBx1DWn4JjHAM8TfEPlFeDsqGtOwjHPBjYB9QSfqi4HPg98PuF1/t/wOVnS0fe1TqUXEYmprtaFIiIibaQAFxGJKQW4iEhMKcBFRGJKAS4iElMKcMkYZlYZfse6Q+uIdBUKcBGRmFKAS1oyswfNbEF4be0rmy0rMbOVZjbLzFaY2Rwz65GwypfNbKGZLTGzUeFjppjZi+G1q18ws5EpPSCRFijAJV19xt0nE1z86yoza37FypHA/7n7aGAnwXXmD9rq7icCNwPXhPetBE5x90nAd4DrO7V6kTZQgEu6usrMXiW4jspQ3nthqPXu/nx4+y7gAwnLHgj/XwCUhLcLgD+GM63cBIztjKJFjoQCXNKOmZ0GnAmc7O4TCGa6yW+2WvNrSCT+fPBqj428c8nl7wPPuPs44CMtbE8k5RTgko4KgO3uvjfsw57awjrF4TWoAWYA/2jDNg9e9vPTSalSpIMU4JKOHgdyzGwFcANBN0pzrwH/Gq7Tl6C/+1BuBP7bzBahiVCki9DVCCXjmFkJ8HDYHSISW2qBi4jElFrgIiIxpRa4iEhMKcBFRGJKAS4iElMKcBGRmFKAi4jE1P8Det/yr8BWRFUAAAAASUVORK5CYII=\n", "text/plain": ["<Figure size 432x288 with 1 Axes>"]}, "metadata": {"needs_background": "light"}, "output_type": "display_data"}], "source": ["N = 1000\n", "obs = []\n", "for alpha in tqdm([0., 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.]):\n", "    total_null = 0\n", "    for i in range(0, N):\n", "        mat = random_symmetric_adjacency_matrix(10, alpha=alpha)\n", "        w, v = numpy.linalg.eig(mat)\n", "        nb_null = sum(numpy.abs(w) < 1e-7)\n", "        total_null += nb_null\n", "    obs.append(dict(alpha=alpha, null=total_null / N))\n", "\n", "df = pandas.DataFrame(obs)\n", "df.plot(x=\"alpha\", y=\"null\", title='nombre de valeurs propres nulles');"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On peut lire ce graphe de plusieurs fa\u00e7ons. Tout d'abord, si `alpha=0`, il n'y a aucun arc et la matrice est nulle, toutes les valeurs propres sont nulles. Si `alpha` est petit, il y a peu de coefficients non nuls et il est impossible de compresser l'information qu'elle contient en une matrice de rang inf\u00e9rieur."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q3 : que fait l'algorithme suivant\n", "\n", "On cr\u00e9e un tableau ``T=list(range(n))`` o\u00f9 ``n`` est le nombre de noeuds.\n", "\n", "Pour tous les arcs $V=(E_i, E_j)$ faire ``T[i] = T[j] = min(T[i], T[j])``.\n", "\n", "Recommencer tant qu'une valeur de ``T`` est mise \u00e0 jour."]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"data": {"text/plain": ["array([0, 1, 0, 3, 4, 1, 6, 7, 1, 9])"]}, "execution_count": 13, "metadata": {}, "output_type": "execute_result"}], "source": ["def connex_components(mat):\n", "    N = mat.shape[0]\n", "    T = numpy.arange(N)\n", "    \n", "    modifications = True\n", "    while modifications:\n", "        modifications = False\n", "        for i in range(N):\n", "            for j in range(i+1, N):\n", "                if mat[i, j] == 1 and T[i] != T[j]:\n", "                    T[i] = T[j] = min(T[i], T[j])\n", "                    modifications = True\n", "    return T\n", "\n", "mat = random_symmetric_adjacency_matrix(10, alpha=0.2)\n", "res = connex_components(mat)\n", "res"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le nombre de composantes connexes correspond au nombre de num\u00e9ro distincts dans le tableau que la fonction retourne."]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 11/11 [00:00<00:00, 65.36it/s]\n"]}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAy8AAAElCAYAAADtKd1/AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy89olMNAAAACXBIWXMAAAsTAAALEwEAmpwYAABPv0lEQVR4nO3dd3gU5frG8e+TBAi9hd4C0kIvoSkIigULgg0rYj8eu2AHsddzRD32dkRFsYAUUVFQQVE6CNJ7CTX0Gkh5f3/soDn5JRBImS3357r2YndnduaeybDvPvO+s2vOOURERERERIJdlN8BREREREREckPFi4iIiIiIhAQVLyIiIiIiEhJUvIiIiIiISEhQ8SIiIiIiIiFBxYuIiIiIiIQEFS8CgJl1M7OkQlzftWY2pbDW560z3sycmcUU5nrl/zOzoWb2lHe/UI89EZHjpfYjeKj9EBUvIiIiIiISElS8yAkxs2i/MwQLCyiQ/0v5fZZPZw1FRIKH2g+R46fiJciZ2Rozu9fM5pvZbjP73MxiM02/ycxWmNkOMxtrZtUzTXNmdquZLTezvWb2pJmdZGa/m9keM/vCzIpmWd/DZrbNW+9VmZ4famZvmtm3ZrYfOM3MqpvZSDNLNrPVZnbnUbajopdvj5nNAE7KMr2xmU3wtmOpmfXJYTmXmdmsLM/dY2Zjvfvnmdlcbz3rzeyxo2Qqa2bvm9kmM9tgZk8dKcrM7DEzG5Zp3v8ZMmBmk8zsaTP7DTgA1POGwq3y9vXqzPsvy3ofM7MR3t9yr5nNMbOWmaavMbMHzGw+sN/MYszsAjNbaGa7vHUnZJn/ITNbZGY7zeyDI8fIkS51b3mbgQ/MLMrMHjSzlWa23TsOKnjzx5rZMO/5XWY208yq5LAdOR6bls2wQG//1c/p75FpvhyPKzNrb2azvL/vFjMbcqzliUjo89quHWbWxntc3XuP6HYcy1D7ofZD7UcYUPESGvoAPYC6QAvgWgAzOx141pteDVgLfJbltWcDbYGOwP3AO8DVQC2gGXBFpnmrAnFADaAf8I6ZNco0/UrgaaA08DvwNTDPm787cLeZnZ3DNrwOpHg5r/dueNtREpgAfApUBi4H3jCzJtks52ugkZk1yJLrU+/+fuAaoBxwHvBPM+udQ6ahQBpQH2gNnAXcmMO82ekL3ExgfyQD/wHOcc6VBk4G/jjKa3sBXwIVvOyjzaxIpulXePnLAfWA4cDdQCXgW+Br+9/C8yoCf+uTgIbAoEzTqnrrqePlvQPoDXQFqgM7Cfx9IPB3L0vg+KgI3AIcPMp2ZHtsnigLnIE82nH1CvCKc64MgW39Ii/rE5HQ4JxbCTwADDOzEsAHwIfOuUkAZvaG94E5u9t8bzFqP9R+qP0IAypeQsN/nHMbnXM7CPzHbOU9fxXwX+fcHOfcIeAhoJOZxWd67QvOuT3OuYXAAuAH59wq59xu4DsCb7qZPeKcO+Scmwx8Q+DN5YgxzrnfnHMZQHOgknPuCefcYefcKuBdAoXH//DORl0MDHbO7XfOLQA+zDTL+cAa59wHzrk059xcYCRwadZlOecOAGPwii6vEWoMjPWmT3LO/emcy3DOzSfwpt01m0xVgHOBu71MW4GXsst/FEOdcwudc2kEGrEMoJmZFXfObfL2eU5mO+dGOOdSgSFALIEC84j/OOfWO+cOApcB3zjnJnjz/xsoTqCBO+I1b/4dBArMzEVpBvCo93c9SKBBGeicS/KOm8eAS7yzgqkEGp36zrl059xs59yeo2xHTsfmiWrH0Y+rVKC+mcU55/Y556blcX0iEiKcc+8CK4DpBE6EDcw07VbnXLkcbi28edR+qP1Q+xEGVLyEhs2Z7h8ASnn3qxPobQHAObcP2E7gjMMRWzLdP5jN41KZHu90zu3P9Hitt44j1me6XweonvnsFvAwkF0XcSUgJsvr12a6XwfokGVZVxE445OdT/n7zfVKYLTXKGFmHczsZ6/LeDeBN9q4bJZRBygCbMq0zrcJ9Pzk1l/b4+23y7z1bTKzb8yscS5fmwEkkfO+zvp3zvCm18hh/qx/t2TnXEqmx3WAUZm2ezGQTuBv9zHwPfCZmW00sxeynNHLKqdj80Qd67i6gcCZwSXekITz87g+EQkt7xIYNfCq9+H5eKn9UPuh9iPEqXgJbRsJ/GcF/hp+VRHYcILLK+8t44ja3jqOcJnurwdWZzm7Vdo5d242y00mcGapVpZlZ17W5CzLKuWc+2cOOScAlcysFYFG6NNM0z4lcBatlnOuLPAWYNksYz1wCIjLtM4yzrmm3vT9QIlM82dXSLn/eeDc9865MwmcEVxCoJHNyV/7wuvqrknO+zrr39m812f+O2fdtzktCwLbfk6W/R3rnNvgnEt1zj3unGtC4Mzc+QSGURyv/9l/ZpZTIZrVUY8r59xy59wVBD4kPA+MyHLMikiYMrNSwMvA+8BjR6618Ka9ZWb7crhl7sVQ+6H2Q+1HiFPxEtqGA9eZWSszKwY8A0x3zq3JwzIfN7OiZtaFwBvPlznMNwPYa4EL+YqbWbSZNTOzdllndM6lA18RaGxKeNey9Ms0yzigoZn1NbMi3q2dZbqoMMvyUr1c/yIwFndCpsmlgR3OuRQza0/gzFp2y9gE/AC8aGZlLHAR4klmdmSIwB/AqWZW28zKEhiSlyMzq2Jmvbw3wkPAPgLd7Tlpa2YXeV3td3uvyakL+wvgPDPr7p3FGuDN/3umeW4zs5peYz4Q+Pwo634LeNrM6njZK5lZL+/+aWbW3Bvqt4dAN/vRtiMn84Cm3rEZS2BoQW4c9bgys6vNrJJ39nCX95oTyScioecVYJZz7kYCw5rfOjLBOXeLd9Iru1vTTPOp/VD7ofYjxKl4CWHOuYnAIwSuD9lE4AK04xlzm9VmAhffbQQ+AW5xzi3JYd3pBIqbVsBqYBvwHoGL9bJzO4Eu4c0ELnT8INOy9hK42PFyb92bCZwVKXaUrJ8CZwBfemOGj7gVeMLM9gKDOfoFedcARYFFBLZ7BIGzXjjnJhB4A58PzCZQYB1NFNDfy7+DwDjpnHqOIDDu+jJvvX2Bi7xG9f9xzi0l8CULrxLYzz2Bns65w5lm+5RAY7oKWAk8dZR1v0Lg7OIP3n6aBnTwplUlsB/2EBgOMJnAUIDj4pxbBjwBTASWA7n6QdJcHFc9gIVmts/bjsu9cdgiEsa8D8g9+Pt9tT/QxnL4Vq5jUPuh9kPtRwgz57L2CIpIQbLA12/Wd85dnU/LWwPc6BWzIiISptR+iKjnRUREREREQoSKFxERERERCQkaNiYiIiIiIiFBPS8iIiIiIhISVLxItsysm5klFeL6rjWzXH2jiIiIiIhEJhUvQcTMHjOzYX7nkNBgZmvM7Ay/c4iISHBR+yDhTMWL5AvvR6lERERERAqMipdCZmbVzWykmSWb2Wozu9N7vgfwMHCZme0zs3k5vH6Nmd1rZvPNbLeZfe79Au2R6TeZ2Qoz22FmY82seqZpzsxuNbPlZrbXzJ70fhX4dzPbY2ZfmFnRLOt72My2eeu9KtPzQ83sTTP71sz2A6fltG05bEdFL98eM5tB4Ac2M09vbGYTvO1YamZ9jrKsCmb2gZltNLOdZjY6v/fHkWF0R9kfZc3sI2/b15rZIDOL8qbVN7PJ3t9rm5l9nul1r5jZem99s82sS6Zpj3kZPvLyLTSzRG/ax0Bt4GvveLnfe76jl3+Xmc0zs26Zlnetma3ylrXacvhxNwv8KvHDZrbSm3e2mdXypp1sZjO9bZlpZidnet0kbx/+5r3uBzOL86bFe/u7n5mt8/bDwEyvjTKzB711bve2u4I37U0zG5lp3ufN7EcLKGZm//aWucXM3jKz4t58cWY2ztsXO8zs1yN/ExEJbmZ2X+b/995z/zGzV45zOWof1D6ofQg3zjndCulGoFicTeCXe4sC9Qj8ou3Z3vTHgGHHWMYaYAZQHahA4Fdsb/GmnU7gF2XbEPh1+leBXzK91hH4Zd4yQFPgEPCjl6MsgV8K7ufN2w1IA4Z4y+oK7AcaedOHAruBU7ztKnG0bctmOz4j8OvFJYFmwAZgijetJLAeuA6IAVp729Ukh2V9Q+DXjMsDRYCuPuyPj7xllQbigWXADd604cBAbz/FAp0zZbgaqOht5wBgMxCb6XhIAc4FooFngWlZjoUzMj2uAWz35o8CzvQeV/L26Z5MeasBTXPYn/cBfwKNAANaehkr8PcvOscAV3iPK3qvm0Tg15kbAsW9x8950+K9/f2uN62lt78TvOl3Efil5pre/n0bGO5NK+Htz2uBLt7ftKY37SUCv/Zcwdv3XwPPetOeBd4icEwU8V5rfr8P6Kabbse+ee9R+4Fy3uMYYCvQ1nv8BrArh9v8TMtR++DUPqD2IaxuvgeIpBvQAViX5bmHgA+8+4+Ru+Ll6kyPXwDe8u6/D7yQaVopIBWI9x474JRM02cDD2R6/CLwsne/G4E345KZpn8BPOLdHwp8lNtty/J8tJercabnnuHv4uUy4Ncsr3kbeDSbZVUDMoDy2UwrlP3hbc9hMhVXwD+ASd79j4B3jryhHuPvuxNomel4mJhpWhPgYJZjIXPj9ADwcZblfQ/0I9A47QIuBoofI8NSoFc2z/cFZmR5bipwrXd/EjAo07RbgfHe/Xhvf9fMNH0GcLl3fzHQPcvfNRWIyXR87QDWAld4zxmBDwgnZXpdJ2C1d/8JAh8Y6ufl/61uuunmzw34DrjJu38+sOg4X6/24e/Hah/UPoTNTV1khasOUN3rptxlZrsIDBWrcpzL2Zzp/gECb7oQ6I1Ze2SCc24fgTMrNTLNvyXT/YPZPC6V6fFO59z+TI/Xeus4Yn2m+8ezbZUInJnJ/Pq1me7XATpkWdZVQNVsllUL2OGc25nNtMLaH3EEztyszTLtyHruJ/BGOsPr2r/+yEwWGAK42Otm30XgjF5cpuVk/VvHmllMNtsKgf12aZb91hmo5uW+DLgF2GRm35hZ4xyWU4vAGbKs/md/ZrOd2eUt9b+z5zi9DjAqU+7FQDre8eOcm06gJ88IfCiAwHFUApid6XXjvecB/gWsAH7whkM8mMP2ikhw+pBA7wPevx8f5+vVPvxN7YPah7Ch4qVwrSdQ9ZfLdCvtnDvXm+7yuPyNBP6TA2BmJQl05244weWV95ZxRG1vHUdkznusbcssmcBZqlpZlp15WZOzLKuUc+6f2SxrPVDBzMplM62w9sc2AmeB6mSZtgHAObfZOXeTc646gTNub1hgnHMXAg1XHwJnBssRGIpnucyT9XhZT+DMWub9VtI595yX43vn3JkEzlotIdBFn531ZLkGyfM/+zPrdubReuCcLNljnXMbAMzsNgLDBTYS2GcQ2O8HCQxvOPKass65UgDOub3OuQHOuXrABUB/M+ueD1lFpHCMBlqYWTMCPS+fHJngXb+wL4fbQm82tQ9/U/ug9iFsqHgpXDOAvWb2gJkV9y58a2Zm7bzpW4D4PFw0Nhy4zsxamVkxAkOxpjvn1uQh8+NmVtR7Iz0f+DKH+Y61bX9xzqUDXwGPmVkJM2tCoOv6iHFAQzPra2ZFvFs7M0vIZlmbCAwteMPMynvznupNLpT94W3PF8DTZlbazOoA/YFhAGZ2qZnV9F6/k0CjkkFgDG4agWIuxswGExhfnVtbCIy/PmIY0NPMzvb2f6wFLiStaWZVzKyX17geAvZ5GbLzHvCkmTWwgBZmVhH4lsDf5UozizGzywgMVRh3HJlz8haB/VcHwMwqmVkv735D4CkCZ177AvebWSvnXAaBBvYlM6vszVvDzM727p/vfQgwAo1++lG2WUSCjHMuBRgBfEpgSNK6TNNu8U5qZXdr6s2j9uFvah/UPoQNFS+FyHsTOx9oBawmcGbgPQJdwfB3YbDdzOacwPInEhhjOxLYRODsyOV5iLyZwJvpRgJnvG5xzi3JYd3H2rasbifQJbyZwPUzH2Ra1l7gLC/7Rm+e5wmcWclOXwJntpYQuKDzbm85hbk/7iAwvnYVMIVAY/tfb1o7YLqZ7SNw8eBdzrlVBMYbjydwseFaAhdfZh5KdyzPAoMs0CV+r3NuPdCLwHC9ZG9Z9xH4fx5FoMHcSGBscFcgu54sCFx0+gXwA4GLON8nMA56O4G/8QACwyvuB853zm07jsw5eYXAvvnBzPYSuDizgwWGQAwDnnfOzXPOLfe272PvA8cDBLr+p5nZHmAigQtJARp4j/cRGHv9hnPu53zIKiKF50OgOcc/ZOwItQ9qH9Q+hBlzLq8jlUTCnwW+UnKYc67mMWYVEZF8Yma1CRQeVZ1ze/zOkx21DyKFSz0vIiIiEnS8IdT9gc+CtXARkcKX07dSiIiIiPjCu/5iC4EhUz18jiMiQUTDxkREREREJCRo2JiIiIiIiISEQh02FhcX5+Lj4wtzlSIiksXs2bO3OecqHXvOyKN2SkTEf0drpwq1eImPj2fWrFmFuUoREcnCzLL+ErZ41E6JiPjvaO2Uho2JiIiIiEhIUPEiIiIiIiIhQcWLiIiIiIiEBP3Oi4hEvNTUVJKSkkhJSfE7Sr6KjY2lZs2aFClSxO8oIS0cjw8dGyISqlS8iEjES0pKonTp0sTHx2NmfsfJF845tm/fTlJSEnXr1vU7TkgLt+NDx4aIhLJjDhszs/+a2VYzW5DpuQpmNsHMlnv/li/YmCIiBSclJYWKFSuGxQfTI8yMihUrhlVvQU4Kup0Kt+Mjko4NEQk/ubnmZSjQI8tzDwI/OucaAD96j0VEQla4fDDNLBy3KQdDKeB2Ktz2Zbhtj4hEjmMWL865X4AdWZ7uBXzo3f8Q6J2/sf6/GSNfYu4Pw3AZGQW9KhERCSHB0k6JiES6jAzHsGlr+WnJlgJbx4l+21gV59wm7/5moEpOM5rZzWY2y8xmJScnn9DKMtLTKbv4M1r/fhvz/nUOG9csPaHliIiEi0mTJnH++ecDMHToUG6//XafEwWdQm2nREQi3YINu7nwzd8ZNHoB4+ZvOvYLTlCevyrZOecAd5Tp7zjnEp1ziZUqVTqhdURFR1Pv/l+YVv9uGh6YS/kPOjNt6MMcPqTxuiIicnSF0U6JiESqPSmpPDZ2IRe8NoUNOw/w8mWtePHSlgW2vhMtXraYWTUA79+t+Rcpe0WKFqPj1Y+z58bfWVyqAx3XvM6m59uy4LevC3rVIiIFbs2aNSQkJHDTTTfRtGlTzjrrLA4ePEi3bt2YNWsWANu2bSM+Pt7foKGj0NupgvTRRx/RokULWrZsSd++fbn22mu58847Ofnkk6lXrx4jRowAYNSoUXTv3h3nHJs2baJhw4Zs3rzZ5/QiEo6cc4ydt5EzXpzMh1PXcFWHOvw4oBu9W9co0OvqTvSrkscC/YDnvH/H5FuiY6haqz5V7xvHvJ++oNKvg2g24WpmTT+T+CtfIq5qrcKKISJh6vGvF7Jo4558XWaT6mV4tGfTY863fPlyhg8fzrvvvkufPn0YOXJkvuaIMAXSTvlxfCxcuJCnnnqK33//nbi4OHbs2EH//v3ZtGkTU6ZMYcmSJVxwwQVccsklXHjhhYwcOZLXX3+d8ePH8/jjj1O1atV8zSsisip5H4PHLGTKim00r1GWd69JpGWtcoWy7mMWL2Y2HOgGxJlZEvAogcbgCzO7AVgL9CnIkNlpeXofDnY4h6mfPkLbpI9Ieas90xPuJvHiAUTH6OdrRCT01K1bl1atWgHQtm1b1qxZ42ueUBGs7VR++emnn7j00kuJi4sDoEKFCgD07t2bqKgomjRpwpYtf18c++qrr9KsWTM6duzIFVdc4UtmEQlPKanpvPHzCt6avIpiMVE80aspV3WoQ3RU4X2D4TE/5Tvncnrn657PWY5b8ZKl6XTTy6xbdi17Rt5Fh8XPsOy5Edj5Q2jQqovf8UQkBOWmh6SgFCtW7K/70dHRHDx4kJiYGDK8b1nU73JkrzDbKT+Pj6wyHy+By3oCkpKSiIqKYsuWLWRkZBAVlefLW0VE+HnpVh4ds5B1Ow7Qq1V1Bp6XQOXSsYWeIyze0Wo3bEXTB35mVtsXqJC2lXqjejL9tevZs2u739FERPIkPj6e2bNnA/x1XYNEltNPP50vv/yS7dsDbdqOHVm/FfpvaWlpXH/99QwfPpyEhASGDBlSWDFFJExt2n2Qfw6bzXUfzCQm2vj0xg68cnlrXwoXOPFrXoKORUWR2PMf7O58MbM+uZ/E5K/Y+fKPzGr7MG3PuwnTmScRCUH33nsvffr04Z133uG8887zO474oGnTpgwcOJCuXbsSHR1N69atc5z3mWeeoUuXLnTu3JmWLVvSrl07zjvvPBISEgoxsYiEg7T0DIb+voaXJiwjLcNx71kNuenUehSLifY1l2Xuai5oiYmJ7si35hS05X/8CuPuoUHachYUa0WZi1+hdsNWhbJuEQktixcvDtsPd9ltm5nNds4l+hQpqGXXToXr8RGu2yUieTd77Q4GjlrAks17Oa1RJR6/oBm1K5YotPUfrZ0Km56XrBq06kJ6s2lM/2oICYteIvaT7kytdQ2tr3yS2BKl/I4nIiIiIhJUdu4/zHPfLeHzWeupVjaWt65uy9lNqxToVx8fr7AeSxUdE0OHPvdz+JYZzC97Gp2S/suOf7Vh3k9f+B1NRERERCQoZGQ4vpi5ntNfnMSIOUncfGo9JvbvSo9mVYOqcIEwL16OiKtai8T+I1hw5jBSrQgtf7mJOf86n83rV/gdTUREQkBhDrEuDOG2PSJy4pZs3kOft6dy/8j5nFSpFN/c2ZmHz02gZLHgHKAVEcXLEc1O6Um1B2Yzte5tJOybTpn3TmbasMdIPXzI72giIhKkYmNj2b59e9h84HfOsX37dmJj/fmmIBEJDvsPpfH0N4s47z9TWJm8jxcuacEX/+hE46pl/I52VMFZUhWgosVi6dTvGTauvoatX9xFxxUvsfq5URw6+1807nCW3/FERCTI1KxZk6SkJJKTk/2Okm9iY2OpWbOm3zFExAfOOb5fuJnHv17Ept0pXN6uFg/0aEz5kkX9jpYrEVe8HFG9bmOq3fcdcyd+SrXfH6Xud5cyY+q5NLhqCOUrVfM7noiIBIkiRYpQt25dv2OIiOTZuu0HeHTsAn5emkzjqqV57crWtK1Twe9YxyWiho1lZVFRtD7rasrcO4ep1a6m9c7vsdcTmTHyZTLS0/2OJyIiIiKSZ4fS0nn1x+Wc+dJkZqzewaDzEhh3R+eQK1wggnteMitRqiyd/vE6qxddy8FRd9P+z0dZsuRzivZ6mXrNOvgdT0RERETkhPy2YhuPjFnAquT9nNu8Ko+c34RqZYv7HeuERXTPS1Z1m7Qj4aFfmdnqaaqkJlH7yx5Me/MW9u3Z6Xc0EYkAH330ES1atKBly5b07duXa6+9ljvvvJOTTz6ZevXqMWLECABGjRpF9+7dcc6xadMmGjZsyObNm31OLyIiwWTr3hTuHD6Xq96bTlq6Y+h17XjjqrYhXbiAel7+H4uKol3v29nd5VJmf3of7Td/xrYh37Osw2Ban90Pi1K9JxLWvnsQNv+Zv8us2hzOee6osyxcuJCnnnqK33//nbi4OHbs2EH//v3ZtGkTU6ZMYcmSJVxwwQVccsklXHjhhYwcOZLXX3+d8ePH8/jjj1O1atX8zSwiIiEpPcMxbNpa/v39Ug6lZXBn9wbc2u0kYotE+x0tX6h4yUHZilXocMdHLJn1I0W+u5c20+9m7oIRtLhnDNEx2m0ikr9++uknLr30UuLi4gCoUCEwDrl3795ERUXRpEkTtmzZ8tf8r776Ks2aNaNjx45cccUVvmQWEZHgMm/9LgaNXsCfG3bTuX4cT/RqSr1KpfyOla/0KfwYGid2J63ldKYOe4ROa99ixtdv0P7CO/2OJSIF5Rg9JIWtWLFif93P/DsjSUlJREVFsWXLFjIyMohSr7CISMTafTCVf32/hE+mryOuVDH+c0Vreraohpn5HS3fqbXLhZgiRenY71mWxjSm7rwh7N+7y+9IIhJmTj/9dL788ku2b98OwI4dO3KcNy0tjeuvv57hw4eTkJDAkCFDCiumiIgEEecco+Ym0f3FSXw6fR39OsXz44CuXNCyelgWLqCel1yzqChcj2eoNO4ipn7xJJ1ueNHvSCISRpo2bcrAgQPp2rUr0dHRtG7dOsd5n3nmGbp06ULnzp1p2bIl7dq147zzziMhIaEQE4uIiJ9WbN3LoNELmLZqBy1rlWPode1pVqOs37EKnIqX49A4sTuzJ59Oq3UfsSXpVqrUPMnvSCISRvr160e/fv1ynL5v3z4ABg8e/NdzpUuXZsmSJQWeTUREgsPBw+m8+tNy3v11FcWLRPP0hc24vF1toqPCs6clKw0bO07VL3mOKBzrvnzQ7ygiIiIiEkEmLtrCGUMm88aklfRsWZ2f7u3GVR3qREzhAup5OW7V6jRiao0r6bTxQ5bP/YUGrU/1O5KIiIiIhLENuw7y2NiFTFi0hfqVS/HZzR3pWK+i37F8oeLlBDS77DG2vzSa1G8fwrX8Vb/9IhIGnHNhd3Fj5m8nExGR0JOansH7U1bzysTlOBwP9GjMDZ3rUjQmcj97Ru6W50HpshVY0fQumqQu4I8JH/sdR0TyKDY2lu3bt4fVh33nHNu3byc2NtbvKCIicgKmr9rOua/8ynPfLeGU+nFM7N+Vf3Y7KaILF1DPywlr2/sOVi/+kErTnuFQ10spFlvC70gicoJq1qxJUlISycnJfkfJV7GxsdSsWdPvGCIichy27zvEM98uYeScJGqUK8671yRyZpMqfscKGipeTlBMkaLs6/oYzX++jmkjXqDj1Y/5HUlETlCRIkWoW7eu3zFERCSCZWQ4hs9cxwvjl7L/UBr/7HYSd5xenxJF9XE9M+2NPGje9SLmTX2DJiveZmfyPyhfqZrfkUREREQkxCzYsJtBoxfwx/pddKhbgad6N6NBldJ+xwpKkT1oLh+U6/U8JVwKyz4f6HcUEREREQkhe1NSefzrhVzw2hTW7zjAkD4t+ezmjipcjkI9L3lUJ6Et0yv1pm3yKNYuvZM6jVr5HUlEREREgphzjnHzN/HkuEUk7zvEle1rc//ZjSlboojf0YKeel7yQYM+T3GQYuwc/YDfUUREREQkiK3etp9r/juDO4bPpXKZYoy69RSevrC5CpdcUs9LPqhQuQbT6t9Mx5Wv8OcvY2h+ai+/I4mIiIhIEElJTefNSSt5c/JKikVH8VjPJvTtFE90VHj9xlhBU89LPml1yQNstCqUnDSY9LQ0v+OIiIiISJCYvCyZs1/+hVd+XE6PplX5cUBXrj2lrgqXE6DiJZ/EFi/JpnYPUS9jDbPHvOp3HBERERHx2ebdKdz2yRz6/XcG0WYMu6ED/7miNZXL6AeET5SGjeWjNj36sXjuO9T782X2nXktpcqU9zuSiIiIiBSytPQMhv6+hpcmLCM1w9H/zIb8o2s9isVE+x0t5KnnJR9ZVBTR5zxLHLv48/PH/Y4jIiIiIoVs9tqd9HztN576ZjGJ8RWYcM+p3Nm9gQqXfKKel3zWsE03Zk06g9ZJw9i87jaq1m7gdyQRERERKWA79x/m+fFL+GzmeqqWieXNq9rQo1lVzHRdS35Sz0sBqHnJcwAkjXjQ5yQiIiIiUpAyMhxfzFpP9yGT+XJ2Ejd2rsvEAV05p3k1FS4FIE/Fi5ndY2YLzWyBmQ03M119BFSt3YC5Na8mcc9Els2Z5HccEZGIpXZKRArS0s17ueydqdw/Yj7xFUsw7o7ODDq/CaWKaXBTQTnh4sXMagB3AonOuWZANHB5fgULdc0ve5RtlCPju4dwGRl+xxERiThqp0SkoOw/lMYz3y7m3P/8yvKt+3j+4uaMuOVkEqqV8Tta2MvrsLEYoLiZxQAlgI15jxQeSpUpz6rm99A4dRFzxn/odxwRkUildkpE8o1zjvELNnPmkMm888sqLmlTk58GdOOydrWJ0m+2FIoTLl6ccxuAfwPrgE3AbufcD1nnM7ObzWyWmc1KTk4+8aQhqG2v21kVFU+1mc+ScnC/33FERCKK2ikRyU/rdxzghg9nccuw2ZQpXoQRt3Ti+UtaUKFkUb+jRZS8DBsrD/QC6gLVgZJmdnXW+Zxz7zjnEp1ziZUqVTrxpCEoOiaG/d2eoLrbwh8jnvc7johIRFE7JSL54VBaOq/9tJwzhkxm2qrtDDovga/v6ExifAW/o0WkvAwbOwNY7ZxLds6lAl8BJ+dPrPDR/NRe/FG8I01XvMOOrRv8jiMiEknUTolInvy+YhvnvPIr//5hGac3rsyPA7pyY5d6FInWF/b6JS97fh3Q0cxKWOB74LoDi/MnVngp3/t5inOI5Z8/7HcUEZFIonZKRE7I1r0p3P3ZXK58bzpp6Y4PrmvHm1e3pVrZ4n5Hi3gn/D1uzrnpZjYCmAOkAXOBd/IrWDip06gV0ytdSGLyV6xZPIv4hES/I4mIhD21UyJyvNIzHJ9MX8u/vl/KodQM7jy9PreeVp/YItF+RxNPnr6E2jn3KPBoPmUJa40uf4b9r41n95gHIWGi33FERCKC2ikRya35SbsYNHoB85N2c0r9ijzRqxknVSrldyzJQgP2Ckm5uKosavAPWqbMZP6kkX7HERERERFg98FUBo9ZQK/Xf2PT7hReubwVw27ooMIlSKl4KUStL76PJKtKmV8eIy31sN9xRERERCKWc47RczfQ/cXJDJu2ln6d4vlxQFd6tapB4DI5CUYqXgpRsdgSJHd8mPiMdcwe/R+/44iIiIhEpBVb93HVe9O5+/M/qFEuljG3deaxC5pSJraI39HkGPJ0zYscv1Zn9mXRrHdosPAV9p51PaXL6jvCRURERArDwcPpvPbzct75ZRWxRaJ5snczrmxfm+go9bSECvW8FDKLiqLIuc9SgT0s+FzXkIqIiIgUhp+WbOHMlybz+s8r6dmiOj8N6EbfjnVUuIQY9bz4oEHrU5k56WzabBjOxjW3Uz2+kd+RRERERMLShl0HeXzsQn5YtIX6lUvx2c0d6Vivot+x5ASp58UntS99lgyMTSMf9DuKiIiISNhJTc/g7ckrOePFyfyyPJn7ezTi2zu7qHAJcep58UmVmicxtfY1dFr/HktmTqRxuzP8jiQiIiISFmas3sGg0X+ybMs+zkiozKM9m1KrQgm/Y0k+UM+Lj1r0eYRkymPfD8RlZPgdR0RERCSkbd93iHu/nEeft6ey/1A6716TyHv92qlwCSMqXnxUsnQ5VrfsT6O0Jcz+7n2/44iIiIiEpIwMx/AZ6zj9xcmMnruBW7qexIT+p3Jmkyp+R5N8pmFjPmvb81ZWLviAmjOfJ+W0K4gtoV9zFREREcmthRt3M2j0Auau20X7uhV4qnczGlYp7XcsKSDqefFZdEwMB09/gqokM/fLZ/2OIyIiIhIS9h1K44mvF9Hz1Sms236AFy9tyec3d1ThEubU8xIEmp3Sk7m/nUzzVe+zbfMtxFWt5XckERERkaDknOPbPzfzxLiFbN17iCva1+b+sxtRrkRRv6NJIVDPS5CIu/A5inGYlV8O9DuKiIiISFBas20//T6YyW2fzqFiyWJ89c+TeebC5ipcIoh6XoJErQYtmVblYtpt+ZLVC6dTt2kHvyOJiIiIBIWU1HTemrySNyatpGh0FI/2bELfjnWIidZ5+Eij4iWIJFz2FPte/YZ9Yx/EJfyIRek/pIiIiES2X5cn88joBazZfoDzW1TjkfObUKVMrN+xxCf6dBxEylaswuKGt9L80BzmTx7pdxwRERER32zZk8Jtn86h7/szMDM+vqE9r13ZRoVLhFPxEmTaXHwv66065X59nLTUw37HERERESlUaekZ/HfKarq/OJkJi7ZwzxkN+e6uLnRpUMnvaBIEVLwEmaLFYtnWaSB1MtYze9TLfscRERERKTRz1u3kgtd+44lxi2hbpzwT7jmVu85oQGyRaL+jSZDQNS9BqNUZV7Jw1ts0XPQqu3deT9nycX5HEhERESkwuw4c5vnxS/ls5jqqlI7ljavacE6zqpiZ39EkyKjnJQhZVBTFznuWsm4viz8f7HccERERkQLhnGPE7CS6vziZL2at54ZT6jJxQFfObV5NhYtkSz0vQap+y87M/LkHbTZ9zoZVd1CjXoLfkURERETyzbItexk0agEz1uygTe1yfNy7OU2ql/E7lgQ59bwEsfg+z5FGNFu+esDvKCIiIiL54sDhNJ79bjHnvvIry7bu5bmLmjPilpNVuEiuqOcliFWqHs/UOtfSad3bLJn+A407nOV3JBEREZET4pzjh0VbeHzsQjbuTqFPYk0ePCeBCiWL+h1NQoh6XoJcyz4D2UoFoiYMJCM93e84IiIiIsdt/Y4D3PjhLP7x8WxKxxbhy1s68cIlLVW4yHFT8RLkSpQqy9pW99IwbRlzvnnX7zgiIiIiuXY4LYPXf17BmS9NZuqq7Tx8bmPG3dmZdvEV/I4mIUrDxkJA2563sOLP96k15wUOdr+K4iVL+x1JRERE5KimrtzOoNF/sjJ5Pz2aVmVwzyZUL1fc71gS4tTzEgKioqM51P0pqrCdeaNe9DuOiIiISI6S9x7ins//4Ip3p3E4PYMPrm3HW33bqnCRfKGelxDR9ORz+XNyGxqueJ8D++6hRKmyfkcSERER+Ut6huPT6Wt54fulpKSmc/tp9bnttPoULxrtdzQJI+p5CSFFuj9MBfYwX70vIiIiEkT+TNrNRW/8xiNjFtK8RlnG330q957dSIWL5Dv1vISQxu3PZP5PbWm08gP27+1PydLl/I4kIiIiEWxPSiovfr+Uj6etpULJYrxyeSsuaFkdM/M7moQp9byEmKJnDKS8el9ERETER845xvyxgdP/PZmPp62lb8c6/HRvV3q1qqHCRQqUel5CTOPE7syf2I7Gqz5g357+lCpT3u9IIiIiEkFWJu9j8JgF/LZiOy1qluWDa9vRvKauxZXCoZ6XEBR71iDKs5c/R/3b7ygiIiISIVJS03nxh6Wc8/KvzE/azZO9mzHq1lNUuEihUs9LCGrYphvzJrQnYfVQ9u25V70vIiIiUqB+XrKVwWMXsH7HQS5sXYOHz02gUulifseSCJSnnhczK2dmI8xsiZktNrNO+RVMjq74mYMoxz4WfPUvv6OIiAQttVMiebNx10Fu+Xg21w2dSdHoKD69qQMvXdZKhYv4Jq89L68A451zl5hZUaBEPmSSXGjYpivzJnQgYc1Q9u6+l9JlK/gdSUQkGKmdEjkBqekZDP1tDS9NXEaGc9x3diNu6lKPojG64kD8dcJHoJmVBU4F3gdwzh12zu3Kp1ySCyXOGkRZ9rPgq+f9jiIiEnTUTomcmFlrdtDz1Sk8/e1iOtWryIR7unLbafVVuEhQyMtRWBdIBj4ws7lm9p6Zlcw6k5ndbGazzGxWcnJyHlYnWTVofSp/lOhE07Ufs2fXdr/jiIgEG7VTIsdhx/7D3D9iHpe8NZU9B1N5u29b3uuXSK0K6rCU4JGX4iUGaAO86ZxrDewHHsw6k3PuHedconMusVKlSnlYnWSn1NmDKMN+Fqr3RUQkK7VTIrmQkeH4fOY6Tn9xEl/N2cA/utZj4oCunN20qn6zRYJOXoqXJCDJOTfdezyCQCMhhah+y87MLXEyTdcNY/fObX7HEREJJmqnRI5h8aY9XPr2VB4Y+ScNK5fmmzu78NA5CZQoqi+kleB0wsWLc24zsN7MGnlPdQcW5UsqOS6lvd6XRaPU+yIicoTaKZGc7TuUxlPjFnH+q1NYvW0//760JZ//oyONqpb2O5rIUeW1rL4D+MT7BpdVwHV5jyTHq37LU5j7/Sle78sDlC0f53ckEZFgoXZKJBPnHN8t2MwTXy9i854Urmhfmwd6NKJciaJ+RxPJlTwVL865P4DE/IkieVHmnMGUGXk2U796lk43vOh3HBGRoKB2SuRva7fvZ/CYhUxelkxCtTK8cXUb2tTWD11LaNGAxjBxUvOOzBnfhWbrPmH3jgcpW0EXnYqIiAgcSkvnrUmreH3SCopGRzH4/CZc06kOMdH66mMJPTpqw0i5cx6htB1k0VfP+B1FREREgsCU5dvo8fKvvDRxGWc1qcLE/l25vnNdFS4SstTzEkbqNevAnPGn0nz9cHZvf5CyFav4HUlERER8sGVPCk99s5iv520kvmIJPrq+Pac21KgMCX0qu8NM+XMHU8oOsuirZ/2OIiIiIoUsLT2DD35bTfcXJ/P9ws3cfUYDxt99qgoXCRvqeQkzdZu0Y06prrRIGs6ubQ9SLq6q35FERESkEPyxfhcDR/3Jwo17OLVhJZ64oCnxcSX9jiWSr9TzEoYqnDeY4hxisa59ERERCXu7D6Ty8Kg/ufCN39i27xCvX9mGD69rp8JFwpJ6XsJQfEIis8t0o8WGz9mZ/BDlK1XzO5KIiIjkM+ccX83ZwDPfLmbngcNcd3Jd7jmzAaVji/gdTaTAqOclTMWd+wjFOcQS9b6IiIiEneVb9nL5O9MY8OU8alcswdd3dGZwzyYqXCTsqeclTNVJaMusMqfTcuPn7Nj6IBUq1/A7koiIiOTRgcNp/OfHFbz36ypKFovh2Yuac1liLaKizO9oIoVCPS9hrNL5g4nlMEtHqfdFREQk1E1YtIUzh/zCW5NX0rt1DX4a0JUr2tdW4SIRRT0vYaxOo1bMKtudlhu/ZPuWh6hYpabfkUREROQ4Je08wGNjFzFx8RYaVinFF//oRPu6FfyOJeIL9byEucrnP0IxDrNcvS8iIiIh5XBaBm9MWsEZQybz24ptPHROY765s4sKF4lo6nkJc7UbtmJW2TNouelLtm1+iLiqtfyOJCIiIscwbdV2Hhm9gOVb93F20yoM7tmUGuWK+x1LxHfqeYkAVXo+QlFSWTHqab+jiIiIyFFs23eI/l/8weXvTONgajrv90vk7b6JKlxEPOp5iQC1GrRkZrmzaLl5JNs2P0xc1dp+RxIREZFMMjIcn85Yxwvjl3AwNZ3bTjuJ209rQPGi0X5HEwkq6nmJENV6DqYIaaz46im/o4iIiEgmCzbs5sI3f2fQ6AU0rV6W7+46lfvObqzCRSQb6nmJEDXrN2NmubNoteUrtm0cSFz1On5HEhERiWh7UlIZ8sMyPpq6hgoli/HyZa3o1ao6ZvrqY5GcqOclglTvNZgY0lkxWr0vIiIifnHOMXbeRs54cTIfTl3D1R3r8OOArvRuXUOFi8gxqOclgtSo15QZ5XvQessokjcOpFL1eL8jiYiIRJRVyfsYPGYhU1Zso3mNsrzXL5EWNcv5HUskZKjnJcLUuGAwUWSwatSTfkcRERGJGCmp6Qz5YSk9Xv6VeUm7eLJXU0bfdooKF5HjpJ6XCFOjXgIzKvSg1dYxbN0wiMo16vodSUREJKz9vHQrj45ZyLodB+jdqjoPn5dA5dKxfscSCUnqeYlANb3el9WjnvA7ioiISNjatPsg/xw2m+s+mElMtPHpjR14+fLWKlxE8kA9LxGoet3GzKhwDq2Tx7J5/Qqq1qrvdyQREZGwkZaewdDf1/DShGWkZTjuO7sRN3apS7EYffWxSF6p5yVC1ew1GMOxdszTfkcREREJG7PX7uD8V6fw1DeL6VCvIhP7d+W20+qrcBHJJ+p5iVDV4xsxveJ56n0RERHJBzv3H+a575bw+az1VCsby1tXt+XsplX01cci+Uw9LxGsTu/BgGPtaH3zmIiIyInIyHB8MXM9p784iZFzkvjHqfWY2L8rPZpVVeEiUgDU8xLBqtZuwPS4nrTe9jWb1i6lWp1GfkcSEREJGUs272HQqAXMWruTdvHleap3cxpVLe13LJGwpp6XCFen9yMArBvzlM9JREREQsP+Q2k8/c0izvvPFFYm7+OFS1rw+c2dVLiIFAL1vES4qrXqMz2uJ222fc3GNUupHq/eFxERkew45/h+4WYe/3oRm3ancEX7Wtx/dmPKlyzqdzSRiKGeFyH+wsE4jKSxuvZFREQkO+u2H+D6oTO5ZdgcypUoysh/nsyzF7VQ4SJSyNTzIlSpeRLTK11Am+QxbFy9hOp1G/sdSUREJCgcSkvnncmreO3nFcREGY+c34R+neoQE63zvyJ+0P88AaDuhYPJIIqksU/4HUVERCQo/LZiG+e88isvTljGGQlV+HFAN27oXFeFi4iP1PMiAFSuUZfplXvRdutXbFi1mBr1EvyOJCIi4oute1N4atxixs7bSJ2KJfjw+vZ0bVjJ71gignpeJJN6Fz5COtFsUO+LiIhEoPQMx4e/r6H7vyczfsFm7uregO/vPlWFi0gQUc+L/KVS9XimVe5N4taRJK1YQM36zfyOJCIiUijmrd/FoNEL+HPDbro0iOOJXs2oG1fS71gikkWee17MLNrM5prZuPwIJP6qf+EjpBHNpq/1zWMiEh7UTsnR7D6YyqDRf9L7jd/YsieF165szUfXt1fhIhKk8qPn5S5gMVAmH5YlPourXodpVS4iccuX6n0RkXChdkr+H+cco//YwNPfLGbH/sNce3I8/c9sSOnYIn5HE5GjyFPPi5nVBM4D3sufOBIM6l80iFRi2PS1rn0RkdCmdkqys2LrXq54dxr3fD6PmuVLMPb2zjzas6kKF5EQkNeel5eB+4HSOc1gZjcDNwPUrl07j6uTwhBXtTbTql5Mu82fsX75PGo1aOl3JBGRE/UyaqfEc/BwOq/+tJx3f11FiaIxPHNhcy5vV4uoKPM7mojk0gn3vJjZ+cBW59zso83nnHvHOZfonEusVEnf1hEq6l84kMMUYYuufRGREKV2SjL7cfEWznxpMm9MWskFLWvw44CuXNmhtgoXkRCTl56XU4ALzOxcIBYoY2bDnHNX50808VNc1Vp/9b6sW/YHtRu28juSiMjxUjslbNh1kMfHLuSHRVtoULkUn9/ckQ71KvodS0RO0An3vDjnHnLO1XTOxQOXAz+pQQgvDS4axCGKsnWcel9EJPSonYpsqekZvDV5JWe8OJlfl2/jwXMa8+1dXVS4iIQ4/c6L5KhilZpMq3YJ7Td9ytolc6jTuI3fkURERI5p+qrtPDJmAcu27OPMJlV4tGcTapYv4XcsEckHef6dFwDn3CTn3Pn5sSwJLg0vGkgKRUn+5im/o4iInDC1U5Fh+75DDPhiHpe9M439h9J575pE3r0mUYWLSBhRz4scVYXKNZha/TI6bPyYtYtnUyehrd+RRERE/kdGhmP4zHW8MH4pBw6ncWu3k7jj9AYULxrtdzQRyWf50vMi4a3xRQ+TQlG2fatrX0REJLgs2LCbi978nYGjFpBQrTTf3dWF+3s0VuEiEqbU8yLHVL5SNabWuIwOGz5mzeJZxCck+h1JREQi3N6UVIZMWMaHv6+hQsmivHRZS3q3qoGZvvpYJJypeJFcSbhoIAde/ZI9Yx7ANZqARanTTkRECp9zjnHzN/HkuEUk7zvE1R3qcO9ZjShboojf0USkEOgTqORKubiqLEy4ixYps5j19Vt+xxERkQi0ett+rvnvDO4YPpcqZWIZfespPNm7mQoXkQii4kVyrd2l97OkSBMazH2a7VuS/I4jIiIRIiU1nZcmLOPsl3/hj3W7ePyCpoy+7RRa1irndzQRKWQqXiTXoqKjKX7x65RwKawZdoffcUREJAJMXpbM2S//wis/LuecZlX58d6u9Ds5nugoXdsiEolUvMhxqdO4DbPjb6Tt3p/4Y+Jwv+OIiEiY2rw7hds+mUO//84g2oxPbuzAK5e3pnLpWL+jiYiPdMG+HLe2Vz7O6ue/o/qUh9mTeBZlylX0O5KIiISJtPQMPpy6liE/LCUtwzHgzIbc3LUexWL01cciop4XOQFFi8WSev5/qOh2svjj/n7HERGRMDF77U56vvYbT45bRPu6FZhwT1fu6N5AhYuI/EU9L3JCGrbpxrTpl9Fxy2csmvodTTqd43ckEREJUbsOHOb58UsYPmM91crG8tbVbTi7aVX9ZouI/D8qXuSEtej7Ahtf/JnSP/QnpdWpxBYv6XckEREJIc45RsxO4tnvlrD7YCo3danL3Wc0pGQxfTwRkexp2JicsBKlyrL9tH9Ry21k7scP+R1HRERCyNLNe+nz9lTuGzGfenEl+ebOzgw8r4kKFxE5Kr1DSJ40P7UXM+ecQ7sNH7Ny/uWc1OJkvyOJiEgQ238ojVd+XM77U1ZTJjaGFy5uwSVtaxKlrz4WkVxQ8SJ51rDvK+x6tT1uzO2kJUwjpkhRvyOJiEiQcc7x/cItPPH1QjbuTuHydrV4oEdjypdUmyEiuadhY5JnZStWYW37x6ifvpJZnz3ldxwREQky63cc4IYPZ3HLsNmUKV6Ekf/sxHMXt1DhIiLHTT0vki/a9OjH3AVf0GrFGySt6EPN+s38jiQiIj47lJbOu7+s4tWfVhATZQw6L4FrT44nJlrnTkXkxOjdQ/KFRUVR46o3SCWG3V/cisvI8DuSiIj46PcV2zjnlV/59w/L6J5QmYkDunJjl3oqXEQkT/QOIvmmco26LGp2H00Pz2PmqFf8jiMiIj7YujeFuz+by5XvTSct3fHBde1446q2VCtb3O9oIhIGNGxM8lW7i+5m4fJRNP7zBZI7XUil6vF+RxIRkUKQnuH4ZPpa/vX9Ug6lZnBn9wbc2u0kYotE+x1NRMKIel4kX0VFR1Omz5sUdakkfXKb33FERKQQzE/axYVv/MbgMQtpWbMc4+/uQv8zG6pwEZF8p+JF8l2t+s3546R/0nr/FOaMH+p3HBERKSC7D6YyeMwCer3+G5t3p/DqFa35+Ib21KtUyu9oIhKmVLxIgUi84hFWRJ9E7WmPsntHst9xREQkHznnGD13A91fnMywaWvp1ymeiQO60rNldcz0Y5MiUnBUvEiBiClSFOv1GuXcHpZ+dKffcUREJJ+s2LqPq96bzt2f/0GN8sUZe3tnHrugKWVii/gdTUQigC7YlwJzUouTmTrtajpt/IgFv46hWZdefkcSEZETdPBwOq/9vJx3fllF8SLRPH1hMy5vV5voKPW0iEjhUfEiBar11c+y/l8TKf/TfRxsczrFS5b2O5KIiBynn5ZsYfCYhSTtPMhFbWrw8LkJxJUq5ncsEYlAGjYmBSq2RCn2njWEGm4L8z66z+84IiJyHDbsOsjNH83i+qGziC0SzWc3d2RIn1YqXETEN+p5kQLXpNM5TJ/Vi3abP2PZnCto2Kar35FEROQoUtMz+O+U1bw8cTkOxwM9GnND57oUjdE5TxHxl4oXKRQJfV9i+8u/EjPuTlKbzaBIUZ21ExEJRjNW72DQ6D9ZtmUfZyRU4bELmlCzfAm/Y4mIABo2JoWkTLmKbDzlaeplrGHWp4/6HUdERLLYvu8Q9345jz5vT2X/oXTevSaR9/olqnARkaCinhcpNK3OvJLZ8z6n7ep3Wbv0cuo0auV3JBGRiJeR4fh81nqe+24J+w+l8c9uJ3HH6fUpUVQfEUQk+KjnRQpVnatf46AV48CIW8lIT/c7johIRFu4cTcXv/U7D331J42rlua7u7rwQI/GKlxEJGipeJFCFVe1FstaPUxC6kJmjvi333FERCLSvkNpPPH1Inq+OoV12w/w4qUt+ezmjjSooq+zF5HgplMrUugSL7iV+Uu+otmiIWxefzFVa9X3O5KISERwzvHtn5t5YtxCtu49xJXta3P/2Y0pW6KI39FERHJFPS9S6CwqirjL38RwbPn0VlxGht+RRETC3ppt++n3wUxu+3QOcaWK8dU/T+bpC5urcBGRkHLCxYuZ1TKzn81skZktNLO78jOYhLfq8Y2Y3+gOWh6czuxv3/M7joiEIbVTASmp6bw8cRlnvfwLc9bu5NGeTRhz2ym0rl3e72giIsctL8PG0oABzrk5ZlYamG1mE5xzi/Ipm4S5dn0eYulzX3PSrCfZ2aEn5StV8zuSiISXiG+nfl2ezCOjF7Bm+wF6tqzOI+clULlMrN+xRERO2An3vDjnNjnn5nj39wKLgRr5FUzCX3RMDEUvep2Sbj8rP77D7zgiEmYiuZ3asieF2z6dQ9/3Z2BmfHxDe169orUKFxEJeflywb6ZxQOtgenZTLsZuBmgdu3a+bE6CSN1m7Rjau3r6LT+Peb/PIIWp13idyQRCUOR0k6lpWfw4dS1vDRhGYfTM+h/ZkNuPrUesUWi/Y4mIpIvzDmXtwWYlQImA08757462ryJiYlu1qxZeVqfhJ9DKQfY/EJ7imWkUKr/TEqV0ThskYJkZrOdc4l+5ygskdJOzVm3k0GjFrBo0x66NqzEE72aUqdiSb9jiYgct6O1U3n6tjEzKwKMBD45VoMgkpNisSU4eM7LVHbbWPjxvX7HEZEwEgnt1K4Dh3noqz+5+M3f2bH/MG9e1Yah17VT4SIiYemEh42ZmQHvA4udc0PyL5JEosbtzmD6jItpt3UkS2ZeQeN2Z/gdSURCXLi3U845RsxO4tnvlrD7YCo3nFKXu89sSKli+gk3EQlfeel5OQXoC5xuZn94t3PzKZdEoGbXvMhWi6P4d3dzKOWA33FEJPSFbTu1bMteLnt7GveNmE98xRKMu6Mzg85vosJFRMLeCb/LOeemAJaPWSTClSxdjpVdn6PF5BuY+skjdLrhRb8jiUgIC8d26sDhNF75cTnv/7qaUrExPH9xcy5tW4uoqLDaTBGRHOkUjQSVFqddwqy5n5G47gNWL+xD3aYd/I4kIuI75xw/LNrC42MXsnF3Cn0Sa/LgOQlUKFnU72giIoUqTxfsixSEk/q+yj4rSeqo20lPS/M7joiIr9bvOMCNH87iHx/PpkzxIoy4pRMvXNJShYuIRCQVLxJ0yleqxsrER2iYtoyZnz/jdxwREV8cTsvg9Z9XcOZLk5m6ajsDz03g6zs6kxhfwe9oIiK+0bAxCUptz72ReQtH0GLZa2xc3YfqdRv7HUlEpND8vnIbj4xewMrk/fRoWpXBPZtQvVxxv2OJiPhOPS8SlCwqiipXvkEGUWz/7BZcRobfkUREClzy3kPc8/kfXPnudA6nZ/DBte14q29bFS4iIh4VLxK0qtaqz8Im99D80Fxmjnnd7zgiIgUmPcPx8dQ1nP7iJMbN38gdp9dnwj1dOa1xZb+jiYgEFRUvEtTaXXIvi4s0pdG8Z9m2eb3fcURE8t2fSbu56I3feGTMQprXKMv4u09lwFmNiC0S7Xc0EZGgo+JFglpUdDQlLnmD4u4Q64bd5nccEZF8s/tgKoPHLOCC16ewcXcKr1zeik9u7MBJlUr5HU1EJGjpgn0JenUatWJq3ZvotOZNZn3zLm16XE9UtM5Iikhocs4xdt5Gnhy3mB37D3FNxzoMOLsRZWKL+B1NRCToqXiRkJB45eOsfH48iTPvZd+MR1hftB57yiVg1VtS8aREajVqQ9FisX7HFBE5qhVb9zF4zAJ+X7mdFjXL8sG17Whes6zfsUREQoaKFwkJRYoWo8It3zHjl89wm+ZTdvcSmm/9mhLJI2AeHHbRrIypw/bSjcmo0pwyddtQK6E9pcvq9xBExH8pqem89tMK3v5lJbFFonmyV1Ou7FCH6CjzO5qISEhR8SIho3ylarS/+J6/HqenpbFu1QK2Lp9JatJ8Su5cSP1dU6iw61tYCoyHJKvG1pINORzXjOJ1WlMjoQNxVWv7txEiEnF+XrKVwWMXsH7HQS5sXYOHz02gUulifscSEQlJKl4kZEXHxFC7YStqN2z113MuI4Otm9ayccl0Dq6bS7FtC6m6fwnV902GNcBk2EY5NsY2YH+FJhSt2ZoqDdtRvW6CrqMRkXy1cddBnvh6EeMXbqZ+5VIMv6kjnU6q6HcsEZGQpuJFwopFRVG5Rl0q16gLXP7X87t3biNp8Qz2rplN9JY/qbh3KQkbhlFk44cwA/a54v9zHU2Fem2p3bitrqMRkeOWmp7B0N/W8NLEZWQ4x31nN+KmLvUoGqMv+BQRySsVLxIRypaPo+zJ58LJ5/71XMrB/axZOoedK2fl4jqaZpSp25bq9VsRU7QYUVFRREVFY1FRmEX9/dgMi9IHFJFINWvNDgaNXsCSzXs5I6Eyj/ZsSq0KJfyOJSISNlS8SMSKLV6SBq26QKsufz13zOtocindGRlE4TAcRsZf/0aRYQZ/PRf11zSXaR4wMuzIc95y7Mh9iXSbT+pDx6sG+x1Dsnhs7EKG/r6GGuWK807ftpzVtKrfkUREwo6KF5FMjnYdzaal0zm4aRm4dHAO55x3PwOc824ZmMvAuQzAedMyMG/akefsyGsyz/PXfReYjvc6vMcuAyPDl/0iwSWmdGW/I0g2alcowT+61uOu7g0oUVTNq4hIQdC7q8gx/O91NCIi2bu+s94jREQKmgbni4iIiIhISFDxIiIiIiIiIUHFi4iIiIiIhAQVLyIiIiIiEhJUvIiIiIiISEhQ8SIiIiIiIiFBxYuIiIiIiIQEFS8iIiIiIhISzDlXeCszSwbW5mERccC2fIoTqiJ9H0T69oP2QaRvP+R9H9RxzlXKrzDhJB/aqWCj/y9Hp/2TM+2bo9P+OboCa6cKtXjJKzOb5ZxL9DuHnyJ9H0T69oP2QaRvP2gfSO7pWDk67Z+cad8cnfbP0RXk/tGwMRERERERCQkqXkREREREJCSEWvHyjt8BgkCk74NI337QPoj07QftA8k9HStHp/2TM+2bo9P+OboC2z8hdc2LiIiIiIhErlDreRERERERkQil4kVEREREREJCUBYvZtbDzJaa2QozezCb6cXM7HNv+nQzi/chZoHJxfb3N7NFZjbfzH40szp+5CxIx9oHmea72MycmYXV1xXmZvvNrI93HCw0s08LO2NBy8X/g9pm9rOZzfX+L5zrR86CYmb/NbOtZrYgh+lmZv/x9s98M2tT2BkleJlZLe//x5H3iLv8zhRszCzae/8Y53eWYGNm5cxshJktMbPFZtbJ70zBxMzu8f5fLTCz4WYW63cmP2XXXplZBTObYGbLvX/L59f6gq54MbNo4HXgHKAJcIWZNcky2w3ATudcfeAl4PnCTVlwcrn9c4FE51wLYATwQuGmLFi53AeYWWngLmB64SYsWLnZfjNrADwEnOKcawrcXdg5C1Iuj4FBwBfOudbA5cAbhZuywA0Fehxl+jlAA+92M/BmIWSS0JEGDHDONQE6Ardl9z4a4e4CFvsdIki9Aox3zjUGWqL99BczqwHcSeBzWDMgmkAbFMmG8v/bqweBH51zDYAfvcf5IuiKF6A9sMI5t8o5dxj4DOiVZZ5ewIfe/RFAdzOzQsxYkI65/c65n51zB7yH04CahZyxoOXmGAB4kkDhmlKY4QpBbrb/JuB159xOAOfc1kLOWNBysw8cUMa7XxbYWIj5Cpxz7hdgx1Fm6QV85AKmAeXMrFrhpJNg55zb5Jyb493fS+DDZw1/UwUPM6sJnAe853eWYGNmZYFTgfcBnHOHnXO7fA0VfGKA4mYWA5QgzNqf45VDe5X5s/qHQO/8Wl8wFi81gPWZHifx/99w/5rHOZcG7AYqFkq6gpeb7c/sBuC7Ak1U+I65D7whMrWcc98UZrBCkptjoCHQ0Mx+M7NpZna0M/ShKDf74DHgajNLAr4F7iicaEHjeN8rJEJ5Q6tbE2a91Hn0MnA/kOFzjmBUF0gGPvCG1b1nZiX9DhUsnHMbgH8D64BNwG7n3A/+pgpKVZxzm7z7m4Eq+bXgYCxeJJfM7GogEfiX31kKk5lFAUOAAX5n8VEMgeFC3YArgHfNrJyfgXxwBTDUOVcTOBf42Ds2RMRjZqWAkcDdzrk9fucJBmZ2PrDVOTfb7yxBKgZoA7zpDcvdTz4O+Ql13rUbvQgUedWBkt7nMcmBC/wuS779NkswNvQbgFqZHtf0nst2Hq/LriywvVDSFbzcbD9mdgYwELjAOXeokLIVlmPtg9JAM2CSma0hMJ57bBhdtJ+bYyAJGOucS3XOrQaWEShmwkVu9sENwBcAzrmpQCwQVyjpgkOu3iskcplZEQKFyyfOua/8zhNETgEu8NqPz4DTzWyYv5GCShKQ5Jw70lM3gkAxIwFnAKudc8nOuVTgK+BknzMFoy1HhjJ7/+bb8PZgLF5mAg3MrK6ZFSVwEdTYLPOMBfp59y8BfnLh82ubx9x+M2sNvE2gcAm3ax3gGPvAObfbORfnnIt3zsUTuO7nAufcLH/i5rvc/B8YTaDXBTOLIzCMbFUhZixoudkH64DuAGaWQKB4SS7UlP4aC1zjfetYRwJDFzYd60USGbzrQN8HFjvnhvidJ5g45x5yztX02o/LCXyG0Jlzj3NuM7DezBp5T3UHFvkYKdisAzqaWQnv/1l39IUG2cn8Wb0fMCa/FhyTXwvKL865NDO7HfiewDc4/Nc5t9DMngBmOefGEnhD/tjMVhC4QChsvuUhl9v/L6AU8KX3PQXrnHMX+BY6n+VyH4StXG7/98BZZrYISAfuc86FS+9jbvfBAALD5e4h0B19bRidxMDMhhMoUOO863oeBYoAOOfeInCdz7nACuAAcJ0/SSVInQL0Bf40sz+85x52zn3rXyQJIXcAn3gnj1ah95e/OOemm9kIYA6Bb/WbC7zjbyp/5dBePQd8YWY3AGuBPvm2vjBq60VEREREJIwF47AxERERERGR/0fFi4iIiIiIhAQVLyIiIiIiEhJUvIiIiIiISEhQ8SIiIiIiIiFBxYtIFma2xvvtlDzNIyIi4jcz62Zm47z715rZa35nEskLFS8iIiIiIhISVLxIRDOz0WY228wWmtnNWabFm9kSM/vEzBab2QgzK5FpljvMbI6Z/Wlmjb3XtDezqWY218x+z/QLxSIiInnmtU2Lzexdr+36wcyKm9kkM0v05okzszU+RxUpECpeJNJd75xrCyQCd5pZxSzTGwFvOOcSgD3ArZmmbXPOtQHeBO71nlsCdHHOtQYGA88UaHoREYlEDYDXnXNNgV3Axf7GESk8Kl4k0t1pZvOAaUAtAg1CZuudc79594cBnTNN+8r7dzYQ790vC3xpZguAl4CmBRFaREQi2mrn3B/e/cxtkEjYU/EiEcvMugFnAJ2ccy2BuUBsltncUR4f8v5NB2K8+08CPzvnmgE9s1meiIhIXh3KdP9IG5TG35/r1PZI2FLxIpGsLLDTOXfAu2alYzbz1DazTt79K4EpuVjmBu/+tfmSUkRE5NjWAG29+5f4mEOkQKl4kUg2Hogxs8XAcwSGjmW1FLjNm6c8getbjuYF4Fkzm8vfvTEiIiIF7d/AP732R1/lL2HLnMs6KkZEIPCNLsA4bwiYiIiIiPhMPS8iIiIiIhIS1PMiIiIiIiIhQT0vIiIiIiISElS8iIiIiIhISFDxIiIiIiIiIUHFi4iIiIiIhAQVLyIiIiIiEhL+D1ie4SDoqMONAAAAAElFTkSuQmCC\n", "text/plain": ["<Figure size 1008x288 with 2 Axes>"]}, "metadata": {"needs_background": "light"}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "\n", "N = 100\n", "obs = []\n", "for alpha in tqdm([0., 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.]):\n", "    total_null = 0\n", "    total_cnx = 0\n", "    for i in range(0, N):\n", "        mat = random_symmetric_adjacency_matrix(10, alpha=alpha)\n", "        cnx = len(set(connex_components(mat)))\n", "        w, v = numpy.linalg.eig(mat)\n", "        nb_null = sum(numpy.abs(w) < 1e-7)\n", "        total_null += nb_null\n", "        total_cnx += cnx\n", "    obs.append(dict(alpha=alpha, null=total_null / N, cnx=total_cnx / N))\n", "\n", "df = pandas.DataFrame(obs)\n", "fig, ax = plt.subplots(1, 2, figsize=(14, 4))\n", "df.plot(\n", "    x=\"alpha\", y=[\"null\", \"cnx\"], ax=ax[0],\n", "    title='nombre de valeurs propres nulles\\net nombre de composantes connexes')\n", "df.plot(\n", "    x=\"null\", y=[\"cnx\"], ax=ax[1],\n", "    title='x=valeurs propres nulles\\ny=composantes connexes');"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le nombre de composantes connexes semble \u00e9gal au nombre de valeurs propres nulles de la matrice d'adjacence dans laquelle le coefficient sur la diagonale est le degr\u00e9 du noeud."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q4 : construire un algorithme qui retourne les composantes connexes d'un graphe\n", "\n", "On construit un dictionnaire qui accumule les \u00e9l\u00e9ments dans des listes associ\u00e9s \u00e0 chaque num\u00e9ro de composante connexe."]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["{0: [0, 1, 2, 3, 6, 7, 8, 9], 4: [4], 5: [5]}"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["def connex_components_indices(mat):\n", "    cnx = connex_components(mat)\n", "    res = {}\n", "    for i, c in enumerate(cnx):\n", "        if c not in res:\n", "            res[c] = []\n", "        res[c].append(i)\n", "    return res\n", "\n", "mat = random_symmetric_adjacency_matrix(10, alpha=0.3)\n", "connex_components_indices(mat)"]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": []}], "metadata": {"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.10.5"}}, "nbformat": 4, "nbformat_minor": 2}