{"cells": [{"cell_type": "markdown", "id": "69e1b7d3", "metadata": {}, "source": ["# Algo - graphes al\u00e9atoires\n", "\n", "Comment g\u00e9n\u00e9rer un graphe al\u00e9atoire... G\u00e9n\u00e9rer une s\u00e9quence de nombres al\u00e9atoires ind\u00e9pendants est un probl\u00e8me connu et plut\u00f4t bien r\u00e9solu. G\u00e9n\u00e9rer une structure al\u00e9atoire comme une graphe est aussi facile. En revanche, g\u00e9n\u00e9rer un graphe al\u00e9atoire v\u00e9rifiant une propri\u00e9t\u00e9 - la distribution des degr\u00e9s - n'est pas aussi simple qu'anticip\u00e9."]}, {"cell_type": "code", "execution_count": 1, "id": "72d61704", "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "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, "id": "2078981b", "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "markdown", "id": "c1b0c638", "metadata": {}, "source": ["## Graphe al\u00e9atoire - matrice d'adjacence al\u00e9atoire\n", "\n", "L'existence de chaque arc est d\u00e9fini par une variable binomiale de param\u00e8tre $p$."]}, {"cell_type": "code", "execution_count": 3, "id": "d076b8b7", "metadata": {}, "outputs": [{"data": {"text/plain": ["array([[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n", " [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0],\n", " [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],\n", " [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],\n", " [0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n", " [0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]])"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["import numpy\n", "\n", "mat = numpy.random.random((15, 15))\n", "mat = mat + mat.T\n", "adja = (mat >= 1.4).astype(int)\n", "for i in range(adja.shape[0]):\n", " adja[i ,i] = 0\n", "adja"]}, {"cell_type": "markdown", "id": "0f9d2c1a", "metadata": {}, "source": ["En le visualisant..."]}, {"cell_type": "code", "execution_count": 4, "id": "f448c29a", "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAO0AAADnCAYAAADy1tHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAgFklEQVR4nO3deXhTdboH8O/J1rRN9w3owlbbAmWzIJUdQRBcEEUBqQqMAlNG1OfOiMPiXHH0cUG9zFwBcRm8gAgXBh0dLoIKZRGcYZG1BQpCWuiWtkna0uzn/lETmiYnS7P1R9/P8/QBkpOTUz3fs/7e93A8z/MghDBDFOoFIIR4h0JLCGMotIQwhkJLCGMotIQwhkJLCGMkoV4AQvxN1ajH9uPlKKnUQqszIVouQU6XaDyWl4YERVioF89nHN2nJbeLU2VqfLC/FEUXawAAepPF9p5cIgIPYGx2EgrHZGJgemxoFtIPKLTktrDp6FW8vqsEOpMZrtZojgPkEjGWTclBQX6PoC2fP9HhMWFeS2CL0Wy0uJ2W54Fmoxmv7yoGACaDSxeiCNNOlanx+q4SjwLbWrPRgtd3leB0uTowCxZAtKclTPtgfyl0JrPD66qvV0F39RQsRh3EkXGIzn8UUQMn2U2jM5mxZn8p1hUMCdbi+gWFljBL1ahH0cUap+ew0fmPIWHy8+AkUhhry1D5+R8hS+mNsC6Ztml4Hth3oQa1jXqmrirT4TFh1vbj5YLvyZK6g5NIf/0XBw4cTPUVDtNxALafEJ5PR0R7WsKskkqt3W2dtmq/XYOmM9+DN+khS+mN8N6Oh8E6kwUlFQ2BXEy/o9ASZml1JpfvJ0wqRPy9C6C/XgKd8gw4sdTpdFqdMRCLFzB0eEyYFS13v8/hRGLI0/vB3KBCw8ldAvNxHuaOikJLmJXTJRphEg9XYYvF6TmtXCJCTtcoPy9ZYFFoCbOm56U5fd3cpEbT+SJYDM3gLWY0XzmOpuIiyHsMcpiWBzD9Tufz6ajonJYwK1ERhjFZSdhbXGV/24fj0HDy/1D77RqAt0ASk4y48c8i4o5hdp/nOGBcdhJTt3sAGntMGHeqTI2ZHx1Fs9FxgIU74VIxts7Px4C0WP8vWADR4TFh2sD0WDw3KhW8Se/V58KlIiybksNcYAEKLWGcwWDAlpWFyJddR7hUDI5zPT3Htexhl03pw2SxAECHx4Rxv/3tb3H9+nV8+eWXOHtDizX7S7HvQg04tAycsLLW047LTkLh2Ewm97BWFFrCrPXr1+P999/HTz/9hOjoaNvrtY16bD9RjpKKBmh1RkTLpcjpGoXpd1LnCkICwpN2MYcPH8a0adNw6NAhZGVlhXiJg4tCSzoMT9vFTO8TjTkPjcNHH32EKVOmhGhpQ4dCSzoEj9vFAODNBoyKrMbGPy0I2vJ1JHT1mITcrXYxrgMLtIxggliGY+YMbDp6NQhL1/FQaElIdcZ2Mb6iYYwkpITaxQBA0/kiqA9vgVlbA3FkHBLufwHy9Fzb+6y2i/EVhZaEjKt2Mc2/nET9/g1ImroEsm5ZMDfWOUzDarsYX9HhMQkZV+1iNIc2I2bELISl5oDjRJBEJUISlegwHYvtYnxFe1oSMkLtYniLGfqKUoRnDsP1dc+CNxsQcUc+YsfNg0hqv0dlsV2Mr2hPS0JGqF2MuUkNWEy4eeEwUgreQte5f4Gh6go0P24VmA9b7WJ8RaElISPULob7dW8alfcgJIp4iCNiEDX0YTRfPiYwH7baxfiKQktCRqhdjFiugLjN+SsnUL7DYrsYX1FoScgItYsBAEX/CWg4/g3MTWqYdY3Q/vtLRGQOdZiOxXYxvqILUSRkBNvFAIgZMRPmZi2ur18ATiJFZM4oxAyfYTcNq+1ifEVjj0lIdcZ2Mb6iw2MSUgPTY7FsSg4k8G4YI8vtYnxFoSUhl6S5AN2RzxEm4TpFuxhf0eFxEHlS3N3ZlJSUYPTo0di5cyeiuvfrFO1ifEWhDQJPi7sLx2RiYHpsaBYyBOrr6zFs2DC8/PLLmDdvnu31271djK8otAHmcXE3B8glYiybkuPXw76Ounc3mUyYPHky+vfvj/feey9ky8EiCm0A3Sru9vwiS8sFFt/P1zr63n3x4sW4dOkSvv76a0gkdOfRGxTaALHeyqg6+iWaznwPQ81VRPYZg8QHXnSYVn1oCzSHNiN55p8R3mOQz7cyQr13d2f9+vV47733cPToUcTGxgbte28XdPU4QKzF3RJFAmKGz4BiwL1OpzPWV+DmhUMQK+Jtr1mLu9vDq9YtPNBsNOP1XcVBa91SVFSEFStW4Ouvv6bAthMdlwRA6+LuiOzhAAB9ZSnMRpXDtHV71iJu7BzUfrvW9lp7i7uFWreY1FWo3bMGhuslgESKyOwRiJswH5xIDOBW65YBabEBvSp75coVzJgxA5s3b8Ydd9wRsO+53dGeNgBcFXe31lRyCJxYivDejmNq21PcLdS6pXbPGogjYpH23EZ0m/tX6MrOouHEP+2m8WXv7gmtVouHHnoIy5cvx4QJEwL2PZ0BhTYAhIq7W7Pob0Jd9BniJ8x3+r7OZMGxSzfQ1NTk0Xe6at1i0lQhss9IcBIZxIo4hPfMg1GltJum9d7d38xmMwoKCjBy5EgsWrTI7/PvbOjwOACEirtbUx/6HJH97oEkNkVwmr37DyPxdxMhFouRnJyMlJQUpKSkOP17UbUMQiex0UOmoun8AYRl9IdF14jmK8cQO6rAYTrr3n3B6N4e/66e3FJavnw5tFotduzYIVhiRzxHoQ0AoeLu1nTXTsHcUIuGky2HqZabWqi+fBPR+dMRkz8dADDtgfvw3v8sQWNjI6qqqlBVVYXq6mrb34uLi7F//35UVVXhesYEWDKcdyWUp+ei8efdKHvvcYC3IDJ3PMKz7nZcJi9at7i+pVSJ97+7iLHZSejZfAnbtm3DTz/9BKm0cxWrBwqFNgBairsroTdZwFvMgPWHt4A3GQCRGCmzXgfMt84/Kz57EXHjn0F4rzwAt4q7OY5DVFQUoqKikJmZKfid8z77N34oqXZ4nectqNr2CqIG3YcuT66CxdiM2n+uhnr/3xA3bp7D9J60bnF3S8k6/HDPuSpYjGFYtGoTEhMdm7KR9qFz2gBoXdytOfwFlKsegfbodjSd2wflqkegOfwFxOHRECvibD/gRBDJFRDJwgF4X9wttHe3NDfArK1B1J0PgJNIIQ6PhmLAhHa3bvH2aQCcNAx/O6nutE8DCATa0wZA6+Lu2FGzETtqttvPpBV+avt7e4q7W+/dWxNHxEASk4KGk7sQPewR8IZmNJ75HtLkng7zcNe6xXpLqeroV04HjBhUStR+8x5M9RUAAFmXTMTduwBIzAjKLaXOgva0AbJobCbkEnG7PiuXiFE4VvhQ2BlXrVuSHlmG5ivHUb76CVz/cD44sQTx459xmM7d3t3dgBGJIh5JD/8RaS98gbTnP0f4HcOg+uptAIG/pdSZ0J42QKzF3e0be+x9cber1i2ylF7oMvtN1zOwWMDfOI/zJxUYNWqUw9ueDBgRyRUQyRUAWi5kc5zIttftrE8DCATa0wZQQX4PLJvSB+FScVCKu33Zu4eHSfCbu9NRUFCARx55BBcvXrR739MBIwCgfH8GlO9MQ93eDxF992O21zvj0wACgUIbYAX5PbB1fj4m9U1BmEQEeZuWobzJADEHdImWo1+3aBy7Vo91RZfbNcjBuncPl3r3v9VaWbTkmZkoKSnBsGHDMHz4cCxevBgqVcue1JMBI1YZL25F+ovbED9xIWQpt+75dsanAQQCVfkEUevi7vL6myhXN6OivgkSkQgm3NoV+1o6548qn5qaGrz66qvYsmULpk2bhktdx+OaKdpumvoDG2HWqpxWLgEtt5vKV89Gt2fXQhzZ8juMz0nGJ087DtsknqNz2iBKUIRhweje2HT0Knafq2wZJywSo+34Kdt9zvNVOHBR5XXpXEF+DwxIi/W4dUv/1BhUVFTg3LlzDj8ikQhfffUVJKMSEZbteK7rEs+DN+lhbqi1hfZ8hRanytSdqkOHv9GeNsiCXRjftnWLDGZEmTVIbLiMX0rO2MIJALm5uejXr5/dT1JSEgDgpb/txbbiJkAstQ0YUR/6HOaGWiRMfg4QiaG7dhri8GhIk3uAN+qhPrARNy8cRurCj8FJZC0LxFsgk4iw4v5+ePJu738fQqENKmc9fpXvTrebhjcZEDV4CuInLrR73dvC+NraWoe95tmzZ2GWRCBt9HREpt6B8Oh4JMdFIa93V8wdk4PEKLng/FSNegx/83sYzDzUBzdDc3iL3fsxI2ZBmtQd6gObYG5QgZPIENYtC7FjnobMyT1hmAwYFVWDN39zP1JTUz36nUgLCm0Qzd94zOktGSuLoRnlf30SyY/9J+QZuXbvcRwwqW+Kw1PP1Wq103DevHnTbo8Zmd4Hh+oV+EnZciHIm/YzPM9j8+bN+OOuKxBnDAY4+wtd2uNfC3bnaL76M+r2rINZWwNZtywk3v8iJDHJAAARb4L2769iaO8UzJkzB1OnToVcLrzhYJW/+3S1O7QdtWFYR6Vq1GPEWz+4vALbeOZ7aA59jm4LP3ZaDSMVAc91r8LVkrO2cGo0GvTt29cuoLm5uUhLS7PNw5cLU1euXMHChQtRXV2NJW+twcrDWoenAdy88CPAcWj+5QR4o8EWWvNNDa5/+CwSJi9GROZdUB/YBF35OXR96l3b943PTsQ4SSk2bNiAEydO4PHHH8ecOXNw1113+VQR1BHWz0D16fI6tB29YVhHta7oMt7/7qLL0FZ+vhTy9H7Cwx7NRvRsPIf7ukts4czIyIBIJHyLp73n0C9PykLV4R14++23sWTJErzwwguQSqUu59f2anLDz7vRdOY7dHlyFQDAYtCh/C9PoOvc1ZAmpAMAwiQi/LjkHiQowqBUKrFx40Zs2LABEokEc+bMQUFBgVeHzx1l/Qxkny6vrh57XN3RzquetzN39zlNmmroy84iYcpi4ZmIpRg05n4smTHIo+8Uaj/jTrPRgj99eRoZl07jX//6F3r16mV7z/r/s2W+rp+/Y6y5ZjfGWSSTQxLbBYYapS20rWt4MzIysGzZMixduhQ//vgjNmzYgNzcXOTn53t0+NxR1k9vNpSt+3QB8Gh5PA5toBekvTrCYZAnVBrXHSgaz/6AsLS+kMZ2cTldWZUKTU1NiIyMdPudQu1nrIx113Hjk98hMmcEEh/8vd17nESKPtNfsAuslfWW0oJNx1Gh0QnO32LUQRwRY/eaKCwSvKHZ9m9nAy44jsOIESMwYsQIrF69Gjt37sTHH3+MwsJCwcPnjrJ+Cm0oKze/DP2NC7a+XOKoBKTO/9D2vjd9ujwKrdCCuLoA4e2CeMvTIuxQHKarVCocP34cx44dw7Fjx3D8+HGYhs6GLGuk4Geazv5gK3535ed/H0HikgeRmJiInJwcZGdn2/1pPZd11X7Gqm7POoR1dd5gjQeH/U7GCut0Oly9ehVlly8jXNcEQHjjIZLKYdHftHvNYrgJ7tfyQ6uKWjWMRqPTIvmIiAjMnj0bs2fPth0+FxQU2B0+qyyRDusnbzKids8a6K7+DIuuEZLYLogb8zTCe9+6kBeI9dPVhjJ+4kJEDZwk+FlrUUXbi41teRRaoQWxVntYL0D4siDe6CiHQQBQV1dnC6j1z/r6euTl5SEvLw8zZ87EqlWrsLecx/vfXXJ6iKwrL4a5sRYROcKhBlrOyV589gk8s2EplEolSkpKcOHCBZw7dw47duzAhQsXoNVqkZWVBcXQaTDFD4LQSNWm80UQySMhTciBSV3hdBqz2YyFb38GRdkRXLlyBZcvX4ZKpUJGRgZ69+4NXd+HAZlwaKVJ3dF05nvbvy0GHUz1lZAlZdhNd/TAPihenIS0tDRkZmY6/PTs2RNyuVzw8Dl15qvQxfYCWo0q4y1mSKIS0eWJNyGOSULz5WOo+eotdJv333Ytfvy5fnqyoXTF06IKt6F1tSDu2oN6syCeCuVhUH19PU6cOGEXUJVKhcGDB2PIkCF49NFH8cYbbyAzM9Ph4lBMih7vf3fJ6Xybzn6PiKzhEIVFuP590FI6JxaL0bNnT/Ts2ROTJ0+2m0aj0eDixYt47fsyKDXOA2vR34T64GakzHoDjae+Ffw+E8+hxijFfSNH4qmnnkLv3r2RmpoKsbjlEM96cU1nMDrtzhGRdTfq932KppLDiMgcCs3hLZAm97CdzwK/bogKn8Lc/1mGq1evorS01Pazd+9elJaW4tq1a+jSpYtDmBcvXozfL38V9394Ajxvf6VZJJPbXdCLyLwLkpgU6CtL7ULrz/XTXVGFev9nUO//DNL4VMSOfhLy7gMcpvGkT5fb0HpT3SGkPQ3DnPHlwoq3h0EajQYnTpywO8ytqqrCoEGDMGTIEEydOhUrV65EVlaWy6u3Vq5K5xLu+53bz3taGB8TE4OhQ4ci8TwAjWP7GQBQH9gIxcCJkES7bwHTOycXvxEYKzw9Lw3vf3cRmsNf2A22aDq3DzEjZiF21GwkTVuKuj3rUPvNu5B1zULSQy/ZzcO6IZLJZMjKykJWVpbD95hMJiiVSly+fNkW6EOHDqG0tBSVcf2huHvGrRFXAsxN9TDWXXfYywMt6+fmHy/jiTuTYTAYoNfrYTAY7P7u7LW27+/WpEBvinf8cgBx4+ZCmpAOTixFU/EBVO94DV3n/gXSuK5203lSVOE2tN5UdwjxV3WHs8N0o6oMtXvWwlBVCnF4DOLGzbUdAdgvg/BhUENDg0NAb9y4gYEDB2LIkCGYMmUKXnnlFWRnZ9v2Mu2xaGwmDl5Steup594Wxgu1nzFUXYHu2il0nbvaw/kIt5+xbYjMwt05wnsMQur8dU7f83RDJJFI0KtXL/Tq1Qv33mtfeP/8Fyfx1akbLj/Pm01Q/WMVFP3H2+3lrXQmC95Y+xlePfAxwsLCIJPJIJPJbH/39LWbsmTBZQjrlm37u6L/eDSdL0Lz5WOQDnnQYVp3fbrchtaTdqCe2PnP3Tix5nl0794dGRkZtj+tP+6uhjo7TOctZlTveA1RgycjZeZr0CnPombHSnRN6g5pvP29PethkLKqDspL5+0uEimVSgwYMABDhgzBxIkTsXTpUuTk5Pj9wVDBLIwXaj+jU56BSVOF8jVzAQC8QQfwFlSonncIsrv2M0BwN0TONOhdr588b4Hqm3cBsQTx9y4UnO7+h6fjk51v+bQsL2w9iS9/dr0BseE4tBxnOHLXp8vtWulJO1BPTBgzAk/0vAvXrl2DUqnEkSNHsHXrViiVSiiVSigUCrsgtw33zhLHPbWxtgzmxjpEDX0YHMchvMdAhKX2RdPZHxA7+kmH6fU6HQY/WohM4y/Iy8vDPffcg5deegl9+vQJWnvP1vc5A/mALOuha1uKQZMQ2We07d/af/0dJk0V4ic5NhH3pLlcsDt0tOVq/eR5HrW7/gJzkxrJj/0nOLHwtO6C4gmhDaVF1wj9jQuQZ/QHRGI0FR+Avuys00b1nmwo3SZSaEEACLYHtd6Lar0gQ+/ohnsEzmktFgtqampsgVYqlbh27RoOHjxoe008ch7C+4xxt7gAeBhqrgn8tjIU/O4lrJ55pwfzCRxvS+fas2ILnUOLpHJAemuAAieVtzx5oM39VG+aywVrQ+SMq/Wz7tsPYKwtQ8rMP0MkFf49PAmKJ4Q2lLzFDPWBTTDWlQOcCNKENCQ9stzhaBDwbEPpdhijqzGzQtUebc9vWg9Va6+nPzmCotI6u9d4swk31i+AYvBkRA99GDrlaVT/70rIu/dHyozXnM6noxVhB/Kp586qijzVnsdtni5XB3RD5IzQ+mnSVOP62nmAWGq3E4m/bxEU/cbZTeuP9dPKXVGIK0JFIW253dO6uurpSXvQ9rQDdSZO4Th8jRNLkPToctTt/RDaozsg65qJyD4jAbHwoY4/DoP8yVoYHwjBPnQdkBaLdQVDArohakto/ZTEJKP7y9+4nwFvwehM39dPq2Cc43t0whrqiw2A8GGQLLmnXafByo2/R2TueIFl8c9hEEtCcegayA2RM76snyLegkPrV+Bs3rvIzc11/wE3grGh9KgDmG8Nw3y/2AC0nC84W98M1b+ANxlgMeqg+envMDXWQ9Hf+aMUve3af7tw11xOLhEhTCLCpL4p2Do/n7kiD1/Wz1cfHoiX5z+BcePGYc2aNfBHeXmgu3B6VZoXyHIjd4qKijDvb0dh7tLXrgi7/odP0XjqW/AWM8LS+yH+3gWQxnVzukyenC/c7oJ56BpsvqyfFy9exKxZs5Ceno5PPvkECQkJgp/3tEglUOf4XtfTBvtiQ2VlJf7whz+gqKgIL/75v/BhaTh0Xo6IAtp3YYWwx5f1U6/XY9myZdi2bRs2btyIMWPs71a0t1bX3xvKdneu8GRBfCmbM5lMWLt2LVauXIl58+ZhxYoVUCgUQW+MRtjkS1B2796NefPm4ZlnnsErr7wCiUQS0qNMh+8IRI8oX7sHHDlyBIWFhYiNjcUHH3yAvn372r3fkf4DkttTZWUlnn76aTQ2NuLxZX/FuqNVHWZH4ffQ+hIolUqFJUuWYPfu3XjnnXcwa9YswT5BobgnSDoXi8WCJW+vwTZVN3AuBmcICdQpmV8H17a3bM7C82g+vQcrVqzA7NmzUVxcjOjoaJefD8U9QdK5iEQiaFLzIdJUOdy5MDc3oHbXauiunoQoPBpxY55GZL+xdtMEopYc8GNo3T27VH+9BOqDm2CoLAU4EeQZ/RF37wI0K+Lxys6fkXx6L/bu3YuBAwd69b3BvidIOg9bkYqT9+r2rAUnliLtuU0wVF1B9fZXIU3uCVlSd9s0gXpSoN8ewOXu2aUWXSMUg+5D6m8/RWrhp+Bk4aj953+1vCmWYvDsl70OLCGBJFRLbjHocPPCj4gdXQCRLBzy9H6IyByGpnP7HKYNxJMC/RLats8ujci6G6Jw+8Pb8N5DEJkzEqKwCIikckTlPQD99eJf3+Ww/2JNu54UR0igCNWSm+qugxOJ7Qb8S5N7wuikUCUQTwr0S2jb091CX3YO0sRbXQTo2aWkoxGqJbcYm8GF2TenE4VFwNKqy6T9fFwXtXvLL6H1truFofoXaA5vQdy4ubbX6NmlpKMRqtUVScPB6+0DyutvQtSmy+St+fi3SMUvofWmu4Wx/gaqt/0JcRPmQ55uP0Db31skQnzRUqTiGBFJfCp4ixnGuuu21wzVv0Da6iKUVSCKVPwSWk+7W5g01ajashwxI2ZCkXuPk/l0rLI50rlNz3NeXCKSyRGRfTfUBzfDYtBBV34eN0t/QmSbOl0gMEUqfglt6y0SbzG3dLBo1c2Ct5hhalChastSROU9gKjBUxzm0RnL5kjHZq3VdTa+J35iIXiTAeV/nQ3VP95BwsRCu9s9gP9qydvyy4io1t0DhLpZgOOgOfQ5OKl9MXvGf2wH4N/uAYT4S7C7f3jCb8MYg9Fmg5BQ6GhFKn4bXLFobCbkkvb1BPZXdwtCAiHQRe3e8mvBQEfbIhHiTx2lSKVDVfkQwoJQF6kEpJ62o2yRCLkdBSS0VqHeIhFyOwpoaAkh/ue3q8eEkOCg0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyh0BLCGAotIYyRhHoBCPGVqlGP7cfLUVKphVZnQrRcgpwu0XgsLw0JirBQL57fcTzP86FeCELa41SZGh/sL0XRxRoAgN5ksb0nl4jAAxibnYTCMZkYmB4bmoUMAAotYdKmo1fx+q4S6ExmuFqDOQ6QS8RYNiUHBfk9grZ8gUSHx4Q5LYEtRrPR4nZangeajWa8vqsYAG6L4NKeljDlVJkaMz86iqqjX6LpzPcw1FxFZJ8xSHzgRQAAbzZC9Y93oK8ohVlbjZRZb0DefQAAIFwqxtb5+RiQFhvC38B3dPWYMOWD/aXQmcyQKBIQM3wGFAPudZgmLK0fEh/8D4gj4+xe15nMWLO/NFiLGjB0eEyYoWrUo+hiDXgeiMgeDgDQV5bCbFTZpuHEUkQPndryD5H9PonngX0XalDbqGf6qjLtaQkzth8v93keHIDtJ3yfTyhRaAkzSiq1drd12kNnsqCkosFPSxQaFFrCDK3O5Kf5GP0yn1Ch0BJmRMv9cwkmWi71y3xChUJLmJHTJRphkpZVlreYwZsMgMUM8BbwJgN4i7nlPZOx5T0AvMXU8t6vdzblEhFyukaF5hfwE7pPS5ihatRjxFs/QG+yQH1wMzSHt9i9HzNiFmJHzUb5mnkwa6vt3ktd+AkksSkIk4jw45J7mL56TKElTJm/8Rj2Fle5HLoohOOASX1TsK5giP8XLIjo8JgwZdHYTMgl4nZ9Vi4Ro3Bspp+XKPgotIQpA9NjsWxKDsKl3q264VIRlk3JYX4II0AjogiDrIP+O2uVD53TEmadLldjzf5S7LtQAw4tAyesrPW047KTUDg287bYw1pRaAnzahv12H6iHCUVDdDqjIiWS5HTNQrT76TOFYSQDoAuRBHCGAotIYyh0BLCGAotIYyh0BLCGAotIYz5f1vLJrG+DmLCAAAAAElFTkSuQmCC\n", "text/plain": ["
"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import networkx\n", "import matplotlib.pyplot as plt\n", "fix, ax = plt.subplots(1, 1,figsize=(4,4))\n", "G = networkx.from_numpy_matrix(adja) \n", "networkx.draw(G, with_labels=True, ax=ax) "]}, {"cell_type": "code", "execution_count": 5, "id": "b256dd97", "metadata": {}, "outputs": [{"data": {"text/plain": ["array([1, 1, 4, 1, 3, 1, 2, 4, 2, 3, 4, 0, 1, 5, 2])"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["degres = adja.sum(axis=1)\n", "degres"]}, {"cell_type": "code", "execution_count": 6, "id": "50cdcd35", "metadata": {}, "outputs": [{"data": {"text/plain": ["{1: 5, 4: 3, 3: 2, 2: 3, 0: 1, 5: 1}"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["distrib = {}\n", "for d in degres:\n", " if d in distrib:\n", " distrib[d] += 1\n", " else:\n", " distrib[d] = 1\n", "distrib"]}, {"cell_type": "markdown", "id": "4d008768", "metadata": {}, "source": ["## Vocabulaire li\u00e9 aux graphes\n", "\n", "* **arc (ou edge en anglais)** : lien liant deux noeuds, il peut \u00eatre **orient\u00e9** ou non, s'il est orient\u00e9, les deux extr\u00e9mit\u00e9s ne jouent pas le m\u00eame r\u00f4le, l'arc ne peut \u00eatre \"parcouru\" que de la premi\u00e8re extr\u00e9mit\u00e9 vers la seconde.\n", "* **noeud (vertex en anglais)** : \u00e9l\u00e9ment du graphe\n", "* **graphe** : un graphe est d\u00e9fini par un ensemble de noeuds et un ensemble d'arcs\n", "* **matrice d'adjacence** : matrice binaire de dimension $N \\times N$, $A=(a_{ij})_{ij}$ et $a_{ij} = 1$ s'il existe un arc reliant le noeud *i* \u00e0 *j*, 0 sinon.\n", "* **chemin** : s\u00e9quence de noeuds et d'arcs appartenant au graphe\n", "* **pr\u00e9d\u00e9cesseur et successeur** : si un arc orient\u00e9 relie les noeuds *i* \u00e0 *j*, *i* est le pr\u00e9decesseur de *j*, *j* est le successeur de *i*. Par extension, si *i* appara\u00eet toujours avec *j* dans tous les chemins possibles du graphes, *i* est un pr\u00e9decesseur de *j*.\n", "* **arbre** : cas particulier des graphes orient\u00e9s, il existe un unique pr\u00e9decesseur \u00e0 tous les noeuds nomm\u00e9s la racine, un noeud sans successeur est appel\u00e9 **feuille (ou leaf en anglais)**. Dans un arbre binaire, chaque noeud n'a que deux successeurs directs.\n", "* **degr\u00e9 d'un noeud** : nombre d'arcs connect\u00e9s \u00e0 un noeud, on peut distinguer pour les graphes orient\u00e9s le fait que les arcs partent ou arrivent \u00e0 un noeud\n", "* **Composante connexe** : au sein d'une composante connexe, il existe toujours un chemin reliant n'importe quelle paire de noeuds.\n", "\n", "Quelques propri\u00e9t\u00e9s de la matrice d'adjacence :\n", "\n", "* Pour un graphe non orient\u00e9, la matrice d'adjacence est sym\u00e9trique.\n", "* La somme sur la ligne *i* est \u00e9gale au degr\u00e9 du noeud *i*.\n", "* La matrice d'adjacence est triangulaire sup\u00e9rieue dans le cas d'un arbre dont les noeuds sont num\u00e9rot\u00e9s en largeur d'abord (un noeud a toujours un num\u00e9ro sup\u00e9rieur \u00e0 tous des niveaux moins profonds)."]}, {"cell_type": "markdown", "id": "a1527b71", "metadata": {}, "source": ["## Apart\u00e9 : matrice d'adjacence \u00e0 la puissance n\n", "\n", "Si $A$ est une matrice d'adjacence, $a^2_{ik}$ et un coefficient de cette matrice. $a^2_{ik} \\sum_j a_{ij} a_{jk}$. Comme $a_{pq} \\in \\{0, 1\\}$, $a^2_{ik} > 0$ s'il existe un $j$ tel que $ a_{ij} = a_{jk} = 1$. Autrement dit, les noeuds $i j, k$ sont reli\u00e9s. Si $a^2_{ik} > 0$, alors il existe un chemin de longueur 2 entre les noeuds $i, k$. Par r\u00e9current, $A^3_{pq}$ est positif s'il existe un chemin de longueur 3 reliant les noeuds $p, q$."]}, {"cell_type": "markdown", "id": "d3a9f780", "metadata": {}, "source": ["On calcule $\\sum{A}=A + A^2 + A^3 + ... + A^n$ o\u00f9 n est la dimension de la matrice."]}, {"cell_type": "code", "execution_count": 7, "id": "cb764aad", "metadata": {}, "outputs": [{"data": {"text/plain": ["array([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],\n", " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]])"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["adjan = adja.copy()\n", "conne = numpy.zeros(adja.shape)\n", "for i in range(1, adja.shape[0]):\n", " conne += adjan\n", " adjan = adjan @ adja\n", "(conne > 0).astype(int)"]}, {"cell_type": "markdown", "id": "d068e893", "metadata": {}, "source": ["D'apr\u00e8s les remarques pr\u00e9c\u00e9dentes, $\\sum A_{pq} > 0$ s'il existe un chemin reliant les noeuds $p, q$, donc s'il font partie de la m\u00eame composante connexe. Et 0 si les deux noeuds font partie de deux composantes connexes distinctes."]}, {"cell_type": "markdown", "id": "426ca456", "metadata": {}, "source": ["## Trouver le nombre de composantes connexes\n", "\n", "On s'inspire d'un algorithme de coloriage. Au d\u00e9but, chaque noeud appartient \u00e0 sa propre composante connexe not\u00e9 $c_i$. Pour chaque arc reliant deux noeuds *i* et *j*, on associe aux deux noeuds \u00e0 la composante $\\min(c_i, c_j)$. On continue tant qu'un noeud change de composante connexe."]}, {"cell_type": "code", "execution_count": 8, "id": "664bb7e8", "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAO0AAADnCAYAAADy1tHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAfJUlEQVR4nO3deXxU9b3/8deZJZksZA8QSBB+RgigIJsNm2xWW9zoT3pFwa0XI8XeH7X28aMV6+1Gq71XarUs1ev93SrIjxavWJVWQAmgwr0VMGwJGGRJkKxkT2Y95/4RZ8hk1iQzkxn4PP8y55z5zgny5pzzXT5H0TRNQwgRM3T9fQJCiJ6R0AoRYyS0QsQYCa0QMUZCK0SMkdAKEWMMvf1gXauFrQcrKatqptlsJ8VkoGBwCt+elEtmcnwoz1EI0YXS03HakopG1haXs+dULQAWu+raZzLo0IDZo7JZPiuf8XlpoTxXIQQ9DO3GA2dZvb0Ms92Bv08pCpgMelbNL2BJ4fAQnKYQwino2+POwJbSYVMDHqtp0GFzsHp7KYAEV4gQCqojqqSikdXby4IKbFcdNpXV28s4UtnYm3MTQngR1JV2bXE5ZrvDY7u9sZr6HeuwXigDg5GkUdNJv6UIRad3HWO2O1hXXM6GJZNDd9ZCXMUCXmnrWi3sOVXr9Rm2fsc69Ilp5P7T6wx55CXMFcdoOfSe2zGaBrtP1lLfagnZSQtxNQsY2q0HK33uszdVkzR6BoohDn1yOgkjJmGrO+9xnAJsPeS7HSFE8AKGtqyq2W1Yp6uUyXfTdmIvqs2MvaWOji8+JWHERI/jzHaVsostfT9bIUTgZ9pms93nPlPe9bR+9jcq1vwDaCpJ188jYeRUH+3Yen+WQgiXgFfaFJP3XGuaSvWfniFx1DSGPfkmuSveQDW30lj8/3y0Y+zbmQohgCBCWzA4hXiD52FqRwuO5loGTLwDxWBEn5BC8rhb6Dj9qcexJoOOgpwBoTljIa5yAUO7cFKu1+36xFQMqYNoObwdTXWgmltpPfoBxoEjPI7VgIUTvbcjhOiZgKHNSo5n1shsFMVzX/b/XkXHFwep/N39XPhDEYreQMa8pW7HKArMGZUtiwiECJGg5h6XVDSy6JUDdNg8J1gEkmDUs6WokHG5ab05PyFEN0FNYxyfl8aq+QUkGHu2/DbBqGPV/AIJrBAhFPSCAeekf1nlI0T/6vF62iOVjawrLmf3yVoUOidOODnX084Zlc3y2flyhRUiDHocWqf6VgtbD1VSdrGFZrONFJORgpwBLJwolSuECKdeh1YI0T+ksJsQMUZCK0SMkdAKEWMktELEmF7XPRZCBCfUNcKl91iIMAlXjXAJrRBhEM4a4XJ7LESIhbtGuHRECRFCkagRLldaIULIW41wzW6jfsc6zGc/QzW3YkgbTPqsh0i41r0WeLA1wuVKK0SI+KoRrqkODAOyGHz/s+Q9sYW0mx+g9u3nsDdWux8XZI1wCa0QIeKrRrguzkTazMUY0gahKDoS82/CkDoIS1W5x7HB1AiX0AoRIv5qhHflaGvAdukCcdnDPPYFUyNcQitEiPirEe6kOezU/eVfSb5hHsbMPB/t+K8RLqEVIkR81Qh30jSVunefB72BjK8v89OO/xrhElohQsRXjXAATdOo3/4ijrZGsr/1FIree8CDqREuoRUiRHzVCAe49P5abPUVDFz4DDqj7/nGwdQIl3FaIULEWSN8Z2m127CPvamG1s/+BnojlS894Nqe8Y3HSR47x/VzsDXCZe6xECEUiRrhcnssRAhFoka43B4LEWLhrhEut8dChEm4aoRLaIUIs1DXCJfQChFjpCNKiBgjoRUixkhohYgxElohYoyEVogYI6EVIsZIaIWIMRJaIWKMhFaIGCOhFSLGSGiFiDESWiFijIRWiBgjoRUixkhohYgxElohYoyEVogYI6EVIsZIaIWIMRJaIWKMhFaIGCOhFSLGSGiFiDESWiFijIRWiBgjoRUixkhohYgxElohYoyEVogYI6EVIsZIaIWIMRJaIWKMob9PQMSOulYLWw9WUlbVTLPZTorJQMHgFL49qXdvNBe9I2+CFwGVVDSytricPadqAbDYVdc+k0GHBswelc3yWfmMz0vrn5O8ikhohV8bD5xl9fYyzHYH/v6mKAqYDHpWzS9gSeHwiJ3f1Uhuj4VPnYEtpcOmBjxW06DD5mD19lIACW4YyZVWeFVS0chtRU/R8NlOrLVnSRo9i6w7ngBAc9io+8u/YLlYjqO5hkH3/QrTNeNcn00w6tlSVMi43LR+Ovsrm/QeC6/WFpejJqaTOu1eksd93WN/fO5Ysu58En1Susc+s93BuuLySJzmVUluj4WHulYLe07VkjhyGgCWqnIctjrXfkVvJGXK3Z0/6Dz/3dc02H2ylvpWi/Qqh4FcaYWHrQcr+9yGAmw91Pd2hCcJrfBQVtXsNqzTG2a7StnFlhCdkehKQis8NJvtIWrHFpJ2hDsJrfCQYgpNV0eKyRiSdoQ7Ca3wUDA4hXiDDk11oNmtoDpAU9HsVjTVAYBmt3XuAzTV3rmvy+ihyaCjIGdAv5z/lU7GaYWHulYL05/7kOrdr9P08Wa3fanT7yNt5mIq130HR3ON276hy17FkDYIgHiDjk9WzpXe4zCQ0Aqvil7/lJ2l1X6nLvqiKHDbmEFsWDI59Ccm5PZYePf47HxMBn2vPmsy6Fk+Oz/EZyScJLTCq/F5aayaX4BR17NLbYJRx6r5BTKFMYwktMKn20el0vHxJuL0nbe8/ihK55zjVfNHy2KBMJNnWuHT0qVLMZlMFP3ol6wrLmf3yVoUOidOODnX084Zlc3y2flyhY0ACa3wavfu3Tz00EMcO3aMlJQUAOpbLWw9VEnZxRaazTZSTEYKcgawcKJUrogkCa3w0NHRwbhx41izZg133nlnf5+O6EZCG+XCVZfJX7vP/+pnnD59mi1btoTwNxGhIqGNUuGqyxSoXYeq0vHFQV5buZi5N14bkt9FhJaENgqFqy5TsO2CRoLRIPWeopSENsr0pC6TU+fYqP+hlnC1KyJPQhtFSioaWfTKATpsDrfttroK6nesx1pdjj4hlfQ5j5A4aprbMf7qMvlq19X+pQt8+er3SCqYTtadPwy6XdE/pNxMP+reGVR6sckjWJrqoObNXzBgwjcZtOgXmM8fo/bNn5OTfQ3GjKGu45x1mbzN911bXI7Z7j2wAJd2bCA+5zqv+/y1K/qHhLYf+OsM6s5WX4Gj9RIDpixAURQSho8nfugY2o59SNrND7iO81WXyVnvydf9VNuJPehMSRgzC7A3XvTYL/Weoo9MY4ywjQfOsuiVA+wsrcZiV3tZ1kXDWnvOY6u3ukz+6j2plnYa920ife5Sv98m9Z6ii4Q2gi53BgXqvb3MmJGLPjGV5v96E81hp+PMIcznj6HZLR7HeqvL5K/eU+Pe10kefyuGlCy/5yD1nqKL3B5HSElFI6u3l1F94G3ajn7gUQDcWnee+nfXYG/ovEWNG5xP+tcfIy5rGNn3PM2lnX+g+cCbxOXkkzR6Bui9l3LpXpfJV70na/UXmM+VkPPI74I6f6n3FD0ktBHi7AwyJGeSOu1eOs4cQrNZXfsNyRlkL/gx+tSBoKm0HHqPurd/w5B//D1xA0cwePGzrmOrXv8hSdfP8/o93esy+ar3ZD5/FHtTNZXrHgFAs5pBU7lYt8JrkKXeU/SQ0EZA184g51BN9wLgOlMyOlMy0Nn5oyg611XXWnMGY8ZQNE2l5dB27K0NJN9wi8f3eKvL1FnvqcrjFjn5xttIGn2z6+fm//5P7E3VZNz2eFDtiv4joY2AnhT/Pv/be9GsHaBppM5cDEDbsd20lryPpjqIzxvLoEW/QDF4Xvk0YOHEXLdtCyfl8ttdpzyO1RlNYDS5flaMJhRDHPrE1KDaFf1HQhsBPSn+PeyJLahWM23HPkCfMhCA9LnfIX3ud/x+TlE617R2H5bJSo5n1sjsgPWe0r76ByLYdkX/kd7jCOhp8W9dnInkCd+k/t01ONoag/qMv7pMUu/pyiKhjYBeFf/WNDS7BUdLfcBDA9VlGp+XxlPfLEBRe9YDLPWeopOENgKcxb8BnwXAO84cxlp1Gk11oFraafjg39CZkjFm5flstyd1mRo/fYekU+9jMuqk3lOMkwUDEeAs/m2xqzTu2+S1ALgx+xoa927E0VKHYogjfshI0mY9RNzAER7txekVFEUJui7TkSNHmDdvHvv376fdlCX1nmKchDZC+lL8G2BIqonROSkc2Leb+VPH8aN75wTVOdTe3s6UKVNYuXIlDz74oGu71HuKXdJ7HCGPz85n3+d1PpfH+ZNg1LNhySTG5abxSPE6RmkZQQfrySef5MYbb+SBBx5w256ZHM9jN0tlilgkz7QR4iz+nWDs2R95986gESNGcObMmaA++9Zbb7Fjxw7Wr1+PEuhBVsQMCW0ELSkczqr5o0kw6gN2BqGpGFA9OoOCDW1lZSXLli1j06ZNrhKo4sogoY2wJYXD2VJUyG1jBhFv0GEyuP8vMBl0xBt0zByRSvNbP+OmDKvb/mBC63A4WLJkCStWrKCwsDDkv4PoX9IR1Y8CdQa98MILbNu2jQ8//BCdrjPcFy5cYNKkSVRVVflsd/Xq1ezatYtdu3ah1/duUoWIXhLaKOZwOJg6dSpFRUUsXdq5UF1VVZKSkqivrycxMdHjM/v372fBggUcPHiQ3FyZL3wlktBGuSNHjnDLLbdQUlJCTk4Oda0WvrZoBTfftQglPsmtyLjBYWbChAmsWbOGBQsW9PepizCR0MaAp59+moNn6sj7xlL2nKrFarWg6S6v8nFOikhqOsso9Rybf/+s78ZEzJOOqBhw7TcepnTIbew80bkutmtgoXNWk8Wucikhl8MZs9h44Gz/nKiICJlcEeU2HjjLb3Z8DoY4At4S6XSYbSqrt5cCyLzhK5TcHkcxb0XGzz+/0O0YzW5lwIT5ZNy6zG27FBm/csmVNop5KzI+7Mmtrv9WrR1UvvQAiQUzPD4rRcavXPJMG6UCFRkHaD/5CfrEVOLzxnrs61pkXFxZJLRRKpi6Uq1HPyDp+rk+5xVLkfErk4Q2SgWqK2VvqsFScYykG7yXUgUpMn6lktBGqUB1pVqPfUh87hiMaYMDtCNFxq80EtooFaiuVNuxD0m+fm4Q7UiR8SuNhDZKda0r1Z25shRHa73XXuOupMj4lUlCG6UWTvI92b/t2AckjpyGLt5zwUBXUmT8yiTjtFHKX5HxzG98L+Dnpcj4lUuutFFMiowLbyS0UcxZVype37P6TlJk/MomoY1y903JI+7EuxgUVYqMC0BCG/XWr19Pet0xti6b4bOulEHRiDfouG3MILYUFUpgr3CyyieKVVRUMHHiRPbt20dBQQHgWVfqXHkZJnM9f/zn70qn01VCQhulNE3j7rvvZvLkyTzzzDM+j9u3bx8/+MEP+Pvf/x7BsxP9SYZ8otTWrVs5ffo0W7du9XvclClTKC0tpbW1leTk5AidnehP8kwbhRoaGlixYgUvv/wycXFxfo81mUxMmDCB/fv3R+jsRH+T0EahlStXsmDBAqZPnx7U8TNnzmTfvn1hPisRLeT2OMrs2bOHv/71rxw7dizoz8ycOZPf/OY3YTwrEU2kIyqKmM1mxo8fz3PPPdejusVNTU0MHTqUS5cuBbydFrFPbo+jyK9+9SvGjh3b40LjqampXHfddRw8eDA8JyaiitweR4njx4+zfv16SkpKevV553Pt1KlTQ3xmItrI7XGE1LVa2HqwkrKqZprNdrfXeaQnGpkxYwYPPvggy5YtC9yYF3/+85957bXXeOedd0J85iLaSGjDrKSikbXF5ew5VQvgVvfJ+TqPYYYWmvb/mQPbt7jejtdTVVVVjBkzhrq6ul63IWKD/N8No40HzrLolQPsLK3G8tWrO7pyvs7jVHsCTZMf4Y3/Pt/r7xo8eDCZmZkcP368r6ctopyENkw2HjjL6u2ldNgcfmsXAyg6HRaHxurtpX16D4+M114dpCMqDEoqGlm9vYzqA2/TdvQDrLVnSRo9i6w7nnAd03H2My7t2ICjuZa4ISPJuv0JOlIHsnp7GeNy01xrYf09C3dfIDBz5kx27tzJ8uXLI/nrigiTZ9owKHr9U3aWVtNW9gkoCh1nDqHZrK7QOtqbuPCHR8n85v8hMf8mGvduxFx5nJwHn0dR4LYxg/jurPyAz8KzR2WzfFY+4/PSAPj888+ZO3cu58+f91nAXMQ+uT0Osa6v80gcNY3EkVPRJaS4HdN+aj9xWcNIKpiBYogjdcb92GrOYKuvQNNgV2kN9768P+Cz8I4T1Sx65YDrljo/Px+bzca5c+ci9euKfiChDbFgXudhqz2HceAI18+6OBOGtMFYazs7ouyqhtmuBnwW1jTosDlcz8KKoshz7VVAnmlDLNDrPABUmxl9YqrbNl18Epq1w+dn2k7sofHjzTiaa9EnpZN5+/cx5V0PQIdNdT0LT5o2m9f+/iUH4w4HfAYWsUlCG2KBXucBoDOaUC3tbttUaztKXILX4zvOHKah+D/IvnslcUNG4mi95HGM2eZg6Wuf0tA2HFu8lc8/+9K1z2So4re7Tnk8A4vYJLfHIRbodR4AxuxrsNWccf2sWs3YG6qIyx7m9fimjzaROv0+4ocWoCg6DAOyMAzIcjtGA2paLNhUwOC+aMDXM7CITRLaEOv6Og9NdaDZraA6QFPR7FY01UHiyKlY687RVvYxmt1K08ebMQ4cjjEzz6M9TXVguViO2t7EhQ2PUrn2IS7tWI9q6/l7Z7s/A4vYJEM+IVbXamH6cx9isas07ttE08eb3fanTr+PtJmLu4zT1hCX0zlOa0gb5NGevaWeC2sfIm5wPtkLn0HR6al985fED7uB9FkPej2H5oPv+Bwfdkow6tlSVCi1kWOQhDYMil7/lJ0nqgnFH6zD3ErlC4vIvP0Jkr96F21b2cc0fbKFId950etn2k96Hx/uyjkevGHJ5BCcpYgk6YgKUk9mJt0/PoOdRytB3/fXTOpNyei7Pb8GmjiROGoaAJaqchy2Oq/HaBrsPllLfatFepVjjIQ2AP+rdDx7ZY8ePcojd9/FlPt+wFFDPh02/8M/wUi+4RZaDr5Lwv+aBHoDzX/fRmL+lD63qwBbD1Xy2M3X9rktETkSWj86J/2XYbZ7n/Rv/irAO05Us/dUHXcNc/DvP36YF154gcWLFwf8vJOiQLxeh82h4vByXOr0RTg6mrnw8mMoBiNJBTNJnXZvn38/s12l7GJLn9sRkSXPtD5cXqUT/JVSs1v4xwnpPHP/HNe2I5WNrCsuZ/fJWmw2K6py+d9J5xziOaOyWT47n9/vLvf6asveatj7Oo7mOq/PtE7zCgby6kN9v2qLyJErrReBVulYLpTRuG8j1qpyUHSYht1A+tcfw5CcweYyCwsqG129suNy09iwZDL1rRZuefRpRhXOJSktixSTkYKcASycePmZ+PHZ+ez7vI4OmyNiv2uKqe/P3SKyJLRerC0ux2x3YEjOJHXava5eWCfV3Eryjd8gYcRE0Om4tGMD9e+9wKB7f47Z7mBdcblHr2xmcjyVu/6D955/giFDhnj9XuerLXt6he9OUx2dY8NdxofR6VF07u+6NRl0FOQM6PX3iP4hoe2m+yod8OyFTbjWPZADJt1B9Rs/Bnz3ytbU1GC328nJyfH7/c433gXzLOxL08f/3218uO34btf4cFcasHBibs+/QPQrCW03wazS6c5ScRxj1uUpiN56ZU+cOMHYsWODWue6pHA443LTXM/CCpc7veDys3BqgpGaFs+ZUWkzF3sE1IOmMm14us/hnp4McYnIktB2E8wqna6sNWdo+ngz2fc87drmrVf2+PHjjBkzJuh2uz4Ld321Zddn4cqGDha9cqBXz8B6NHa88CTvDX6a22+/3bW9p0NcIvIktN0Es0rHydbwJTV/+mfSbylyLZO73I7N7efjx48zduzYHp9PZnK8z3HUzOT4Xj0DJxh1rJo/lrxvPsvDDz/M22+/zZo1a9h2rK5HQ1yr5hfIC6z7gSwY6CaYVToA9qYaqjc/Ter0RSRfP9dLO+69sr0NbSBLCoezav5oFIcNAkycVJTOOcer5o9mSeFwZs2aRUlJCXa7nRu+tZyfv3M8qEJ0svCgf8mVtpvOVTpVWOyqz15YR1sD1ZufYsCkOxgwYb5HG917ZTVNC1toAQa1fI6u+EXmfe859nxe5/MZ2Dke3HWRQEpKCit+toZ9Gz7C6uViXffOv2I+W9K5cD8pnZTCexgw/jbAffG9LDyIHJlc0U0wq3RQFJo+egPFaHLbN+zJzhdAxxt0fLJyrqvDpqamhoKCAurr60NecE1VVSZPnsxTTz3FwoUL/T4D++pAchai8/Y3wVp7DmP6EBSDEVt9BVVv/JiB3/4p8YPzAVl40B/kSttNVnI8s0Zms7O02m8vbNqM+71uV5TOK1rXgDg7ocJRIXHz5s3ExcVxzz33AP6fgb3pOsTlTVz2NV1+UlBQsDdcdIVWFh5EnoTWi77MTDIZ9Cyfne82ZHKkrBbHTUvYsOd0SIdMzGYzq1at4rXXXuv1PwjBDHHVv7+OtqMfoNktxA261mOcWhYeRJbcHvvQm7nHOs1O0ayRfFHX1qN6xb31/PPPs3fvXt5+++1et/H9LYfZ1qWelC+a6sByoQzz+aOkFi5E0bv/e/+tG4fy23tv7PV5iODJldaHnsxMcq3SOXOUf9unw4Eu7EMmDQ0NPPfccxQXF/fq807BDnEpOj2mvLG0Hd9Ny+HtpEy+q1s7Nh+fFKEmofUj2JlJc0ZlMyIriX/XNCze1tZ103XIxPk9PfXrX/+aBQsW9GjChjfBDnG5qCr2hote2pGFB5EioQ0g2JlJtxU9RcNnO/3WZWr8aDNNH21i4KJfkjD8xl4PmZw/f55XX32Vo0eP9vn36zrE1Z2jrRHzuRIS8m9CMcRhPvsZbaV7yLrr/7odJwsPIktCGyR/vbI/fusoamK61xVBTraGi7Sf/Ah9cobbdl+rgvz5yU9+wvLly32uFuqJhZNy+e2uU953Kgoth/9K/fvrQFMxpA4kfd6jJF73NbfDZOFBZElo+8g5ZJI40n9dpks71pM++2Hq31/vtt3XkImvCftjTE28//77nDrlI2g91HWIq/tzuD4xlcGLn/X7eW9DXCK8JLR9FMyQSVvZRyh6IwnXTgHWe+zvOmQSaMK+xWrl+u++yJkmlfEpHk31SiiGuETkyNzjPgq0Kki1tNO4549k3FLk8xjnqqBg3hyv6QyctiSF9E0BzsX3Ccae/XXoXHhQIFMYI0yutH0UaMik8aM3SBo712sh8q5OXGzib8cvBjUuHIre5+56OsRlMuhllU8/kdD2UaAhE/O5Ehwt9bQcfg8Atb2Zum3PklK4kNTCha7jymtaPSoxVm36EZYvT7rKxOgHZDK06A+u/aGesN+TIa7uCw9E5Eho+8g5ZGK22ryuCBp032pwXH5WvPjHJ0ift7SzhvFXFDQcmvdpiBm3LnOtqvGmN73P/gQzxCWdTv1LQttHziGTYOsyoejQmZLRdXmtpabR2RvVC+GasN/ThQcicmTucQj4W9oWDJ0CqpfPVm36Eba6zrfDGzOGknbzA5iuGedxnMmg44mvj5SQXSXkShsCfRky0St4fasAQPqcRzBm5qHojbSV7qXmzV+Q88iLGNPdKzrKmwKuLjLkEwJ9GTK5dmCyz/3xQ0ahi09EMRhJvmEe8UNH03H6U6/HyoT9q4eENkSctZoSjHoCLW3tWqtpTE4PZkgoCr7qQMmE/auH3B6HUG+GTFotDq8T9lVzK5YvT2IadgPo9LSV7sVScczrJA2ZsH91kY6oMOk6ZNLQZuavf/lPfrriUf5hyjCPOcbOmlRdOdqbqPnTT7FdqgRFhzEzl7SZS0gYMcHju7rXpBJXNglthIwcOZJt27Z5Xf/al95nKax29ZFn2ggZN24cR44c8brv8dn5mAx6r/sCkQn7Vx8JbYT4C+34vDRW3nodODzX4fojE/avTtIRFSEjRo/j9+99yve3HPb6QqvPtr7E0AYT9dfM6iyULhP2hQ/yTBtmzvWxxSdrsFgsKIY41z5nb/LIZBtH//Q8h3dto6JNkQn7wi8JbRh1lmENvNRNU1XijTqeuWOs68opE/aFLxLaMOlN3eTOZ9TRcssr/JLQhkFJRaPX98Y6Olqo3/47zGcPo0tIIX3WQySNne12TIJRz5aiQrn1FT5J73EYrC0ux2z3XDxwacd6FL2R3H/aSNadP6R+xzqstefcjnGujxXCFwltiPl6oZVqNdN+8hPSbl6CLi4BU95YEvO/Rtvx3W7HdV0fK4Q3EtoQ81Wd0X7pAopOjzFjqGubceAIbN2utHC5OqMQ3khoQ8xXdUbV1oESn+C2TRefiGrt8DhW1scKfyS0IearOqPOmIBmcQ+oZml3Kzvj3o6sjxXeSWhDzFd1RkPGUDTVge3SBdc2a80ZjG4vbe7ajqyPFd5JaEOsszqj5x+rLs5E4qipNO7bhGo1Y648QXv5f5E0do7HsbI+VvgjoQ2xhZN8v4gq49blaHYrlS8tpu4v/0LmrcuJ83KllRdaCX9kwUCI+X2hVcIABt7ztN/PywutRCBypQ0DWR8rwklCGwbyQisRTnJ7HCbyQisRLrJgIMyOVDbK+lgRUhLaCJH1sSJUJLRCxBjpiBIixkhohYgxElohYoyEVogYI6EVIsZIaIWIMf8DKwh+/2AkP4MAAAAASUVORK5CYII=\n", "text/plain": ["
"]}, "metadata": {}, "output_type": "display_data"}], "source": ["mat = numpy.random.random((15, 15))\n", "mat = mat + mat.T\n", "adja = (mat >= 1.45).astype(int)\n", "for i in range(adja.shape[0]):\n", " adja[i ,i] = 0\n", "\n", "fix, ax = plt.subplots(1, 1, figsize=(4, 4))\n", "G = networkx.from_numpy_matrix(adja) \n", "networkx.draw(G, with_labels=True, ax=ax) "]}, {"cell_type": "code", "execution_count": 9, "id": "a2c8b379", "metadata": {}, "outputs": [{"data": {"text/plain": ["array([0, 0, 2, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0])"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["C = numpy.arange(adja.shape[0])\n", "maj = 1\n", "while maj > 0:\n", " maj = 0\n", " for i in range(adja.shape[0]):\n", " for j in range(i + 1, adja.shape[1]):\n", " if adja[i, j] > 0 and C[i] != C[j]:\n", " maj += 1\n", " C[i] = C[j] = min(C[i], C[j])\n", " \n", "C"]}, {"cell_type": "code", "execution_count": 10, "id": "b93983d7", "metadata": {}, "outputs": [{"data": {"text/plain": ["{0, 2, 8}"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["set(C)"]}, {"cell_type": "code", "execution_count": 11, "id": "4dfba86b", "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["Il y a 3 composantes connexes.\n"]}], "source": ["print(\"Il y a %r composantes connexes.\" % len(set(C)))"]}, {"cell_type": "markdown", "id": "e33f65b2", "metadata": {}, "source": ["## G\u00e9n\u00e9ration d'un graphe al\u00e9atoire\n", "\n", "Les graphes issues de r\u00e9seaux sociaux ont souvent des propri\u00e9t\u00e9s statistiques particuli\u00e8res. La distribution des degr\u00e9s des noeuds suit souvent une loi \u00e0 queue \u00e9paisse. C'est dans cette cat\u00e9gorie qu'on range les lois qui admettent une esp\u00e9rance mais pas de variance.\n", "\n", "Donc on ne veut pas g\u00e9n\u00e9rer n'importe quel graphe al\u00e9atoire, on veut g\u00e9n\u00e9rer un graphe al\u00e9atoire dont la distribution des degr\u00e9s des noeuds est connue.\n", "\n", "On s'inspire de [algorithme graphe al\u00e9atoire](http://www.proba.jussieu.fr/pageperso/rebafka/BookGraphes/graphes-scale-free.html).\n", "\n", "**Etape 1 :** transformer une distribution des degr\u00e9s des noeuds en une liste de degr\u00e9 souhait\u00e9 pour chaque noeud."]}, {"cell_type": "code", "execution_count": 12, "id": "36b79e8c", "metadata": {}, "outputs": [{"data": {"text/plain": ["array([1, 1, 1, 1, 2, 2, 2, 3, 3])"]}, "execution_count": 13, "metadata": {}, "output_type": "execute_result"}], "source": ["def distribution_to_degree_list(hist):\n", " N = int(hist.sum())\n", " deg = numpy.zeros(N, dtype=numpy.int32)\n", " p = 0\n", " for i, nh in enumerate(hist):\n", " for n in range(nh):\n", " deg[p] = i\n", " p += 1\n", " return deg\n", " \n", "dist = numpy.array(numpy.array([0, 4, 3, 2]))\n", "distribution_to_degree_list(dist)"]}, {"cell_type": "markdown", "id": "7ba2df37", "metadata": {}, "source": ["**Etape 2 :** on part d'un tableau de m\u00eame dimension qui repr\u00e9sente les degr\u00e9s du graphe en cours de construction. Il est nul au d\u00e9part. On tire des noeuds de fa\u00e7on al\u00e9atoire tant que ce degr\u00e9 est inf\u00e9rieur au degr\u00e9 souhait\u00e9. On l'incr\u00e9mente \u00e0 chaque fois qu'un arc est cr\u00e9\u00e9."]}, {"cell_type": "markdown", "id": "9bb9741a", "metadata": {}, "source": ["### Version 1"]}, {"cell_type": "code", "execution_count": 13, "id": "922a80cf", "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["sum=14 expected=17: 100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 85/85 [00:00<00:00, 804.03it/s]\n", ":42: UserWarning: Graphe incomplet\n", "degrees=array([1, 1, 1, 1, 1, 2, 2, 2, 3, 3])\n", "current=array([1, 1, 1, 1, 1, 2, 2, 1, 1, 3])\n", " warnings.warn(\"Graphe incomplet\\ndegrees=%r\\ncurrent=%r\" % (degrees, current))\n"]}, {"data": {"text/plain": ["array([[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],\n", " [0, 0, 1, 0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],\n", " [0, 0, 0, 1, 1, 1, 0, 0, 0, 0]])"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}], "source": ["import warnings\n", "from tqdm import tqdm # pour visualiser la progression de l'algorithme\n", "\n", "\n", "def random_graph(distribution_degree):\n", " degrees = distribution_to_degree_list(distribution_degree)\n", " current = numpy.zeros(degrees.shape[0], dtype=numpy.int32)\n", " expected = degrees.sum()\n", " adja = numpy.zeros((degrees.shape[0], degrees.shape[0]), dtype=numpy.int32)\n", " nb = 0\n", " \n", " # tqdm: une boucle qui affiche l'avancement dans un notebook\n", " # on \u00e9vite la boucle infinie en limitant le nombre d'it\u00e9ration \n", " loop = tqdm(range(expected * 5))\n", " for n_iter in loop:\n", " loop.set_description(\"sum=%r expected=%r\" % (nb, expected))\n", " nodes = [i for i, (c, d) in enumerate(zip(current, degrees)) \n", " if c < d]\n", " if len(nodes) == 1:\n", " i, j = 0, 0\n", " elif len(nodes) == 2:\n", " di, dj = 0, 0\n", " i, j = nodes[di], nodes[dj]\n", " else:\n", " di, dj = numpy.random.randint(0, len(nodes), 2)\n", " i, j = nodes[di], nodes[dj]\n", " if i == j or adja[i, j] == 1:\n", " # arc d\u00e9j\u00e0 cr\u00e9\u00e9 ou impossible\n", " continue\n", " current[i] += 1\n", " current[j] += 1\n", " adja[i, j] = 1\n", " adja[j, i] = 1\n", " nb += 2\n", " \n", " if nb >= expected:\n", " # Tous les noeuds ont le degr\u00e9 souhait\u00e9.\n", " loop.set_description(\"sum=%r expected=%r\" % (nb, expected))\n", " break\n", "\n", " if nb < expected:\n", " warnings.warn(\"Graphe incomplet\\ndegrees=%r\\ncurrent=%r\" % (degrees, current))\n", " return adja\n", "\n", "adja = random_graph(numpy.array([0, 5, 3, 2]))\n", "adja"]}, {"cell_type": "markdown", "id": "d7926547", "metadata": {}, "source": ["On remarque que la somme des degr\u00e9s ne peut \u00eatre impaire car chaque arc est connect\u00e9 \u00e0 deux noeuds."]}, {"cell_type": "code", "execution_count": 14, "id": "d46d210d", "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["sum=12 expected=16: 100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 80/80 [00:00<00:00, 1145.86it/s]\n", ":42: UserWarning: Graphe incomplet\n", "degrees=array([1, 1, 1, 1, 2, 2, 2, 3, 3])\n", "current=array([1, 1, 1, 1, 2, 1, 2, 3, 0])\n", " warnings.warn(\"Graphe incomplet\\ndegrees=%r\\ncurrent=%r\" % (degrees, current))\n"]}, {"data": {"text/plain": ["array([[0, 0, 0, 0, 1, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 1, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 1, 0, 0, 0, 0],\n", " [1, 0, 0, 1, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 1, 0],\n", " [0, 1, 0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 1, 0, 0, 1, 1, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0]])"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["adja = random_graph(numpy.array([0, 4, 3, 2]))\n", "adja"]}, {"cell_type": "markdown", "id": "645aecbb", "metadata": {}, "source": ["On regarde la distribution des degr\u00e9s :"]}, {"cell_type": "code", "execution_count": 15, "id": "82caa1bd", "metadata": {}, "outputs": [{"data": {"text/plain": ["array([1, 1, 1, 1, 2, 1, 2, 3, 0])"]}, "execution_count": 16, "metadata": {}, "output_type": "execute_result"}], "source": ["adja.sum(axis=1)"]}, {"cell_type": "code", "execution_count": 16, "id": "ed7d190c", "metadata": {}, "outputs": [{"data": {"text/plain": ["Counter({1: 5, 2: 2, 3: 1, 0: 1})"]}, "execution_count": 17, "metadata": {}, "output_type": "execute_result"}], "source": ["from collections import Counter\n", "Counter(adja.sum(axis=1))"]}, {"cell_type": "markdown", "id": "280ea232", "metadata": {}, "source": ["L'algorithme ne semble pas aboutir \u00e0 un graphe qui r\u00e9pond au crit\u00e8re souhait\u00e9. Il existe deux cas pour lesquels l'algorithme reste bloqu\u00e9. On note $A_t$ l'ensemble des noeuds \u00e0 l'it\u00e9ration *t* dont les degr\u00e9s sont inf\u00e9rieurs au degr\u00e9 souhait\u00e9.\n", "\n", "* Tous les noeuds dans l'ensemble $A_t$ sont d\u00e9j\u00e0 reli\u00e9s entre eux.\n", "* La seule option possible est de cr\u00e9er un arc entre un noeud et lui-m\u00eame.\n", "\n", "Pour \u00e9viter cela, on choisit apr\u00e8s 5 tirages ne donnant lieu \u00e0 aucune cr\u00e9ation d'arc d'en supprimer quelques-uns. L'algorithme qui suit n'est pas le plus efficace mais voyons d\u00e9j\u00e0 s'il marche avant de nous pencher sur un autre."]}, {"cell_type": "markdown", "id": "7d329116", "metadata": {}, "source": ["### Version 2"]}, {"cell_type": "code", "execution_count": 17, "id": "542f9359", "metadata": {"scrolled": false}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["sum=16 expected=16 n_removed=0: 9%|\u2589 | 7/80 [00:00<00:00, 638.07it/s]\n"]}, {"data": {"text/plain": ["array([[0, 0, 0, 0, 0, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 1, 0, 0, 0, 0],\n", " [0, 0, 0, 1, 0, 0, 0, 0, 0],\n", " [0, 0, 1, 0, 0, 0, 0, 0, 0],\n", " [0, 1, 0, 0, 0, 1, 0, 0, 0],\n", " [0, 0, 0, 0, 1, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 1, 1],\n", " [0, 0, 0, 0, 0, 1, 1, 0, 1],\n", " [1, 0, 0, 0, 0, 0, 1, 1, 0]])"]}, "execution_count": 18, "metadata": {}, "output_type": "execute_result"}], "source": ["def random_graph_remove(distribution_degree):\n", " degrees = distribution_to_degree_list(distribution_degree)\n", " current = numpy.zeros(degrees.shape[0], dtype=numpy.int32)\n", " expected = degrees.sum()\n", " adja = numpy.zeros((degrees.shape[0], degrees.shape[0]), dtype=numpy.int32)\n", " nb = 0\n", " \n", " loop = tqdm(range(expected * 5))\n", " last_added = 0\n", " n_removed = 0\n", " edges = {i: [] for i in range(current.shape[0])}\n", " for n_iter in loop:\n", " loop.set_description(\"sum=%r expected=%r n_removed=%r\" % (nb, expected, n_removed))\n", " nodes = [i for i, (c, d) in enumerate(zip(current, degrees)) \n", " if c < d]\n", " if len(nodes) > 1:\n", " di, dj = numpy.random.randint(0, len(nodes), 2)\n", " i, j = nodes[di], nodes[dj]\n", " else:\n", " i = j = 0\n", " \n", " if i == j or adja[i, j] == 1:\n", " if last_added + 5 < n_iter:\n", " # on supprime un arc\n", " nodes = [i for i, c in enumerate(current) if c > 0]\n", " di = (0 if len(nodes) <= 1 else \n", " numpy.random.randint(0, len(nodes)))\n", " i = nodes[di]\n", " dh = (0 if len(edges[i]) <= 1 else\n", " numpy.random.randint(0, len(edges[i])))\n", " j = edges[i][dh]\n", " \n", " adja[i, j] = 0\n", " adja[j, i] = 0\n", " edges[i].remove(j)\n", " edges[j].remove(i)\n", " current[i] -= 1\n", " current[j] -= 1\n", " nb -= 2\n", " n_removed += 2\n", " continue\n", "\n", " current[i] += 1\n", " current[j] += 1\n", " adja[i, j] = 1\n", " adja[j, i] = 1\n", " nb += 2\n", " last_added = n_iter\n", " edges[i].append(j)\n", " edges[j].append(i)\n", " \n", " if nb >= expected:\n", " # Tous les noeuds ont le degr\u00e9 souhait\u00e9.\n", " loop.set_description(\"sum=%r expected=%r n_removed=%r\" % (nb, expected, n_removed))\n", " break\n", "\n", " if nb < expected:\n", " warnings.warn(\"Graphe incomplet\\ndegrees=%r\\ncurrent=%r\" % (degrees, current))\n", " return adja\n", "\n", "adja = random_graph_remove(numpy.array([0, 4, 3, 2]))\n", "adja"]}, {"cell_type": "code", "execution_count": 18, "id": "a3b6a407", "metadata": {}, "outputs": [{"data": {"text/plain": ["Counter({1: 4, 2: 3, 3: 2})"]}, "execution_count": 19, "metadata": {}, "output_type": "execute_result"}], "source": ["Counter(adja.sum(axis=1))"]}, {"cell_type": "markdown", "id": "71890aae", "metadata": {}, "source": ["Il est possible que cet algorithme aboutisse au r\u00e9sultat souhait\u00e9 m\u00eame avec beaucoup de temps. Est-ce la strat\u00e9gie ou le fait que la distribution des noeuds ne soit pas [r\u00e9alisable](http://www.proba.jussieu.fr/pageperso/rebafka/BookGraphes/graphes-scale-free.html#suite-de-degr%C3%A9s-r%C3%A9alisable)."]}, {"cell_type": "code", "execution_count": 19, "id": "c939dcf0", "metadata": {}, "outputs": [{"data": {"text/plain": ["False"]}, "execution_count": 20, "metadata": {}, "output_type": "execute_result"}], "source": ["def distribution_degree_realisable(distribution):\n", " degrees = -numpy.array(sorted(-distribution_to_degree_list(distribution)))\n", " if degrees.sum() % 2 != 0:\n", " return False\n", " sumdi = 0\n", " for i in range(degrees.shape[0] - 1):\n", " sumdi += degrees[i]\n", " mindi = numpy.minimum(degrees[i+1:], i + 1).sum()\n", " if sumdi >= i * (i + 1) + mindi:\n", " return False\n", " return True\n", "\n", "distribution_degree_realisable(numpy.array([0, 2, 0, 0, 0, 0, 0, 0, 0, 1]))"]}, {"cell_type": "code", "execution_count": 20, "id": "11176a52", "metadata": {}, "outputs": [{"data": {"text/plain": ["True"]}, "execution_count": 21, "metadata": {}, "output_type": "execute_result"}], "source": ["distribution_degree_realisable(numpy.array([0, 4, 3, 2]))"]}, {"cell_type": "code", "execution_count": 21, "id": "419c31ad", "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAO0AAADnCAYAAADy1tHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAVC0lEQVR4nO3dfXBU5b0H8O/Zcza7GzbJJiEQJClYYwgCQQJVCjUJCKRy26G08SoXrFd6C04crHdu7+i9VOe+6FiV1vEF8PrS3o7aXjrUaUVjQRSwitQCIYgQKFowSxPIi0te2N3s7jn3jzQhy+7Z3cBm9zwn38+MM2bPsyePM/n6POec5zw/SdM0DUQkDEu6O0BEw8PQEgmGoSUSDENLJBiGlkgwDC2RYJR0d4AonvYeP7YecKOptQtdviCy7QrKCrNx6+wi5Dtt6e5eykl8TktG1djswcbdJ7HnRBsAwB9UB4/ZFQs0ANVTClBXVYKZxa70dDINGFoypFf2ncIj9U3wBUOI9RcqSYBdkbF+aRlWzZ2csv6lE6fHZDj9gT0Gb0CN21bTAG8ghEfqjwHAqAgub0SRoTQ2e/BIfVNCgR3KG1DxSH0TDrs9I9MxA2FoyVA27j4JXzAU9lnXgW1o+d/7cPqJb6H9jSd1v+sLhrBp98mR7mLaMbRkGO09fuw50RZxDas485Ez7zY4yxfH/L6mAbuOt6Gjxz+CvUw/hpYMY+sBd9TPM6fMQ2bpV2FxZMc9hwRg68Ho5zELhpYMo6m1K+yxzuXwBVU0tXQnqUfGxNCSYXT5gkk6TyAp5zEqhpYMI9uenCeQ2XZrUs5jVAwtGUZZYTZsypX9SdoVC8omZCWpR8bE0JJh1M4uivq5poagBfsANQRoKrRgHzQ1FL0tgNqK6OcxC66IIsMY67ShqrQAbx87G/bY5/wH/4fzH/xq8OfeT3YhZ/4KuG5aGfZ9SQIWTCkw/UsEXHtMhtLY7MHtL+yDNxB9JI3FYZWxZc1clBe5kt8xA+H0mAxlZrEL65eWwWEd3p+mw2rB+qVlpg8swOkxGdDAon++5RMdp8dkWIfdHmzafRK7jrdBQv/CiQED79MumFKAuuqSUTHCDmBoyfA6evzYetCNppZuvPXObsyeMRWVM0tQW8GdK4gMr7a2FrfddhtuvfXWdHclbXgjioRSWFiIlpaWdHcjrRhaEsqECRMY2nR3gGg4CgsL0dramu5upBVDS0LhSMvQkmA40jK0JBiOtHzkQ4IJBoNwOBzwer1QlNG5oG90/leTkAbKg4xffj/ufOlDFLico7I8CEdaMjyWBwnH0JKhsTxIJE6PybBYHiQ63j0mQ4pXHiTQeQann1iO9m0bwj4fDeVBGFoypGjlQYbq3PEcbBOujXrM7OVBGFoyHL3yIAN6j+6BxT4G9kkzox43e3kQhpYMR688CACo/gvw/OFV5C78p5jnMHN5EIaWDCdWeRDPey/DOXMJlOyxMc9h5vIgDC0Zjl55kL6zn8F3uhHZX1mW4HnMWR6Ej3zIcPTKg/g+/xjB82fh3nQXAEDr8wGaipb2H2DCXU9FOY85y4MwtGQ4/eVBWiOmyM7razBmauXgz10fvYbg+bPIq7kn4hxmLg/C6TEZjl55EIvVDtmZO/iPZLVDUjIgZ+ZEtDVzeRCOtGQ4euVBLnVpWZABZi8PwpGWDOme6hLYFfmyvmtXZNRVlyS5R8bB0JIhsTyIPk6PybBYHiQ6vppHhsfyIOEYWhLG0PIgXb4Afr/tNfzzP96Gu6qnmvamUzQMLQlrzpw52LhxI2688cZ0dyWleCOKhDVp0iScPn063d1IOYaWhDV58mScOnUq3d1IOYaWhMWRlkgwHGmJBDNaR1rePSZheTweFBcXo6urC5Ikpbs7KcORloTlcrkgyzI6OzvT3ZWUYmhJaKNxiszQktBG480ohpaExpGWSDCTJ08edaHlq3kkrPYePz7N+DL2+i1Y/Ys/IduujIrSl3zkQ8IZWvpSU1X0Ddn/bTSUvmRoSSgsfcnpMQmEpS/78UYUCSFe6Us9Zix9yZGWhKBX+rL11Qfg/+txSJb+nRvlrHxMXPM/YW0GSl8+t2pOSvo60hhaMrx4pS/zltyNrJk1ut8fWvrSDHeVOT0mw4tV+jJRZip9yZGWDC9W6UsA8Oz+BTy7fwFr3kS4Ku+AfVJ5RBszlb5kaMnw9EpfAkDugrtgzS+GJFvRe+w9nPvNf2PCXU/DmjshynnMUfqS02MyPL3SlwBgu2oKLLZMSIoVzhk3wzZxKryf7tc5jzlKXzK0ZHj9pS8T/FOVJPTXzAtnptKXDC0Znl7pS9XXA+9nB6AF+6CpIfR8sgv+5iNwfHl2RFszlb7kNS0Znl7pS00NwfPeKwh0ugHJAmt+EQq+/SNY8yaGfd9spS+59piE0Njswe0v7IM3ELnAIh6HVcaWNXNNU+eH02MSAktfXsTpMQmDpS/7cXpMwolV+lKRNMiybOrSlwwtCevS0pen/nwMzuB5/OxHa0xz0ykahpZMY9u2bXj22Wexffv2dHdlRPFGFJnGrFmz0NDQALOPQwwtmcbEiROhaRpaWlrS3ZURxdCSaUiSNDjamhlDS6bC0BIJhqElEsxoCC0f+ZCpqKqKnJwcNDc3w+Vypbs7I4IjLZmKxWJBeXk5Dh06lO6ujBiGlkzH7FNkhpZM5/rrr2doiURi9pGWN6LIdPx+P1wuFzo7O+FwONLdnaTjSEumY7PZUFpaiiNHjqS7KyOCoSVTMvMUmTtXkClNKZ+D3xw9j6NbGtDlC5qqSjyvaclUBqrE72o6i0AgAMgXNyg3S5V4hpZMY7RUief0mExhNFWJ540oEt5oqxLPkZaEF61K/Oc/qQ37WQv2IWvWUuQtuTvscxGrxDO0JDS9KvFf+petg/+u9nnhfuYOZJZ9LeL7IlaJ5/SYhJZIlfgLx/dCzsyBrXha1OOiVYlnaElo8arEA0DPx+9gzPSFkCQp6nHRqsQztCS0WFXiASB4/hz8zUcwZsbNcc4jTpV4hpaEFqtKPAD0HHkXtqLrYHUVxjmPOFXiGVoSWrwq8b1H3oVz+sKY5xCtSjxDS0LTqxIPAD73MYR6OqLeNR5KtCrxDC0JbaBKfLR7TL1H3kFm6TxYbJm63xexSjzXHpPwRluVeI60JLzRViWeK6LIFIZTJR6aCkeGVdi3fDjSkmmsmjsZW9bMRc114yGpIShSeHLtigUZigVwN+JfKxQhAwvwmpZMalLpNKx59GdoD9rQ5Qsg225F2YQs1FYU4b236/Hggw+ioaEBVqs4z2cHMLRkOm63G7NmzcK5c+eiLl3UNA01NTVYunQp7rvvvtR38Apxekym8+GHH2LevHm6a40lScLTTz+Nhx9+GK2trSnu3ZVjaMl09u7di3nz5sVsU1ZWhtWrV+OBBx5IUa+Sh6El00kktADw4IMPYufOndi7d28KepU8fORDwmvv8WPrATeaWrvg6fXj9FXVOOQvwHVxXmzPysrC448/jnXr1uGjjz6CLMsp7PXl440oEtbAdql7TrQBQNh7tYlul6ppGqqqqrBy5UqsXbs2Bb2+cgwtCSmZ26UePnwYixcvxtGjR5Gfnz8yHU4ihpaEM5ztUgf0L1mcqhvcdevWIRgMYvPmzUnq5chhaEkosV4O6D26B54PfoVQVxvkMbnI/7v7YC+ePng81ssBX3zxBaZOnYr6+npUVFSEXScbrawIQ0tCWfPyfrx97GzElNj7lwZ0vPU0Cpbdj4yrShHq6QQAKFljB9tIElBz3Xjd7VJfeuklbP51PSpWPoA9f24HcHnXySONd49JGHrbpQLA+fdfRc78FbBNLAMQHtYB8bZLtV63EO0z8/r/p4DIhRm+vwV4x9GzeO9Ee9peOOBzWhKG3napmhqCv+Uk1Avncea578O98U507tgMNeCPaKu3Xeor+07h0beaADkjamDDft+QsiKv7Dt1Of8pV4QjLQlDb7vUUK8HUIO4cPwDjF/1GCSLjLbfPIzze7cgt+q7YW2jbZeqV1Yk6DmLjh2b0HemCVCsGDNlPnIXrYFk6X+eO1BWpLzIldJ3cjnSkjD0tkuVrP1T3azZ34TizIOcmYOsr3wL3k/365wnfLvUaGVFAKBjxybImS4UrXsZV931DHzNR9B98M2wNgNlRVKJIy0JQ2+7VNnuhHzJNazeywIA8P6ut1H3x5/jhhtuwLUzKnSvk4PnzyJ79jcgKRmQnRlwXD0bgfbPw9qko6wIR1oSRqztUp0zFqH7wBsI9XoQ8vWg60+/RWbJVyLa2RQLvr3wRpSWlmLHjh2446Fn4fN5o54ze84y9B59D2rAh2B3O7yf7Yfj6oqIdqkuK8KRloRRO7sIT+48EfVYzvzbEfJ24czzayEpVowpuwk5826L2vaH3/4a8p39FQfu29KA3x76a9R29uLp6Dn0ezT/9O8BTcWY6TfDUfrViHapLivC0JIwBrZLjfacVpIV5NfUIb+mTvf70bZL1btO1jQVZ3/9ELKu/zoK79gANeBFx5tPwbP758hdsDqifSrLinB6TEK5p7oEduXy3saxKzLqqkvCPtO7Tla93Qh1tSGr4huQFCtkRzac5Yt0b26lsqwIQ0tCSfZ2qXrXyXJmDpSc8ehuqIemhqD6etDz8Tuwjrs6om2qy4pwGSMJKVlv+bT3+DH/sXejPv/tO/sZOnc+j8C5vwAWGfZJ5chbvBbymNywdjbFgr33L0zZ3WOGloR12O3Bpt0nset4GyRcXGYIXFwnvGBKAeqqS2IuftBbz5yIeOuZRwJDS8Lr6PFj60E3mlq6I7ZLTWT0E62sCENLhMt7R1dGCP+5rDzlLw3wRhQR+qsTrF86FQ6rHLUC31D918kWyI2/w+fv/jI1HRyCz2mJ/mbV3MkoL3IlfJ081jITlZWVcDqduPfee1PWT06PiaJI9Dr59OnTqKysxEMPPYTvfe97KekbQ0t0hU6cOIEFCxZgw4YNWLFixYj/Pk6Pia5QaWkptm/fjkWLFiEzMxPLli0b0d/H0BIlwfTp0/Hmm2/illtugcPhwJIlSwaPJXuTOE6PiZLo/fffx/Lly/Haa68he/KMK95MPRqGlijJdu7ciTv+63lkVd6JgIor3kz9UpweEyVZq7MEzpu+i74EFlgN3SQOQELB5UhLlER6SyJD3m501D8F36kGWBzZyK26E2OmVYe1SXRJJFdEESWR3iZxnTs2Q5KtKFr3CsZ+84f9uzy2nQ5rk+gmcQwtUZLobaau9vlw4fheuCpXwZLhgL14GjJLbkTvJ7vC2g3dJC4WhpYoSfQ2Uw92noFkkWHNmzj4mXXc1QhcMtICiW0Sx9ASJYneZupqwAvJ5gj7zGLLhNoXuQtkIpvEMbRESaK3SZzF6oDmDw+o5r8AS4Yjavt4m8QxtERJordJnJI3EZoaQqDzzOBnfef+AmvBJJ3zxN4kjqElShK9TeIsGXZkTvkqPH94FWqfDz73UVw4+UeMmbYgom0im8QxtERJUju7SPdY3pI6aME+uJ9ZifbXn0D+kjpkRBlpNQC1FfrnAbgiiihpYm2mLjuyMO47P4r5/WibqUfDkZYoiZK9mXo0DC1REiV7M/VoOD0mSrKBRf/J2Ew96nf4wgDRyEjWZuqXYmiJRtiVbqZ+KYaWSDC8EUUkGIaWSDAMLZFgGFoiwTC0RIJhaIkEw9ASCYahJRIMQ0skGIaWSDAMLZFgGFoiwTC0RIJhaIkEw9ASCYahJRIMQ0skGIaWSDAMLZFgGFoiwTC0RIJhaIkEw9ASCYahJRIMQ0skGMMU4Grv8WPrATeaWrvQ5Qsi266grDAbt86+vNIJRGaV9rIgjc0ebNx9EntOtAEA/FGKFFVPKUBdVQlmFrvS00kiA0lraF/Zd2rEygESmVXapsf9gT0Gb0CN21bTAG8ghEfqjwEAg0ujWlpG2sZmD25/YR+8gVDY5+3bNsB3qhFqwAd5TC6y534HWTNrwto4rDK2rJk7rHqeRGaSltCueXk/3j52NmJK3Nd2GtbcqyApVgQ6mtH6y3/DuFv/A7bCksE2kgTUXDcez62ak+JeExlDyh/5tPf4sedEW9Rr2IyCSZAU699+kiBBQvCLlrA2mgbsOt6Gjh7/yHeWyIBSfk279YA75vGO7ZvQ+/E70IJ+ZIy/Bo5rIkdUCcDWg26srbxmhHpJZFwpD21Ta1fYY51L5dfUIW/xWvjPNMH3+ceQZGtEG19QRVNL90h2k8iwUj497vIF47aRLDLsxdMQ6m5Hd0O9znkCye4akRBSHtps+zAGd1WNuKa9eJ7IEZhoNEh5aMsKs2FTIn9tqNeD3qN7oPZ5oakheD87gN5je2CffH1EW7tiQdmErBT0lsh4Un5NWzu7CE/uPBF5QJLQ3fAWOrZvAjQVSs445N78fWRee2NEUw1AbUXRyHeWyIAuO7SXu8BfCXqR3evGOWshJMvFEVfOzEHhyh/H/b2SBCyYUsCXCGjUGvbiiitZ4P/666+jrq4OlcvvwEFXJXwx7iLr4YooGu2GFdrLXeDf1taGe++9F/v378eLL76IqqqqYa09HuCwWrB+6VSuPaZRLeEbURdDFjuwQPgC/x88uxUzZsxAUVERGhsbUVVVBaB/0f/6pVPhsMqQpNjnk6T+EZaBJUpwpI22wF8LBtCxYxN8pw5B9fVAcRUit+rOyBVMwT48umgcVtTMj3ruw24PNu0+iV3H2yABYVPmgen2gikFqKsu4ZSYCAneiNq4+yR8wfA3cjQ1BCVrLAr/4ceQcwrg/XQ/2n73GK5a/SwU1/jBdpI1A3vabFihc+7yIheeWzUHHT1+bD3oRlNLN7p8AWTbrSibkIXaCu5cQTRU3NDqLfC3ZNjhumnl4M+ZJTdAyRkPf+vJsNAOXeAfK3z5ThvXEhMlIO41bbwF/gNCvV8g0HkGGQVfijg2sMCfiK5c3NDGW+APAFooiPbXN8A542ZY84sjjnOBP1HyxA1tvAX+mqai/Y2fALKCvMV3xzgPF/gTJUPc0MZa4K9pGjrqn0ao14OC5f8OSdZvywX+RMkRN7R6C/wBoHP7RgQ6mjGu9iFYrPo3mbjAnyh54j6nbe/xY/5j70Zc1wbPn8OZzasB2QrJIg9+nvf1e+CctiCsrU2xYO/9C/nohigJ4j7yGeu0oaq0IGIjNiVnHCY98EbcX8AF/kTJldAyxnuqS2BX5PgNo7ArMuqqS+I3JKKEJBTamcUurF9aBod1eO/M9y/wL+PyQ6IkSvh92oGF+izjQZRew36flgv8idLrsisMcIE/UXqkvdQlEQ0PK8ETCYahJRIMQ0skGIaWSDAMLZFgGFoiwfw/4BXB/nlb19YAAAAASUVORK5CYII=\n", "text/plain": ["
"]}, "metadata": {}, "output_type": "display_data"}], "source": ["fix, ax = plt.subplots(1, 1, figsize=(4, 4))\n", "G = networkx.from_numpy_matrix(adja) \n", "networkx.draw(G, with_labels=True, ax=ax) "]}, {"cell_type": "markdown", "id": "c1bf97f2", "metadata": {}, "source": ["Pour ce type de structure, la g\u00e9n\u00e9ration al\u00e9atoire est d'autant plus rapide qu'il y a peu de tirages rejet\u00e9s."]}, {"cell_type": "code", "execution_count": 22, "id": "9ba97dcb", "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.5"}}, "nbformat": 4, "nbformat_minor": 5}