{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Redes Complexas (continuação)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Mais sobre grau" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dada a matriz de adjacência $\\mathbf{A}$ de um grafo sem direção e sem peso, podemos calcular o grau do vértice $i$ como a soma das entradas na linha ou na coluna $i$ da matriz:\n", "$$k_i = \\sum_{j=1}^{n} a_{ij} = \\sum_{j=1}^{n} a_{ji}.$$\n", "\n", "No caso de um grafo *com direção*, precisamos indicar melhor ao que nos referimos. Neste caso, **grau** é o número de arestas conectadas no vértice (não importa se de entrada ou saída), já o **grau de saída** é o número de arestas que saem do vértice e o **grau de entrada** é o número de arestas que chegam no vértice. Se convencionamos que $a_{ij}$ indica a presença de uma aresta que sai de $i$ e chega em $j$, então:\n", "$$k^{\\mathrm{out}}_i = \\sum_{j=1}^{n} a_{ij}$$ e $$k^{\\mathrm{in}}_i = \\sum_{j=1}^{n} a_{ji}.$$\n", "De acordo com essa convenção então $$k_i = k^{\\mathrm{out}}_i + k^{\\mathrm{in}}_i.$$\n", "\n", "Se o grafo tem peso, então as definições de grau em geral são mantidas as mesmas (isto é, não consideramos o peso), mas quando estamos interessados em considerar o peso usamos o conceito de **força** (**strength**) do vértice, que é a soma dos pesos das arestas ligadas a ele, com as respectivas definições de entrada e saída quando existe direção nas arestas.\n", "\n", "Construindo a matriz de pesos $\\mathbf{W}$ com $w_{ij} = w(i, j)$, então\n", "$$s_i = \\sum_{j=1}^{n} w_{ij}$$ para redes sem direção e\n", "$$s^{\\mathrm{out}}_{i} = \\sum_{j=1}^{n}w_{ij}, \\quad s^{\\mathrm{in}}_{i} = \\sum_{j=1}^{n}w_{ji}$$ para redes com direção." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Distribuição de Grau" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Seja $P(k)$ a probabilidade de que um vértice escolhido aleatoriamente no grafo tenha o grau $k$. Esta distribuição é conhecida como a **distribuição de graus**.\n", "\n", "No caso de um grafo específico, definimos $$P(k) = \\frac{n_k}{n},$$ onde $n_k$ é o número de vértices com grau $k$ no grafo." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import networkx as nx" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "gex = nx.read_gml('exemplo.gml')" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deVxU5f4H8M+ZBQZEVhFMUAwXBFdwQc21Ui8u3QhCBfTqr9QwcyO9Zi5lVibuYmZqmrtSGpq5EVgu5ALigqi4JIggoCzDMuv5/cFlEpkZtjmz8X2/XrxeOufMmWfmOXw585zzfA7DsiwIIYToB8/QDSCEkMaEii4hhOgRFV1CCNEjKrqEEKJHVHQJIUSPBNoWNmvWjPXw8NBTUwghxDxcuXIlj2VZZ3XLtBZdDw8PXL58mZtWEUKImWIY5m9Ny2h4gRBC9IiKLiGE6BEVXUII0SMquoQQokdUdAkhRI+o6BJCiB5R0SWEED2ioksIIXpERZcQQvSIii4hhOgRFV1CCNEjrdkLpLo8sQQxVzKRll2EonI5bEUCeLnaItjPDU42loZuHqkB9R8xNEbbPdJ69OjBUuBNhZSMAkQnpOPMnVwAgESuVC0TCXhgAQzq4IyIgW3R1d3eQK0kmlD/EX1iGOYKy7I91C6joluzXYkPsexYGsrlCmi7jyfDACIBHwsCvBDm76G39hHtqP+IvmkrujS8UIOKX9hbKJMpa1yXZYEymQLLjt0CAPrFNQLUf8TYUNHVIiWjAMuOpVX5hX20MqjKOqxciqbdA+A4dKrqsTKZEsuOpaGLmz26uNFXVUNJyShA5Gff4PnVU5DmPkSTjgPRbOQs1fKSW3+i4OxuKIrzIWjaDPYDx8O6fR/qP8IpunpBi+iEdJTLFVUeazUnRvXjNn0XGIEFrL1eq/bccrkCGxPS9dVUokZ0QjqU1g6w6xsCmy5vVlkmL85D3pGVcBzyHtxnHYD94EnIi42CoqQAAPUf4Q4VXQ3yxBKcuZOrdQyw9PY58K3tYOnuU20ZywLxt3ORL5Zw2EqiSWX/WbfvC+v2fcCzsq2yXFGcD56oCaw8e4BhGFi37QlGaAl5wRMA1H+EO1R0NYi5klnjOuLrcWjSaQgYhlG7nAEQk1Tzdoju1dR/Fq5tIXRyR+ndv8AqFSi9cwGMQAihcxvVOtR/hAs0pqtBWnZRlcuKXiYvfApJxg04BXykcZ1yuRJpT4q5aB6pQU39x/D4aNJpCPJiV4CVS8HwhWj27/+CZyFSrUP9R7hARVeDonK51uXiG7/D0s0bQnvXGrYj02WzSC3V1H9lD6+iIP4HuIz7ChaunpBmpyM3ZikE734GC5dXX9gO9R/RLRpe0MBWpP3vUcmN32HTaUgttiPUVZNIHdTUf9Kc+7B094Fli3ZgGB4sW7SHxSsdUPbw6kvbof4jukVFVwMvV1tYCtR/POWZt6AQ56u9auFFIgEPXi2actE8UoPK/mOVCrByKaBUAKwSrFwKVqmAZYt2kGSmQppzHwAgzb4HScZNWDT3UG2D+o9wgYYXNHi7WwusOJ4KdX+XSm7Ewbp9X/AsrbVugwUQ5OvGTQOJVkF+blh9+g4Kz+1D4bm9qsdLbsbDrt9Y2PcPhd1rY5F76CsoSgvAt7KFXZ9gWLXxVa1L/Ue4QEVXjcTERERERMCyRzjKnNrj5avGnIZ/WOM2WKUSrS1K4WBNX08NoZmNJQa2d8YpRSjs+4eqXcfWbxRs/UapXcYwwOAOzhSCQ3SOhhdekJ+fj8mTJyMwMBBz5szBnoX/gUjIr9e2REI+np/dhz59+uDKlSs6bimpjWmD2kIkqGf/CfiIGNRWxy0ihIouAECpVGLLli3w9vaGSCRCamoqQkND0c3dAQsCvGAlrNvHZCXkYeFIb/z120FMnToVI0aMwLRp0/D8+XOO3gFRp6u7fb37b0GAF00BJpxo9EX36tWr6NevH7Zu3Yrjx49j3bp1sLf/55ctzN8DCwI6wkrIh4Y5ECoMA1gJ+VgQ0BFh/h7g8XiYOHEiUlNToVQq4e3tjR9//BHakt2IbjWk/wjhQqONdiwsLMTChQuxf/9+fPnll5g4cSJ4PM1/g65lFmBjQjrib+eCQcWF85Uq81gHd3BGxKC2Go+QLl26hA8++ADW1taIjo5G586ddfyuiCa66D9CaovydF/Asix2796NuXPnYuTIkfjqq6/g5ORU6+fniyWIScpE2pNi7D74M0KDA+HVoimCfGt35wGFQoHNmzdj8eLFCA8Px5IlS9C0KV2WpC8v9l9RuQy2ImGd+o+Q2qCi+z83b97EtGnTUFRUhI0bN8Lf379B22MYpt5DBU+fPsW8efNw6tQprFq1CsHBwRozHAghpkVb0W0UY7pisRhz587FoEGDEBQUhEuXLjW44DZU8+bN8cMPP2Dfvn344osvMHToUNy+fdugbSKEcM+siy7LsoiJiYG3tzeys7Nx48YNfPjhh+Dz63cZERdee+01JCUlISAgAP369cOCBQtQWlpq6GYRQjhitkX37t27GD58OJYsWYJdu3bhxx9/hIuLi6GbpZZAIMCsWbNw7do13L9/H97e3oiNjTV0swghHDC7oltWVoZFixahT58+ePPNN5GcnIwBAwYYulm18sorr2Dv3r3YunUr5s6di1GjRuHBgweGbhYhRIfMqugePXoUPj4+SEtLw9WrVxEZGQmh0PSm4b7++utISUlB37590bNnTyxduhQSCd3BgBBzYBZF9++//8a///1vzJ49G5s2bcKBAwfg5mbaQSWWlpaYP38+Ll++jKSkJHTu3BknT540dLMIIQ1k0kVXIpHgyy+/hJ+fH3r06IHr169j6NChhm6WTnl4eODQoUNYvXo1pk6diuDgYGRm0i1kCDFVJlt0T58+jS5duiAxMRGXLl3Cp59+CktL8724fcSIEbh58ya8vb3RrVs3rFixAjIZ3dWAEFNjckX38ePHGDNmDN5//32sWLECsbGxaNOmTc1PNANWVlb47LPPcOHCBcTFxaF79+44c+aMoZtFCKkDvefp5okliLmSibTsIhSVy2ErEsDL1RbBftqnYcpkMqxfvx5ffvklpk6dim3btsHaWnuIuLlq164dfvvtN/z8888IDw/HwIEDsWLFCri6ar9fG1D/z58QY2AO+6/epgGnZBQgOiEdZ+7kAkCVO7VWBo4M6uCMiIFt0dW9auDIn3/+iWnTpsHV1RUbNmxA+/btddKmhmrINGBdEYvFWLp0KbZt24ZFixbhgw8+gEBQ/W9pQz5/QgzN1PZfg2cv7Ep8iGXH0lAuV0BbjWKYivDoBQFeCPP3wNOnTzF37lycPn0aq1evRlBQkFHlExhD0a2UmpqKiIgIFBYW4ttvv60yzbm+nz8hxsAU91+DZi9UfGC3UCbT/oEBAMsCZTIFlh27hfeX/4hOnTqhWbNmuHXrFgXC1MDb2xvx8fGIjIxEYGAg3n//feTn59f789+V+FAv7SZEG3Pcfzk90k3JKMCY7xNRJlNUeTx7938hyboNhleRgcBv6oSWk7+r2jCFDCsD3BA4SO0fC6NgTEe6LyosLMSiRYuw/3QibN76FHJWzc01U8+g4NxeKIpywW/iAKcRMyFy76RabiXkY/9kf8qWJQaTklGAYZM/wfOrpyDNfYgmHQei2chZAADxzXg8Ox79z8osC1Yuget/1sDSta3B919tR7qcnkiLTkhHuVyhdpnj0Klo2nWY5icLhDiZCQRy1DZzZmdnh7Vr1yJ7Qxz+yiwFXvqCUPYgGc8TtsP5rXmweKU9FOJn1bZRLldgY0I6NoUZ7x89Yt6iE9KhtHaAXd8QlD1IAiuTqpbZ+AyGjc9g1f/F106j8Pw+WLh4AjDu/Zez4YU8sQRn7uTW+JVAE5YF4m/nIl9M01/rI08swdUcKcBU7+LCs7th128sLFt6gWF4EDRtBkHTZlXWoc+fGFJl/bBu3xfW7fuAZ2WrdX3xjTg06TRENQRpzPsvZ0U35or2WVMFCTuQsXYcsnd+jPK/r6ldhwEQk0Szr+pD0+fPKhWQPEmHsrQQjze9j8zoCXh28lsoZdV3Tvr8iaHUVD9eJC98CknGTTTpNKTK48a6/3I2vJCWXVTlso4XOQyeCKGTOxi+ECW3/sDTn5aixcR1EDq0qLJeuVyJtCfFXDXRrGn6/BUlBYBSjtLb5+ASthwMj4/cn75A4fn9cBg4vsq69PkTQ9FWP14mvhEHSzdvCO2rXqdurPsvZ0e6ReVyjcssX+kAnqU1GIEQNp1fh2XLjii7p/6E3e6DP4NhGKP8AWDwNmj62XPwkNrPkxFWXEDe1G8UBDaO4FvboWnPf2v8/IvKaaox0T9t9eNlJTd+h03n1zVsx/j2X86Krq2oDgfRDANA/eBvaHAgWJY1yh8ABm+Dpp9xwW+r/Tz5IhvwXxq/1d6PpheNSUxfbetHeWYqFOJnsO7QT8N2jG//5azoernawlJQffPKcjHK7l8BK5eCVSogvhkPScYNWLXxrbauSMCDVwu6U259aPr8AcCm8xsovnIUipICKMrFKL78C6zb9qy2noBRorWd3meKE6Laf1mlAqxcCigVAKtU1Y1KJdfjYN2+L3iW1SMBjLV+cPYbFeTnhtWn71R7nFUqUPDHLsieZQIMD0InNzgHfgqhU/X8WxZAkK9p5+Iayju+LRF14haqXS8GwK7fGCjKivB48xQwAiGaePWHXd+QauspFEosmTAc5wb0QXh4OIYPHw4LCws9tJ40dpX1o/DcPhSe26t6vORmPOz6jYV9/1CwcilK0s7C+e35ardhrPWD08kRk3dexqlbOfW6bIxVKtHZQYkj80Yb7Uw0Y50ckZqaimnTpiGzTQDkLt4aBm60YxhgmLcLvhrhiYMHD2Lnzp1IS0tDSEgIwsPD0atXL6PtF2IeGlI/KvdfQ12na7BpwNMGtYVIUL8771oKebh/9FsMGzYMd+5UP2Im1YnFYsybNw8DBw5EYGAg9i+aBJGwfp+/SMBHxKC2cHBwwOTJk/Hnn3/ir7/+gouLC8LCwuDl5YWlS5fSPdwIZxpSPyr3X2PEadHt6m6PBQFesBLW7WWshDwsGumDlPgjGD58OPr27YtPP/2Ubk2uAcuy+Omnn+Dt7Y2srCxcv34d06dPh6+HU70//wUBXtWmUL766qtYuHAh7ty5gx07diA7Oxu9evXCgAED8P3336OgoECXb4s0cg2pH+r2X2PBeeBNmL8HFgR0hJWQj5q+jTJMxZz/BQEdEebvAaFQiNmzZyMlJQXp6enw8fHBkSNHuG6ySUlPT0dAQAAWLVqEH3/8ETt37qySq9uQz1/zegz8/f0RHR2Nx48fY86cOThx4gRat26N4OBgxMbGQiqVanw+IbXFxf5raHrL072WWYCNCemIv50LBhUXLleqzMMc3MEZEYPaavwLdfr0aUybNg0dOnTA2rVrDX7HCEOO6ZaVleHrr79GdHQ05s2bh5kzZ2q987EuPv+aPH/+HAcOHMDOnTtx+/ZtjBkzBuHh4ejZsyeN/5IG0cf+q0sGz9N9Ub5YgpikTKQ9KUZRuQy2IiG8WjRFkG/tkt8lEglWrlyJVatWYebMmfj4448Ndm80QxXdX3/9FR999BF8fX2xevXqOt35uKGff23dv38fu3btws6dO8Hj8RAeHo6wsDB4eHjo7DVI46Ov/behtBVdrRfY+/n5scbqwYMH7FtvvcW2a9eOPXHihEHaUPHx6c/Dhw/Zt956i23bti17/Phxvb52fSmVSvbChQtsREQE26xZM7Z///7s5s2b2efPnxu6aYRwBsBlVkNdNbkbU1by8PDA4cOHsWrVKkydOhXvvvuu2d6aXCqV4quvvoKfnx/8/Pxw/fp1DBumJRbTiGgb/3333Xdx5MgRuqsxaVRMtuhWGjlyJG7evAkvLy9069YNUVFRZvVLHBcXhy5duuD8+fO4ePEiFi5cCJFIZOhm1YuFhQXeeustxMTE4OHDh3j99dexfPlytGzZEtOnT8fFixeN8rpnQnRJ72O6XLp79y6mT5+OzMxMbNy4EQMGDOD09bgc083KysLs2bORmJiIdevWYfTo0Zy8jjF4cfyXz+cjPDwcoaGhNP5LTJZB75GmT5W3Jl+yZAlCQ0Mxfvx45OTkGLpZdSKXy7F69Wp06dIFnp6eSE1NNeuCC1Rc/7to0SLcuXMH27dvR1ZWFnr06IGBAwdiy5YtdP0vMStmVXSBiqPPoKAg3Lp1C66urujUqRM2bNgAhUL9bYOMydmzZ+Hr64tjx47h3LlzWLZsGaytqwd5mKsXx3+zsrIwa9Ys/PbbbzT+S8yLpjNsrJFfvVBbN27cYAcOHMh2796dvXDhgk63DR1dvZCTk8NOmDCBbdmyJbt//35WqVTqZLvmIj8/n920aRPbr18/1tnZmZ0+fTp78eJF+pyI0YI5Xr1QWz4+PoiPj8ecOXMQGBiIyZMnIz8/39DNAgAoFAp8++236NSpE5ycnHDr1i28++67NJHgJY6OjpgyZQrOnj2LCxcuwMnJCWPHjkXHjh2xbNky/P3334ZuIiG1ZvZFF6j42hoaGorU1FSIRCJ4e3tjy5YtUCprdzsQLly6dAn+/v7Ys2cP4uLisHLlSjRtanzZn8bG09MTixcvxt27d/HDDz/g8ePH8PPzU43/FhYWGrqJhGin6RCYNZPhBXWSkpJYf39/1t/fn01OTq73dlCP4YX8/Hx26tSprKurK7tjxw76iqwDEomEPXToEBsYGMja2dmx7777LnvkyBFWKpUaummkkYKW4QWzumSsLpRKJX744Qd88sknCAkJwdKlS2FnZ1fj8/LEEsRcyURadhH2HDyEccFvw8vVFsF+2qchKpVK7NixA/Pnz0dQUBC++OIL2Nsbfo64uXn27Jkq/yE9PV2V/9ujRw+dDNu82P9F5XLYigS16n9jYertNxVGlb1gbPLz8zF//nwcPXoU33zzDUJDQ9X+cqZkFCA6IR1n7uQCQJU7lVYGbgzq4IyIgW3R1b1qMU1JSUFERATkcjk2btwIPz8/Tt8TqXDv3j3V9b8CgUCV/9C6des6b6sh/W8MTL39poaKbi389ddf+OCDD2Bra4vo6Gj4+Piolu1KfIhlx9JQLldoTbFnmIrw5AUBXgjz90BRUREWL16M3bt344svvsB7770HHq9RDKMbFZZlkZiYiJ07d+LAgQPo1KkTwsPDERQUVKtvN/Xtf2Nh6u03RY1mckRD9O7dG5cuXUJwcDAGDRqEuXPnQiwW/2+HvYUymfYdFgBYFiiTKbDs2C3M2BCDjh07ori4GKmpqZg8eTIVXANhGAZ9+vTBxo0bkZWVhZkzZ+LYsWNo3bo1QkJCcPToUY3X/9a3/3clPtT9G6kHU2+/OaIjXTVycnLw8ccfI+HaA1iOmAeZsvpwg+zZY2Rt/RBNvPqh2ajI6huRS/HFYCeEBXA7FZnU38vjv5X5v35+fmAYBikZBRjzfSLKZFUn1sgLcpB/ciOkj9MAgRBNOvSDwxuTwfD+ubWMlZCP/ZP9DZrtqq79srwM5J/8FtKcdPCt7OAweCKsO/St9lxjaL8poyPdOnJxccGPP/6InhMWQCZX/0fp2clNsGzRTuM2GKEFzj5rPLPJTJGjoyOmTp2Kc+fO4fz583B0dMSYMWPg7e2NL7/8ElHHrqFcXn0mY/7JjeBb28Nt+k68MnE9yjNuoDjp1yrrlMsV2JiQrq+3olZ0QnqV9rNKBZ7+tBTWbXvCfcZeOA7/EHlHV0L27HG15xpD+80VFV0N8sQS3HjGAmqGBEpSz4AnagJR664an8+yQPztXOSLJVw2k+jIi9f/btu2DemZOfgjPV/tV3J5YQ6adHwNjMACfBsHWLXxgyzvUZV1DN3/eWIJztzJrdJ+WX4GFOJnaNrz32B4fFh5dIVlS2+U3Pi92vMN3X5zRkVXg5gr6rN5lZJSFPy5Gw5D/q/GbTAAYpLMM+PXXFWO//YK+UhjhKZtj9EoSf0DSlk55MV5KLt/GVZtfKtvC4brf7X7r9ovbSykuepn9NH+yw0quhqkZRdVuaymUsEfO2HTdSgEts41bqNcrkTak2Iumkc4pqn/AUDk3hmyvEfIWPUuHkf/Bxau7WDVvk+19QzZ/+raL3RyA9/aDkV//QRWIUfZgySUP7oBVq7+aJb2X25Q0dWgqFxe7TFpzn2U/50C255v1WE7lIplitT1PwCwrBI5BxbBukNftJrzE9xm7IGyXIyChB/Urr/74M9gGEbvP3sOHqrWFoYvgPM7n6Ls3mVkrg9H0cVDaNLxNfCbNtPyOdD+q2tUdDWwFQmqPVb+6DrkhTnI3DgRGevDUHTxEEpvn8eTH2Zo2Y7mO/QS46Wu/wFAWVYMRVEumvqOBCMQgm9lC5sub6DsnvqrfEKDA7VOtefqZ1zw22rbY9G8DVxDv4b7zL1wCVkKeUE2LFu01/I50P6ra+r3LAIvV1tYCrKrfEWz6TYMTTr+cwlY0cWfIS/MgeOwaWq3IRLw4NWCQmxMkbr+BwC+tR0Edi4oTj4G296BYKVlEF+Pg7B5m2rbMGT/a2q/9OkDCB1bgmWVKE46Brn4OWw6v6F2G7T/coOOdDUI8qt+W3OeUAS+jYPqhxGKKs5gW6uf1cQCCPKt/e3RifFQ1/+VnAMXoOz+FWSuHYfH31Vcn+v4+vvV1jNk/2tqf8mNeGSuD0fmujCU/50ClzFLwQjUH83S/ssNOtLVoJmNJQa2d8apWzkaZ/LY9w/V+HyGAQZ3cKYQEROlrf8tXF6Fa+jXWp9v6P7X1H6HIZPgMGRSjc83dPvNGR3pajFtUFuIBPyaV1RDJOAjYlBbHbeI6JOp97+pt99cUdHVoqu7PRYEeMFKWLePyUrIw4IAL7OcQpknlmDTmXuYuT8Zk3Zcwsz9ydh05p5ZXkRv6v1v6u03VzS8UIPKtKXGntKkPRowG6tP3zHLaEBT739Tb785osCbWrqWWYCNCemIv50LBhUXjleqzCMd3MEZEYPamt0RAkUDmn7/m3r7TQ3l6epQvliCmKRMpD0pxu6DPyM0OBBeLZoiyNc8k/f/iQas/f3kKr6edjS7wguYfv+/2P6ichlsRUKTar+poKLLEYZhoO3zM3Waog3zjkSh/GEKlLJy8Js4wNb/HTTtOqzKOo0hGtDc+5/Un7aiS2O6RKOXowEr2foHw+lfM8AIhJDlZyB7z3xYuHjC0vWfs92V0YCbwtTud4Q0WnT1AlFLXTRgJQvn1i9cUM+AAQP58ydV1qFoQELUoyNdopamaMtK+Sc2ouR6HFi5BBYunrDyrH5EWxkNOGWAJ0etJMT0UNElammLNgQAp2ERcHxzCiSP01D+6DoYfvWppBQNSEh1NLxA1NIUbfgihseHyN0HiuI8FCcf07AdigYk5EVUdIlamqIN1VIqq43p/rMdigYk5EVUdIlaFdGA1XcPRUkBSlLPQCktA6tUoOz+FZTcOqP2fnEUDUhIdTSmS9QK8nPDypNp1RcwDIqTf0P+iY0Aq4TArjkcXn8f1u39q61K0YCEVEdFl1QjkUgQ9cVilD9qAkHr7mDBqJbxre1qjDUEALBK9GltT7OcCHkJFV1SRXJyMsaPH4927dph55IofBBzp9qMtNrgMyxOrJ6Ng3aRCA4O5qClxBTliSWIuZKJtOwiFJXLYSsSwMvVFsF++pmGbOjXB2gacIOY0zRQuVyOr7/+GuvWrcOqVasQGhoKhmEalL3QjsnB+PHj4efnhw0bNsDR0ZHDd6B/5tT/XNOeUlcRuMNlSp2+X1/bNGA6kUaQlpaGvn374s8//0RSUhLCwsLAMBVDCmH+HlgQ0BFWQj4YRvt2GKYic6Ey7KZ3795ITk5G8+bN0aVLFxw7pv6yMmLediU+xJjvE3HqVg4kcmW167/L//fYydQcjPk+EbsSH5rV67+Mim4jplQqsXr1avTv3x+TJk3C8ePH4eZW/cRXmL8H9k/2xzBvF1gKeBC9dFWDSMCDpYCHYd4u2D/Zv0q6mLW1NdasWYOdO3ciIiICkydPRnExTZhoLP75pqQ9FhSomDpeJlNg2bFbOit8hn59dWh4oQFM+evlgwcPMHHiRCgUCmzfvh2enrWbqtuQaMOioiLMnj0bcXFx2L59OwYOHKiLt2Iwptz/+pCSUYBhkz/B86unIM19iCYdB6LZyFnV1is4uweFZ/eg+ZgvYOXRDYBuUuq0vb68IAePN/0fGKFItb6t/zuw7zdWJ69PwwtEhWVZfP/99+jVqxdGjhyJhISEWhdcAHCyscSUAZ5YHdINuT8txeqQbpgywLNWJyFsbW2xZcsWrF+/HuPGjcPs2bNRVlbWkLdDjFh0QjqU1g6w6xsCmy5vql1H9vwJSm+fA9+m6nh/ZUod16/vPms/Ws2JQas5MaqCq6vX14SKbiOSlZWFESNGYNOmTUhISEBkZCT4/PrduLAhRo4ciWvXriErKwu+vr64dOmS3ttAuFWZUmfdvi+s2/cBz8pW7XrPTm2Cw6D/ALyqF1I1NKWutq+vCZcpeVR0GwGWZbF37150794dvXr1QmJiInx8fAzaJicnJ+zbtw9LlizByJEjsXDhQkilUoO2iehOTSl1AFCSdhYMTwArz55ql1em1HH1+gDweONEZEZPQN6va6AoLdTZ62tDRdfM5eXlISQkBEuXLsWvv/6KJUuWQCg0njyEkJAQXL16FcnJyfD398f169cN3SSiAzWl1CmlZSg4swMOb7yvcZ2GpNTV9Po8a1u4TliNlhE/oMV/1oCVliLvSJTOXl8bKrpm7MiRI+jSpQtatWqFpKQk9OhhnHdxaNGiBY4cOYIPP/wQQ4YMwfLly6FQ1H1CBjEeNaXUFfy5G018hkBo76p1vd0HfwbDMHX+2XPwkNbt8iysYNmiHRgeH/wmDnB88wOUP0iGUlL60vvQfUoeFV0zVFhYiIkTJ2LGjBnYt28foqKiIBKJan6iATEMg0mTJuHSpUs4fvw4BgwYgPR0bk5kEO7VlFJX/ncKiq8cQcb6MGSsD4OiOA95h79GYWJMlfVCgwPBsmydf8YFv123Bldeg/7S1fAdgsAAABqdSURBVChcpORR0TUzcXFx6NKlC0QiEa5du4YBAwYYukl14uHhgbi4OISEhMDf3x/R0dFQKms/G44Yh8qUOlapACuXAkoFwCrByqVglQq4jF2GV/4vGq9MXI9XJq4H38YRjsM/RFPfEaptNCSlrqbXl2Tdhiw/EyyrhKKsCM9ObYZlq87giZro5PW1oewFM1FaWop58+bh8OHD2LJlC4YNG1bzk4wUj8fDRx99hGHDhmHChAk4fPgwtm3bBnd3d0M3jdRSkJ8bVp++g8Jz+1B4bq/q8ZKb8bDrNxb2/UOrPoHhgSeyAc/CSvVQQ1Lqanp9oZMbnp/5EcrSAvAsrCHy6Abn0XOrbIOrlDwqumbgwoULmDBhAnr16oVr167BwcHB0E3SiQ4dOuDs2bP45ptv4Ovri6ioKIwfP141RZkYr2Y2lhjY3hmnFKHVC6wabhHbqvyfYYDBHZzrHUJTm9dv4q15ck5DX18bGl4wYRKJBPPnz8fbb7+Nr776Crt27TKbgltJIBDgk08+wenTp7Fy5Uq8/fbbyMnJMXSzSC1MG9QWIkH9rgMXCfiIGNTWpF9fEyq6Jurq1avo2bMnbt26hZSUFLzzzjuGbhKnunbtikuXLsHb2xtdu3bFTz/9ZOgmmaQ8sQSbztzDzP3JmLTjEmbuT8amM/c4mQTQ1d0eCwK8YCWsW5mpSKnzatAUYGN4fU0oe6EBDDH3Xi6XY/ny5Vi7di2ioqIQHh5usK/bhsoeqBxO6dmzJzZs2GCwo3tTyl4wZLRiRehMGsrl2kNnGKbiCHNBgFeV0CRTfH1t2QtUdBtA3790aWlpmDBhAmxtbY3ixJIhi05paSn++9//4tChQ/j+++8xfPhwvbfBVIquoYseAFzLLMDGhHTE384Fg4qJB5Uqi/7gDs6IGNSWkyNMfb8+FV2O6OuXTqlUYv369Vi6dCk+//xzTJ06FTye4UeGjKHoxMXFYdKkSRg+fDiioqLQtKn+boRpDO+/Jg0Jodd14QWqptQVlctgKxLWOqXOlF6fii5H9PFL9/DhQ0ycOBFSqRQ7duxA27bcDO7Xh7EUncLCQsyaNQsJCQnYvn273q5NNpb3r0lN0YplD6/i2clNUBTlwuKV9mg2YhYEds0B6CZasTGjaEcTxLIstm7dip49e+Jf//oX/vjjD6MquMbEzs4O27Ztw9q1azFmzBjMmTOHIiOhPdpQUVqI3ENfwn5AGNxn7oWlazvk/rJctZzLaMPGjoquEXry5AlGjRqF6OhoxMfHY+7cuQaJYDQ1o0aNwrVr15CRkQE/Pz805m9pNUUblt65AItmrdDE6zUwAgvYvTYOsqcPIMvPAMBttGFjR0XXyOzbtw/dunWDr68vEhMT0alTJ0M3yaQ0a9YM+/fvx8KFCxEQEIDFixdDJtN9aImxqynaUJb7N4TN26j+z7MQQWDvCmnuI9VjXEUbNnZUdI1EZQTjZ599hqNHj+Lzzz+HhYWFoZtlkhiGwdixY3H16lVcunQJvXv3xo0bNwzdLL2qMVpRVg6eZZMqj/Esm4CV/jMsw1W0YWNHRdcIHD16FF27doWbmxuSkpLQs6f6UGdSN6+88gp+/fVXREREYPDgwfjmm28aTWRkTdGKPKGoWoyhUloK5oXsg4rtNL5vCVyjomtARUVF+L//+z989NFH2LNnD1auXAkrK6uan0hqjWEYvPfee7h48SKOHTuGgQMHNorIyJqiFYXOrSF7+kD1f6W0HPLn2bBwbvXSdown8N5cUNE1kN9//x1dunSBQCBASkqKyd8Z19i1adMGv//+O9555x34+/vj22+/NerLvRqqpmhD6/Z9IM37GyVp58DKpSg8txfC5h4QOv0z4YaraMPGjq7TbYD6XKdZOZPq559/xvfff49//etfHLWOe8Z+naomt27dwoQJE2Bvb4+tW7fWe2afMb//PLEE/Zb/jpz4nVWiDQGoohX/uU73KSxa/O86XXsX1XqWAh7Ozxuil0kL5kbbdboU7ahHiYmJmDBhAnr06IFr167B0dGx5icRnevYsSPOnz+Pr7/+Gr6+vli5cqVBMyy4UJtoQyuPbmg5eZPaZVxGGzZ2VHTrKE8sQcyVTKRlF8H5nYWYuT8ZXq62CPbTPI1QIpHg888/x9atW7FhwwYEBQXpudXkZQKBAJ9++ilGjBiB8ePH49ChQ/juu+/QvHlzrc+rT/8byrRBbfHn3TyUyep+8pDLaMPGjoYXaqm+KU0pKSkYP348Wrdujc2bN8PVVfuN+EyJMX+9rguJRILFixdj+/bt2LhxIwIDA6utY8iUroYwtuyFxoKyFxqoPilNY3q44ZtvvsHq1auxYsUKTJgwway+vgLmU3QrnT9/HhMmTIC/vz/WrVuniow0hpSuhjD19psiKroNUJ8jBUs+A4vUo3ApuoNt27ahVatWNT/JBJlb0QWAkpISzJs3D7/88gu2bNmCXLsOZnGkqC3akFHIwBcI8Ia3K2fRio0NFd16SskowJjvE+s1JiZglIiZ+hq6tTKv2+e8yByLbqXTp09jUuRnEAyPhJKp+6kPY03pUhdtWJJ1FxlnDuC3wwcN3TyzQUW3nibvvIxTt3KqfCUrunIEJdfj1EblvYhhgGHeLtgUpvZzNwvmXHQBYOK2C4i/kwcw/1zOzsplyD+5EeUPr0JZLobAvgUcBo6HlWfVfjal/heLxXB3d8ft27drPJFIaoeiHeuhMqXp5ZoisHFSG5X3MkppMm15YgnOPyioUnABgFUqIGjaDK7jvob7rP2wHxCG3F+WQ15Q9WaZptT/NjY2GD16NPbu3VvzyqTBqOhqoCmlybqD+qg8dSilyXRp6n+ehQj2/UMhsHcBw/Bg3bYXBHYukGRXn1psSv0/fvx4/Pjjj4ZuRqNARVeDmlKaaoNSmkxXbftfUfIcsmePq2UWAKbV/4MGDUJOTk6jS2MzBCq6GtSU0lT77VBKkymqTf+zCjnyYqNg0/n1KpkFVbdjGv3P5/MRFhaGnTt3GropZo+KrgY1pTTVfjuU0mSKaup/llUi7+hKgC+A45tTtWzHdPo/PDwcu3fvbjTxl4ZCRVeDypSmhqCUJtPl5WoLCw13SGJZFvnH1kFRUgDntz8Bw1dfoE2t/318fODq6or4+HhDN8WsUdHVIMjPTe3jmqLy1JErFHirs4vaZcQ4sSyL33//HT9FfQyJRKp2nWcnoiHLz0DzoEXgCTXnLbAAgnzV70fGik6ocY+KrgaVKU0vz9wtPLcPj6ICUZQYg5Kb8XgUFYjCc/uqPZ8BYJmfjh6dvbBixQoUFhbqp+GkXmQyGfbu3YsePXpg2rRpGPPvEXizU8tq/S8vfArx1eOQ5txH5vpwPFoZhEcrgyC+WfXo0FRTusaMGYPY2FiIxWJDN8Vs0eQILRoyI61yRpIi9wGioqJw/PhxTJw4ETNmzKh3fquxMYfJEcXFxdiyZQvWrFmDNm3aIDIyEgEBAeDxeDrpf2ObkVYbo0aNQnBwMMaPH2/oppgsmhxRT13d7bEgwAtWwrp9TBVz773Qxc0e3bt3x+7du5GcnAylUomuXbsiPDwcKSkpHLWa1EZWVhb++9//ok2bNkhMTERMTAwSEhIwcuRI8HgV/a2L/jdF48ePN9urGPLEEmw6cw8z9ydj0o5LmLk/GZvO3NPrJBY60q0FXaY0FRQUYPPmzVi7di18fHwQGRmJN9980yQTyEzxSPfGjRtYuXIlfvnlF4SFhWHWrFlo06aN1uc0tpSu8vJytGzZEikpKXBzM60xaU30Hc1J2Qs6oC2lqbLTBndwrnVKk1Qqxd69exEVFQUej4fIyEiEhISY1G3XTaXosiyL+Ph4REVFITk5GdOnT8fUqVPrdOcOXfe/sZsyZQpeffVVzJs3z9BNaTBD/NGkoqtD6lKavFo0RZBv/e4cwLIsTpw4gaioKKSlpWHGjBmYPHky7OzsOGi9bhl70ZXL5Th48CCioqJQWlqKyMhIhIaGQiQS1Xubuu5/Y3X27FlMmTIFN27cMMlvYZUMFeJORddEJCUlYeXKlSZz0s1Yi25xcTG2bt2KNWvWwMPDo8rJMVI7LMvC09MTBw8ehJ+fn6GbUy8pGQUYNvkTPL96qloqoDTvEfKProL8+RMAgIVrWzi8OQUWzSqmczf0RCidSDMRvr6+2L17N5KSkuikWz1kZWVh/vz5aNOmDS5cuIADBw5UOzlGaodhGJO/Zjc6IR1Kawe1qYACG0c4/3s+3Gbug9uMPbBq1xt5v3yjWl4uV2BjQvUQI12gPdEItW7dGqtWrcL9+/fRqVMnBAQEYOjQoTh58qRRHlka2s2bNzFp0iR06tQJJSUluHjxIvbv349evXoZumkmLTw8HPv27YNMZhr5ES+qjGa1bq8+FZAnsvlfUlzF0AnD8FRHvQC30ZxUdI2Yvb095s2bhwcPHmDcuHGYPXs2unXrhp07d0IqVT9bqrGoPDkWEBCAN954A56enrh79y7WrVuHV1991dDNMwuenp5o164dTpw4Yeim1JmmaM6XPVodgkcr3sazU9/Btk9wlWVcRXNS0TUBFhYW+M9//oPr169j+fLl2L59Ozw9PREVFdXoZrrJ5XLs27cPPXr0QEREBAIDA/HgwQMsWLAATk5Ohm6e2THVIYbaRnO2mrUf7rMOwHHoVFi4eFZZxlU0JxVdE8IwDIYPH464uDj88ssvSEpKwquvvoqPP/4YGRkZhm4ep4qLi7FmzRq0bdsW3377LZYsWYKbN2/ivffea9DVCES74OBgnDhxAs+fPzd0U+qkLtGsPAsRbLr/C/lHV0FRUvDSdnQ/tEJF10T5+vpiz549SEpKgkKhMNuTbk+ePFGdHDt//jwOHDiAM2fOYNSoUXRyTA8cHBwwdOhQHDxoOjetzM7OxtPMh3V7EsuClUugKM6v8jAX0Zy015q4ypNu9+7dq3LS7dSpUyZ90q3y5JiPjw/EYjEuXryIAwcO0MkxAzD2acEsy+LatWv44osv0Lt3b3Ts2BFFf9+CgGE1pgKWPUiGNPseWKUCSkkpnsdtAU9kA2Gzfy7R5Cqak67TNTMSiUQ1043P5yMyMhJjxoyBUKj7v9i6vk6XZVkkJCQgKioKSUlJ+PDDDzF16lQaqzUwmUyGli1b4sKFC/D09Kz5CXoglUpx5swZxMbGIjY2Fnw+H6NHj8aoUaPQv39/FElZ9Fv+O3Lid6LwXNUbbtr1Gwuhc2sU/LELiuI8MAILWLRoB4dB/4FF83+mhFsKeDg/b0i9Jr3Q5IhGiGVZHD9+HFFRUbhz545qpputbc031KwtXRVduVyOmJgYREVFQSwWIzIyEmFhYTRWa0RmzJgBR0dHLF682GBtyM/Px7Fjx3DkyBGcPHkSHTt2VBVaHx+fajPnJu+8jFO3crRO/dWEYYBh3i7YFKa2btbi+VR0G7UrV65g5cqVOHHiBCZNmoQZM2bUO8gkTyxBzJVMpGUXYc/BQxgX/Da8XG0R7Ff3abBisRhbt27F6tWr0bp1a0RGRmLEiBE0VmuELl++jJCQECRevYmfkh4jLbsIReVy2IoE9e7/2rhz5w5iY2Nx5MgRJCcnY8iQIRg9ejRGjBgBFxftNwgwZDQnFV0CAHj48CHWrl2LHTt2YOTIkZgzZw66du1aq+fqMqXpyZMnWL9+PTZv3owhQ4Zgzpw56N27d73fF+He1YznCPz0O/DdOoPH43GW0iWXy3HhwgVVoS0uLsaoUaMwatQoDBkyBFZWVnXaHmUvEKPw/PlzfPfdd1i3bh06d+6MyMhIvPHGGxqDTXSV0pSamoqoqCgcPnwYoaGhmDlzptGMERLNKvu/TCZHxZQB9eqb0lVUVISTJ08iNjYWx44dg7u7u2rYwNfXt8HffChljBgNiUSCPXv2ICoqCkKhUBUv+eJJt4YeKbAsizNnzmDFihW4cuUKPvzwQ3zwwQd0csxEcHWk+OjRIxw5cgSxsbG4cOEC+vbti9GjR2PkyJFo1aqVDlpelb6jOanoEq1ePuk2c+ZMvP/++3hQqKz3mJhIyMN7HsXYt/EbiMVizJkzB+Hh4XRyzITockxUqVTiypUrqmGDx48fY8SIERg1ahSGDh2Kpk31c9fkF6M5dx/8GaHBgZxEc1LRJbX24kk3r/dWIovnjJf3EEVZMfKPrUX5w2TwrGzhMHACmvgMqrqSUgmrZ3fxzeh2dHLMRE3eeRk/7dwC8fW4atGIrEKGvNgVkDxJh6LoKVzGfglR6y6q5zIM8EYHZ7zl9BSxsbE4evQo7OzsVMMGffr0AZ+v4R73esJlNKm2oivg5BWJyfLz88OePXuQfCsd7+xIrVZwAeDZyW/B8IVwm74L0pz7eBrzGYTN28DCufU/K/F4ULp2RN/BQ6jgmqDKlC6+jRPs+oag7EESWFnVkCVLNx807fEW8g5/Xe35LAucvPEYacmb8XbAm/j444/Rrl07fTXfqNFvA1Hrr6eM2gkVSmk5Sm+fh/2AMPAsrCBy94F1294oeekW5AB3KU2Ee5UpXdYd1EcjMnwhbHu+BZG7D6Dhj6pIZImwRRswe/ZsKrgvoKJL1NKU0iR/9hgMjwehY0vVY8LmbSDL/bvaulylNBHu1TalSxuJnKX+V4OKLlFLU0qTUlYGxtK6ymM8S2sopWUatmN6Adikbild2rdD/f8yKrpELVuR+uF+ntAKrKRqgWUlpeBZqL9onYuUJsI9Tf1f9+1Q/7+Mii5Ry8vVFpaC6ruHwLElWKUCsmePVY9Jnz6A8MWTaP/DVUoT4Z6m/q8LHquAoCTHJG/3wyUqukStID/12Qw8CxGsO/RBwZ+7oZSWozwzFaXpf6GJz+Bq67IAgnzrl/FADKuy/zVFIwIAK5dVLAPAKuUVy164BIthGMRv/QouLi4YO3Ys9u7di4KCguov1shQ0SVqNbOxxMD2zlA3M9hxaARYuRSZ60ORF7sCTkMjql4uhorrNAd3cOYkBIVwr7L/C8/vw6OoQBQlxqDkZjweRQWi8Nw+AMDjzVPwKCoQiuJ8PN2/qOLfhU8BVPT/mz4tcPlcAm7cuIEhQ4Zgz549aNWqFYYMGYI1a9bg3r17hnyLBkOTI4hGhkxpIobHRf+Xlpbi9OnTqgkTTk5OqgkTvXv31uuECUNNjqAjXaJRV3d7LAjwgpWwbrtJxdx7Lyq4Jo6L/re2tsbo0aOxZcsWZGVlYdu2beDxeJg6dSpatGiBSZMm4dChQxCLxbp6G1XkiSXYdOYeZu5PhvM7CzFzfzI2nbnHya3WNaEjXVIjQ6Q0EeOhr/5/+PChKgTnr7/+wmuvvaYKwalv/nMlXUaT1gZlL5AG03dKEzEu+u7/wsJCnDhxArGxsfjtt9/g4eGhGobo3r27xhhSdSjakZi0F1OaisplsBUJOUlpIsbJEP0vl8tx7tw51f3QysvLVcHmgwcP1ppcRyHmhBDSACzL4vbt26qIyGvXruH1119X3cLH2dlZtW5KRgGGTf4Ez6+eqpaSJnmchoI/d0GanQ4wPIhadYbDm1MgsHEEQLfrIYQQtXJzc1U3qzx16hQ6deqkGoZYc6UUhw8fAsCoUtIqi27ZvctQysph1cYX4PHw7OQmKMTP4BLyOQBub0xJVy8QQkyWs7MzJkyYgJiYGDx9+hSLFi3Co0ePMGx0EE5ez4R1e/UpaVaePdDE6zXwLK3BE4rQ1G8kJI9vqZazLBB/O5eTqxqo6BJCzIKlpSWGDRuG6OhoLNgaCwuL2uc+SDJuQtis6m2CuIompaJLCDE7adnFkNZyTof06QMUntsLh8ETqzzOVTQpFV1CiNmpbTSl7HkWnh5YDIc3JkPk3knNdnQf1kNFlxBidmoTTSkvfIqcvZ/Crt8Y2HQaomE7uo+mpKJLCDE7ldGUmlLS5MV5yNn7CZr6jUDT7gFqt8FVNCndmJIQYnaC/Nyw+vQdFJ7bh8Jze1WPl9yMh12/sQDDQF6QjcKze1F49p/lrebEqP7NVTQpFV1CiNmpjKY8pQiFff9QtevYvzZO4/O5jCalokuIHuWJJYi5kom07CIUlcthKxLAy9UWwX40jVrXpg1qiz/v5tUrmlIk4CNiUFsOWkVFlxC90J5ylY3Vp+/oNOWK/BNNWb/sBe6iSanoEsKxmlKuKhO7Tqbm4I87eRSNqUOVn6MxRZNS0SWEQ3VJuWJZoEymwLJjFdNRqfDqRpi/B7q42RtNNCkVXUI4kpJRgGXH0ur01RYAymRKLDuWhi5u9pRNrCNd3OyxKayHUUSTUtElhCPRCel4mngY4utx1aIFAUApK8fz37ehNO0sWKUcFs5t4Bq2HABQLldgY0J6vVOuiHpONpaYMsDToG2goksIB/LEEpy5kwu+jRPs+oaoogVf9Oz4BrBKBV55/1vwRDaQPn2gWvZiyhVd1WBeaEYaIRyIuVKRTmXdQX20oCw/E6V3/4LT8OngW9uB4fFh6Vr1EiWuUq6IYdGRLiEcSMsuqnJZ2MskWbchsGuOgj93o+RmPPg2DrDrNw5NvPqp1uEq5YoYFh3pEsKBmlKuFMX5kOX+DZ6lNdw+3AHHN6ci/9fVkOVlvLQd3adcEcOioksIB2pKuWIEFgBPALt+Y8DwhRC16gxRq84oe5D00nZ0n3JFDIuKLiEcqEy50kTY3KPGbXCVckUMi4ouIRwI8qtIp9IULShy7wSBrTMKLxwAq1SgPDMV5Rk3YPWqr2obXKVcEcOiE2mEcKAy5erA5lVVogMrowXt+4fC+Z1Pkf/bOhQlxkBg2xzNRsyC0MkdALcpV8SwqOgSwpGKlKvxsH9NfbSghXNrtBi/Uu0yLlOuiGHR8AIhHKlMubIS1u3XjOuUK2JYdKRLCIeMMeWKGBYVXUI4ZmwpV8SwqOgSogfGlHJFDIuKLiF6ZAwpV8Sw6EQaIYToERVdQgjRIyq6hBCiR1R0CSFEj6joEkKIHlHRJYQQPaKiSwghekRFlxBC9IiKLiGE6BEVXUII0SMquoQQokcMqyVrjmGYXAB/6685hBBiFlqzLOusboHWoksIIUS3aHiBEEL0iIouIYToERVdQgjRIyq6hBCiR1R0CSFEj/4fY3ggeLmgQ3EAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "nx.draw_networkx(gex, pos=nx.get_node_attributes(gex, 'pos'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O atributo `degree` de um grafo NetworkX dá informações sobre o grau de cada um dos vértices:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "DegreeView({'0': 3, '1': 3, '2': 3, '3': 3, '4': 4, '5': 3, '6': 4, '7': 3, '8': 3, '9': 1, '10': 1, '11': 3, '12': 2, '13': 2, '14': 1, '15': 1, '16': 0, '17': 0, '18': 0})" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gex.degree" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Podemos calcular o histograma dos graus:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAMKklEQVR4nO3db4hl9X3H8c8nuyvqarDUS7Cu00lIEESIysX+WRCiRtQVkwd5oGAgRZgnaapNIayPJM8slJA+CIVBbRK0SuofKC4xClGCkKyZWdc/62hJ7SauptmREHTbUqv99MG9o5vxrnN2vb97vzv3/YJh75175u73sOybw++eM8dJBACo62PTHgAA8OEINQAUR6gBoDhCDQDFEWoAKG5rizc9++yzMz8/3+KtAWBTWl5efiNJb9RrTUI9Pz+vpaWlFm8NAJuS7V8e6zWWPgCgOEINAMURagAojlADQHGEGgCKI9QAUFynUNv+a9sHbL9g+z7bp7YeDAAwsGGobZ8r6a8k9ZNcKGmLpBtaDwYAGOi69LFV0mm2t0o6XdLr7UYCABxtwysTk7xm++8k/UrSf0t6LMlj67ezvSBpQZLm5ubGPSdwUpvfvWfaI0zcwTt2TXuETaPL0scfSPqCpE9K+iNJ223ftH67JItJ+kn6vd7Iy9UBACegy9LHlZL+Pclqkv+V9JCkP287FgBgTZdQ/0rSn9o+3bYlXSFppe1YAIA1G4Y6yV5JD0jaJ+n54c8sNp4LADDU6decJrld0u2NZwEAjMCViQBQHKEGgOIINQAUR6gBoDhCDQDFEWoAKI5QA0BxhBoAiiPUAFAcoQaA4gg1ABRHqAGgOEINAMURagAojlADQHGEGgCK63Jz2/Nt7z/q603bt05iOABAhzu8JHlZ0kWSZHuLpNckPdx4LgDA0PEufVwh6d+S/LLFMACADzreUN8g6b4WgwAARuscatunSLpe0j8f4/UF20u2l1ZXV8c1HwDMvOM5or5G0r4kvxn1YpLFJP0k/V6vN57pAADHFeobxbIHAExcp1DbPl3S5yU91HYcAMB6G56eJ0lJ/kvSHzaeBQAwAlcmAkBxhBoAiiPUAFAcoQaA4gg1ABRHqAGgOEINAMURagAojlADQHGEGgCKI9QAUByhBoDiCDUAFEeoAaA4Qg0AxRFqACiOUANAcV1vxXWW7Qdsv2R7xfaftR4MADDQ6VZckv5e0qNJvmT7FEmnN5wJAHCUDUNt++OSLpP0FUlK8rakt9uOBQBY02Xp41OSViX9o+1nbN9pe/v6jWwv2F6yvbS6ujr2QQFgVnUJ9VZJl0j6hyQXS/pPSbvXb5RkMUk/Sb/X6415TACYXV1CfUjSoSR7h88f0CDcAIAJ2DDUSf5D0qu2zx9+6wpJLzadCgDwnq5nfXxN0r3DMz5ekfQX7UYCABytU6iT7JfUbzwLAGAErkwEgOIINQAUR6gBoDhCDQDFEWoAKI5QA0BxhBoAiiPUAFAcoQaA4gg1ABRHqAGgOEINAMURagAojlADQHGEGgCKI9QAUByhBoDiOt3hxfZBSW9JelfSO0m42wsATEjXeyZK0ueSvNFsEgDASCx9AEBxXUMdSY/ZXra9MGoD2wu2l2wvra6ujm9CAJhxXUO9M8klkq6R9FXbl63fIMlikn6Sfq/XG+uQADDLOoU6yevDPw9LeljSpS2HAgC8b8NQ295u+8y1x5KukvRC68EAAANdzvr4hKSHba9t/09JHm06FQDgPRuGOskrkj47gVkAACNweh4AFEeoAaA4Qg0AxRFqACiOUANAcYQaAIoj1ABQHKEGgOIINQAUR6gBoDhCDQDFEWoAKI5QA0BxhBoAiiPUAFAcoQaA4gg1ABTXOdS2t9h+xvYjLQcCAPy+4zmivkXSSqtBAACjdQq17R2Sdkm6s+04AID1utyFXJK+Lekbks481ga2FyQtSNLc3NxHn2yGzO/eM+0RJu7gHbumPQJw0tjwiNr2dZIOJ1n+sO2SLCbpJ+n3er2xDQgAs67L0sdOSdfbPijpfkmX276n6VQAgPdsGOoktyXZkWRe0g2SfpzkpuaTAQAkcR41AJTX9cNESVKSJyU92WQSAMBIHFEDQHGEGgCKI9QAUByhBoDiCDUAFEeoAaA4Qg0AxRFqACiOUANAcYQaAIoj1ABQHKEGgOIINQAUR6gBoDhCDQDFEWoAKI5QA0BxXe5Cfqrtp20/a/uA7W9OYjAAwECXW3H9j6TLkxyxvU3SU7Z/mORnjWcDAKhDqJNE0pHh023Dr7QcCgDwvk43t7W9RdKypE9L+k6SvSO2WZC0IElzc3MnPND87j0n/LMAsBl1+jAxybtJLpK0Q9Klti8csc1ikn6Sfq/XG/ecADCzjuusjyS/k/SkpKubTAMA+IAuZ330bJ81fHyapCslvdR6MADAQJc16nMkfW+4Tv0xST9I8kjbsQAAa7qc9fGcpIsnMAsAYASuTASA4gg1ABRHqAGgOEINAMURagAojlADQHGEGgCKI9QAUByhBoDiCDUAFEeoAaA4Qg0AxRFqACiOUANAcYQaAIoj1ABQHKEGgOK63DPxPNtP2F6xfcD2LZMYDAAw0OWeie9I+psk+2yfKWnZ9uNJXmw8GwBAHY6ok/w6yb7h47ckrUg6t/VgAICBLkfU77E9r8GNbveOeG1B0oIkzc3NjWE0bGbzu/dMewQ0Nov/xgfv2NXkfTt/mGj7DEkPSro1yZvrX0+ymKSfpN/r9cY5IwDMtE6htr1Ng0jfm+ShtiMBAI7W5awPS7pL0kqSb7UfCQBwtC5H1DslfVnS5bb3D7+ubTwXAGBoww8TkzwlyROYBQAwAlcmAkBxhBoAiiPUAFAcoQaA4gg1ABRHqAGgOEINAMURagAojlADQHGEGgCKI9QAUByhBoDiCDUAFEeoAaA4Qg0AxRFqACiOUANAcV3umXi37cO2X5jEQACA39fliPq7kq5uPAcA4Bg2DHWSn0j67QRmAQCMMLY1atsLtpdsL62uro7rbQFg5o0t1EkWk/ST9Hu93rjeFgBmHmd9AEBxhBoAiutyet59kn4q6Xzbh2zf3H4sAMCarRttkOTGSQwCABiNpQ8AKI5QA0BxhBoAiiPUAFAcoQaA4gg1ABRHqAGgOEINAMURagAojlADQHGEGgCKI9QAUByhBoDiCDUAFEeoAaA4Qg0AxRFqACiuU6htX237Zdu/sL279VAAgPd1uWfiFknfkXSNpAsk3Wj7gtaDAQAGuhxRXyrpF0leSfK2pPslfaHtWACANRve3FbSuZJePer5IUl/sn4j2wuSFoZPj9h++QRnOlvSGyf4sycr9nnzm7X9lWZwn/23H2mf//hYL3QJtUd8Lx/4RrIoafE4hhr9l9lLSfof9X1OJuzz5jdr+yuxz+PUZenjkKTzjnq+Q9Lr4x4EADBal1D/XNJnbH/S9imSbpD0L23HAgCs2XDpI8k7tv9S0o8kbZF0d5IDDWf6yMsnJyH2efObtf2V2OexcfKB5WYAQCFcmQgAxRFqACiuTKhn8TJ123fbPmz7hWnPMgm2z7P9hO0V2wds3zLtmVqzfartp20/O9znb057pkmxvcX2M7YfmfYsk2D7oO3nbe+3vTTW966wRj28TP1fJX1eg9MBfy7pxiQvTnWwxmxfJumIpO8nuXDa87Rm+xxJ5yTZZ/tMScuSvriZ/51tW9L2JEdsb5P0lKRbkvxsyqM1Z/vrkvqSPp7kumnP05rtg5L6ScZ+kU+VI+qZvEw9yU8k/Xbac0xKkl8n2Td8/JakFQ2ufN20MnBk+HTb8Gv6R0eN2d4haZekO6c9y2ZQJdSjLlPf1P+BZ53teUkXS9o73UnaGy4B7Jd0WNLjSTb9Pkv6tqRvSPq/aQ8yQZH0mO3l4a/UGJsqoe50mTo2B9tnSHpQ0q1J3pz2PK0leTfJRRpc1Xup7U29zGX7OkmHkyxPe5YJ25nkEg1+0+hXh0ubY1El1FymPiOG67QPSro3yUPTnmeSkvxO0pOSrp7yKK3tlHT9cM32fkmX275nuiO1l+T14Z+HJT2swZLuWFQJNZepz4DhB2t3SVpJ8q1pzzMJtnu2zxo+Pk3SlZJemu5UbSW5LcmOJPMa/F/+cZKbpjxWU7a3Dz8gl+3tkq6SNLazuUqEOsk7ktYuU1+R9IPGl6mXYPs+ST+VdL7tQ7ZvnvZMje2U9GUNjrD2D7+unfZQjZ0j6Qnbz2lwQPJ4kpk4XW3GfELSU7aflfS0pD1JHh3Xm5c4PQ8AcGwljqgBAMdGqAGgOEINAMURagAojlADQHGEGgCKI9QAUNz/A6DXyMfkifkRAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "gex_deg = list(dict(gex.degree).values())\n", "plt.hist(gex_deg, bins=range(6));" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Caminhadas e distâncias" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Uma **caminhada** é um passeio pelos vértices do grafo através de arestas que conecatam esses vértices:\n", "$$(a_1, a_2, a_3, \\ldots, a_L)$$\n", "onde $a_i \\in V$ com $(a_i, a_{i+1})\\in E$.\n", "\n", "Neste caso, $L-1$ é o **comprimento** da caminhada.\n", "\n", "**Caminho mais curto** entre os vértices $v_i$ e $v_j$ é uma caminhada \n", "$$(a_1, a_2, a_3, \\ldots, a_L)$$\n", "para a qual $a_1 = v_i$, $a_L = v_j$ e não existe outra caminhada entre esses dois vértices com comprimento menor do que $L-1$.\n", "\n", "É possível que entre dois vértices existam várias caminhadas com o comprimento mínimo.\n", "\n", "A função `all_pairs_shortest_path_length` retorna um iterador que permite verificar a distância de um vértice para todos os outros:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From 0 : {'0': 0, '1': 1, '2': 1, '3': 1, '4': 2, '8': 2, '5': 3, '6': 3, '7': 3, '9': 3}\n", "From 1 : {'1': 0, '0': 1, '3': 1, '4': 1, '2': 2, '5': 2, '6': 2, '7': 2, '8': 3, '9': 4}\n", "From 2 : {'2': 0, '0': 1, '3': 1, '8': 1, '1': 2, '6': 2, '9': 2, '4': 3, '5': 3, '7': 3}\n", "From 3 : {'3': 0, '0': 1, '1': 1, '2': 1, '4': 2, '8': 2, '5': 3, '6': 3, '7': 3, '9': 3}\n", "From 4 : {'4': 0, '1': 1, '5': 1, '6': 1, '7': 1, '0': 2, '3': 2, '8': 2, '2': 3, '9': 3}\n", "From 5 : {'5': 0, '4': 1, '6': 1, '7': 1, '1': 2, '8': 2, '0': 3, '3': 3, '2': 3, '9': 3}\n", "From 6 : {'6': 0, '4': 1, '5': 1, '7': 1, '8': 1, '1': 2, '2': 2, '9': 2, '0': 3, '3': 3}\n", "From 7 : {'7': 0, '4': 1, '5': 1, '6': 1, '1': 2, '8': 2, '0': 3, '3': 3, '2': 3, '9': 3}\n", "From 8 : {'8': 0, '2': 1, '6': 1, '9': 1, '0': 2, '3': 2, '4': 2, '5': 2, '7': 2, '1': 3}\n", "From 9 : {'9': 0, '8': 1, '2': 2, '6': 2, '0': 3, '3': 3, '4': 3, '5': 3, '7': 3, '1': 4}\n", "From 10 : {'10': 0, '11': 1, '12': 2, '13': 2}\n", "From 11 : {'11': 0, '10': 1, '12': 1, '13': 1}\n", "From 12 : {'12': 0, '11': 1, '13': 1, '10': 2}\n", "From 13 : {'13': 0, '11': 1, '12': 1, '10': 2}\n", "From 14 : {'14': 0, '15': 1}\n", "From 15 : {'15': 0, '14': 1}\n", "From 16 : {'16': 0}\n", "From 17 : {'17': 0}\n", "From 18 : {'18': 0}\n" ] } ], "source": [ "for i, dist in nx.all_pairs_shortest_path_length(gex):\n", " print('From', i, ':', dist)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Se você quiser saber um caminho com distância mínima, ao invés de apenas saber a distância mínima, use `all_pairs_shortest_path`." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From 0 : {'0': ['0'], '1': ['0', '1'], '2': ['0', '2'], '3': ['0', '3'], '4': ['0', '1', '4'], '8': ['0', '2', '8'], '5': ['0', '1', '4', '5'], '6': ['0', '1', '4', '6'], '7': ['0', '1', '4', '7'], '9': ['0', '2', '8', '9']}\n", "From 1 : {'1': ['1'], '0': ['1', '0'], '3': ['1', '3'], '4': ['1', '4'], '2': ['1', '0', '2'], '5': ['1', '4', '5'], '6': ['1', '4', '6'], '7': ['1', '4', '7'], '8': ['1', '0', '2', '8'], '9': ['1', '0', '2', '8', '9']}\n", "From 2 : {'2': ['2'], '0': ['2', '0'], '3': ['2', '3'], '8': ['2', '8'], '1': ['2', '0', '1'], '6': ['2', '8', '6'], '9': ['2', '8', '9'], '4': ['2', '0', '1', '4'], '5': ['2', '8', '6', '5'], '7': ['2', '8', '6', '7']}\n", "From 3 : {'3': ['3'], '0': ['3', '0'], '1': ['3', '1'], '2': ['3', '2'], '4': ['3', '1', '4'], '8': ['3', '2', '8'], '5': ['3', '1', '4', '5'], '6': ['3', '1', '4', '6'], '7': ['3', '1', '4', '7'], '9': ['3', '2', '8', '9']}\n", "From 4 : {'4': ['4'], '1': ['4', '1'], '5': ['4', '5'], '6': ['4', '6'], '7': ['4', '7'], '0': ['4', '1', '0'], '3': ['4', '1', '3'], '8': ['4', '6', '8'], '2': ['4', '1', '0', '2'], '9': ['4', '6', '8', '9']}\n", "From 5 : {'5': ['5'], '4': ['5', '4'], '6': ['5', '6'], '7': ['5', '7'], '1': ['5', '4', '1'], '8': ['5', '6', '8'], '0': ['5', '4', '1', '0'], '3': ['5', '4', '1', '3'], '2': ['5', '6', '8', '2'], '9': ['5', '6', '8', '9']}\n", "From 6 : {'6': ['6'], '4': ['6', '4'], '5': ['6', '5'], '7': ['6', '7'], '8': ['6', '8'], '1': ['6', '4', '1'], '2': ['6', '8', '2'], '9': ['6', '8', '9'], '0': ['6', '4', '1', '0'], '3': ['6', '4', '1', '3']}\n", "From 7 : {'7': ['7'], '4': ['7', '4'], '5': ['7', '5'], '6': ['7', '6'], '1': ['7', '4', '1'], '8': ['7', '6', '8'], '0': ['7', '4', '1', '0'], '3': ['7', '4', '1', '3'], '2': ['7', '6', '8', '2'], '9': ['7', '6', '8', '9']}\n", "From 8 : {'8': ['8'], '2': ['8', '2'], '6': ['8', '6'], '9': ['8', '9'], '0': ['8', '2', '0'], '3': ['8', '2', '3'], '4': ['8', '6', '4'], '5': ['8', '6', '5'], '7': ['8', '6', '7'], '1': ['8', '2', '0', '1']}\n", "From 9 : {'9': ['9'], '8': ['9', '8'], '2': ['9', '8', '2'], '6': ['9', '8', '6'], '0': ['9', '8', '2', '0'], '3': ['9', '8', '2', '3'], '4': ['9', '8', '6', '4'], '5': ['9', '8', '6', '5'], '7': ['9', '8', '6', '7'], '1': ['9', '8', '2', '0', '1']}\n", "From 10 : {'10': ['10'], '11': ['10', '11'], '12': ['10', '11', '12'], '13': ['10', '11', '13']}\n", "From 11 : {'11': ['11'], '10': ['11', '10'], '12': ['11', '12'], '13': ['11', '13']}\n", "From 12 : {'12': ['12'], '11': ['12', '11'], '13': ['12', '13'], '10': ['12', '11', '10']}\n", "From 13 : {'13': ['13'], '11': ['13', '11'], '12': ['13', '12'], '10': ['13', '11', '10']}\n", "From 14 : {'14': ['14'], '15': ['14', '15']}\n", "From 15 : {'15': ['15'], '14': ['15', '14']}\n", "From 16 : {'16': ['16']}\n", "From 17 : {'17': ['17']}\n", "From 18 : {'18': ['18']}\n" ] } ], "source": [ "for i, dist in nx.all_pairs_shortest_path(gex):\n", " print('From', i, ':', dist)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Componentes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Componentes são subconjuntos de vértices com as seguintes caraterísticas:\n", "\n", "- Partindo de qualquer dos vértices do subconjunto, existe um caminho para qualquer outro vértice do subconjunto.\n", "- Não é possível adicionar outro vértice a esse subconjunto e manter a propriedade acima.\n", "\n", "No NetworkX, a função `connected_componets` retorna um iterador com todos os componentes conectados do grafo:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 {'9', '5', '1', '3', '8', '2', '4', '0', '6', '7'}\n", "4 {'12', '11', '10', '13'}\n", "2 {'15', '14'}\n", "1 {'16'}\n", "1 {'17'}\n", "1 {'18'}\n" ] } ], "source": [ "for c in nx.connected_components(gex):\n", " print(len(c), c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Se o grafo tem direção, então as coisas ficam mais complicadas. Para mostrar, vamos criar um grafo com direção." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "gexd = nx.DiGraph(gex)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "OutEdgeView([('0', '1'), ('0', '2'), ('0', '3'), ('1', '0'), ('1', '3'), ('1', '4'), ('2', '0'), ('2', '3'), ('2', '8'), ('3', '0'), ('3', '1'), ('3', '2'), ('4', '1'), ('4', '5'), ('4', '6'), ('4', '7'), ('5', '4'), ('5', '6'), ('5', '7'), ('6', '4'), ('6', '5'), ('6', '7'), ('6', '8'), ('7', '4'), ('7', '5'), ('7', '6'), ('8', '2'), ('8', '6'), ('8', '9'), ('9', '8'), ('10', '11'), ('11', '10'), ('11', '12'), ('11', '13'), ('12', '11'), ('12', '13'), ('13', '11'), ('13', '12'), ('14', '15'), ('15', '14')])" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gexd.edges()" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [], "source": [ "gexd.remove_edges_from([('0', '1'), ('1', '3'), ('2', '3'), ('4', '1'), \n", " ('4', '6'), ('5', '4'), ('5', '7'), ('6','8'), \n", " ('7', '4'), ('7', '5'), ('11', '12'), ('11', '13'), \n", " ('12', '13')])" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deVxU9f7H8ddsMCyyKCgIuC+4ICpmKqK4pIlL0tVyK7XM1Oomt/SnWd3KtEy9lvdq3qzMymuaV8wFd8TdVBS3RHMHFRERkGWGWc7vDy4IMuwww8D3+Xj4eMicM+d8Zr6HD2fOnPM+MkmSEARBEMxDbukCBEEQahPRdAVBEMxINF1BEAQzEk1XEATBjETTFQRBMCNlcRPd3NykJk2amKkUQRCEmiE6OjpJkiR3U9OKbbpNmjTh5MmTVVOVIAhCDSWTyW4WNU0cXhAEQTAj0XQFQRDMSDRdQRAEMxJNVxAEwYxE0xUEQTAj0XQFQRDMSDRdQRAEMxJNVxAEwYxE0xUEQTAj0XQFQRDMSDRdQRAEMyo2e0EoXlK6lg3R8cQmpJGm0eOkVuLr4cTIAG/qOdpaujzhCWK8hOpAVtw90rp06SKJwJvCzsSlsCzqCvsv3wdAqzfmTVMr5UhAcGt3pvVugb+Pi4WqFHKJ8RLMTSaTRUuS1MXkNNF0y+bnYzeYFxGLRm+guHt6ymSgViqYE+LLuG5NzFafUJAYL8ESimu64vBCGeT8Al8kS2cscV5JgiydgXkRFwHEL7IFiPESqiPRdEvpTFwK8yJiC/0C31o8osDPkj6bOp1CqDtgCgBZOiPzImLp4O1CB2/x0dVccsfr3rHfyDi3l+z7N3Bo0xu3IWF582RcPEjKoTUYHj1AWccNl94vQ6vuYryEKiXOXiilZVFX0OgNhR5v9M6GvH/eb/2MTGmDvW/PAvNo9AaWR10xV6kCj8dL6VgP5x4v4tjhmQLT9Y+SSNqymLp9J+ETth6XPq+QtHkRhowUMV5ClRJNtxSS0rXsv3y/2GOCAJmXDqOwd8bWp12BxyUJ9l26z4N0bRVWKeTKP172rXtg36o7cjunAvMYHj1ArnbArnkXZDIZ9i2eQqayRZ9yV4yXUKVE0y2FDdHxpZov/dxeHNr3RSaTFZomAzacKt1yhIopzXjZeLRAVc+HzD9/RzIayLx8FJlShcq9KSDGS6g64phuKcQmpBU4zcgUfWoi2rjz1Av5q8npGr2R2LuPqqI84QmlGS+ZXIFD+74kbV6IpM9GplDhNnwWchs1IMZLqDqi6ZZCmkZf4jzp5yOx9W6LysWjmOXoKrMsoQilGa+sGzGk7FtFgzGfYePRnOyEK9zfMBflCx9j06DZ/5YjxkuofOLwQik4qUv+25RxPhLH9n1LWI6qskoSilGa8cq+dw1bn3bYerZEJpNj69kKm4atyboRk285YryEyieabin4ejhhqyz6rdLEX8SQ/qDQWQv5qZVyfD3rVEV5whPyj5dkNCDps8FoAMmIpM9GMhqw9WyJNv4Psu9dAyA74SrauAvY1G8CiPESqo44vFAKIwK8WbLncpHTM87vxb5VD+S29kXOIwEjOntXQXXCk/KPV+rhX0g9vDZvWsaFfTgHjsYlaCzOPUdzP/wzDJkpKOyccO4+ErumnQExXkLVEZcBl9Lkn06y++K9Ek8bM8loRJn4B6+0NBAQEEDDhg3x9PSkXr16Js90ECquIuMlk8HAtg1YMc7kVZyCUKLiLgMWhxdK6Y3gFqiVinI9V22rJPXIr8yZM4ehQ4cSGBhIgwYN+OKLLyq5SiFXhcZLqWBacItKrkgQcoimW0r+Pi7MCfHFTlW2t8xOJef9kDac2hOOjY0NOp2OR48eoVKpGDduXBVVK1RkvOaE+IpLgIUqI5puGYzr1oQ5IW2wUyko6aiATAZ2KgVzQtowrlsTfHx8+Pvf/46dnR0KhQKtVsv48eNJT083T/G1UEXGSxCqimi6ZTSuWxPWTe7GwLYNsFXKUT9xVoNaKcdWKWdg2wasm9ytwC/wu+++S/369Wnbti0HDx7k3LlzuLm58fXXX5v5VdQeFRkvQagK4ou0CniQrmXDqXgOnb9O1OHf+cvQQbRp6MyIzkXfieD69euo1Wo8PT0xGo3MmDGDL7/8El9fXyIiImjcuLGZX0XtkTtesXcfkabR4aRW4etZp9jxEoTyECHmVWzgwIHs2rWL77//nokTJ5b5+Tdv3iQkJITY2FimT5/OwoULkcvFhxBBsFbi7IUqdOnSJfbv3w/Ae++9h15f8iWoT2rcuDEXLlzgn//8J8uWLcPT05OjR49WdqmCIFQDoulW0OzZs/MabXp6Oj/99FO5lzVt2jSSkpLw8/MjMDCQ0NBQsrOzK6tUQRCqAdF0KyAjI4PNmzejVCqRyWRotdoKfynm6OjInj172L59O1FRUbi6urJ27dqSnygIglUQTbcCHBwcSEhIIDIyEm9vb65fv87evXsrZdkDBw7kwYMHjB49mrFjx9KlSxcSExMrZdmCIFiOaLoV5ObmhoeHB0qlEi8vL+rUqbyQFLlczrfffsuFCxdITk6mYcOGfPLJJ5W2fEEQzE80XSvQpk0brl27xqeffsrcuXNp3Lgx586ds3RZgiCUg2i6VmTWrFncvXuXhg0b4u/vz/jx48t1toQgCJYjmq6VcXNz4+jRo6xfv57//ve/1KtXj61bt1q6LEEQSkk0XSs1YsQIkpOTGTBgAMOGDSM4OJi0tDQA1q1bh7ioRRCqp2oRYp6UrmVDdDyxCWmkafQ4qZX4ejgxMkBcnlkcGxsbfv31V06cOMFzzz2Hu7s7M2fO5IsvvqBBgwZcuXIFGxubQs8T77dgDWrqdmrRy4DPxKWwLOoK+y/fByhwB1e1Uo4EBLd2Z1rvFvj7VN+ovWvXrtG/f3+uXbtm0TpmzpzJwoULAbCzs2P27Nl88MEHedNryvst1Gw1YTutlpcB/3zsBqNWHmP3xXto9cZCt8zW/O+xXX/cY9TKY/x87IZlCrUi7du3z9uzzcrK4pNPPuHGjRuAeL8F61AbtlOLNN2fj91gXsRFsnSGEm+nIkmQpTMwL+KiVb7B5nTz5k0aNGiAvb09MpkMvV5Phw4d+HJbtHi/hWqvtvQFsx9eOBOXwqiVx8jSGQo8nrBmFto7l5DJc26xoqhTD6/J/y4wj51KwbrJ3apdqn91ObyQn0aj4fr16yxetYHdxnbIVKaPgWX8sZ+Uw2sxpN1H4eBKvcHTUfu0B6rv+y3UPGfiUhg4+T0exuwm+/4NHNr0xm1IGADpF/aRvGPZ45klCUmvxWPCl9h6tKiW22lxhxfM/kXasqgraPQGk9PqDphCHf+BRT5XozewPOqKuGFgKajVatq0aYPcbxDyP+5h6k9r1vXTPIz6Affn/g+bhq0wpCcXmC7eb8FclkVdwWjvinOPF8m6fgpJ9zjoybFdHxzb9cn7Of3sHlKP/IJNg+aA9W2nZj28kJSuZf/l++W7oy45Hyn2XbrPg3Rt3mM6nY7vv/+ew4cPV1KV1umHH34gKiqqwGN573cRz0k9tAbnwNHYevkik8lR1nFDWcctb7qp91sQKlvudmrfqgf2rbojt3Mqdv7083txaN83707a1radmrXpboiOL3Z6StRq4r4aQ8JPM9DcPGtyHhmw4VQ8Op2Ob7/9Fm9vbyZPnkx4eHgVVGw95s+fz4ABAwgICMhrvsW935LRgPbuFYyZqdxe8Rrxy8aTvOtrjLqCG27u+y0IVaWkvpCfPjURbdwFHNr3LfC4NW2nZj28EJuQVujbyFyufSaiqueDTKEi4+IBEv87F8+JS1G5ehaYT6M38s+fNvJG39kYjUZyj0mvWrWK7du3V/lrMCU7O5v4+HjatWtnkfVDzpdoOp2OU6dO0bdvX9RqNe1fW4jWvonJ+Q0ZKWDUk3npMA3GLUAmV3D/v5+SemQdrr1fzptPozcSe/eRmV6FUBsV1xeelH5+L7bebVG5eBR43Jq2U7M23TRN0TkBtg1b5/3f0a8fGX/sJ+vqSVRdhhaat07d+tStW5fk5GQMhpzjw+7u7nTo0KHyiy6F9PR07t69a7H1A9y6dYvs7GxkMhkymYyGDRvi4OIGRWSg536xVidgKErHujn/f2p4oaYLkKbRVWntQu1WXF94Usb5SJy7v1DEcqxjOzVr03VSl2F1MhkUcTSyW2d/ji5I5MSJE8yYMYMDBw4wZMgQFi1aVDmFllHu2QuWDBv39fXl6tWrTJgwgY8++ggvLy+mrzvN9Zg7JudXqB1R5Dt+WxwntaoySxWEAkrbFzTxf2BIT8a+dWARy7GO7dSsTdfXwwlbZUKhjxJGTTraO5dQN/IDuYKMiwfQxp2nbr/XCi1DrZTj65mTWfvUU08RFRVFdHQ0rq6uZnkN1dX3339P48aN8fLyynusqPc7l6Nffx5Fb8WuWQAolDw6+Rv2LZ4qMI9aKcfDzsCRI0e4e/cud+7c4datW4SEhNCnTx+TyxWEssjdTjXZOjAacv5JRiR9NsgVeaeRZpzbi32rHsht7QstI39fqO7M2nRHBHizZM/lQo9LRgMpB35GlxwPMjmqet64P/8+qnrehecFRnQu+HhAQEBVlWw1evToUeixot7vXM6BozBkpXH7m9eRKVU4+Abh3OPFAvNIwKI3RjIr/jq2tjmHJAwGA61atRJNV6gUudtp6uFfSD38+NNixoV9OAeOxiVoLJI+m4zYQ7iHzja5DFN9oboya9N1c7Sldyt3dl+8V+C0MYW9M54TlpT4fJkMvBVpHI3aTaNGjWjYsCH16tXLO3VEKMiQkYJD6g20dt5g4pbuMoWSegOnUW/gNJPPl8mgT2t3Zh2MxN/fPy/FTC6XY2dnR3Z2tslAHUEoi7y+YBiLS9BYk/PIlDY0Cltnetr/tlNrCcEx+2XAbwS3QK1UlOu5aqWC0z9/xtChQ+nevTve3t7Y2NiwcePGSq7SukmSxHfffYefnx+d7ZJQ25bvb6taqWBacAuaNGnC0aNHcXLKOX+yU6dOeafrTZ8+nTNnzlRm+UItVNG+MC24RSVXVHXM3nT9fVyYE+KLnapsq7ZTyZkT4sum75diY2NDZmYmWq0We3t7goODq6ZYKxQbG0twcDArVqxg165dfLvgA94PaVPu9zv30sq2bduye/du7OzsWLRoEVFRUXmNeNiwYXTq1ImlS5eSlJRUFS9LqOEq2heq0yXAJbFI4M24bk2YE9IGO5WCko4MyGQ5GQBzQtowrlsTevXqxXPPPYdKpUKpVCKXy9m3bx/FZUjUBlqtlo8//piePXvyl7/8hWPHjtGxY0egYu93fl27diUxMTHvj1zz5s355JNPuH79OosWLeL48eO0aNGCESNGsG3bNnErIaFMKms7re4smqd7Nj6F5VFX2HfpPjJyTnDOlZub2ae1O9OCWxT4S3bv3j2aNm1KQEAA8+fP5/XXX6dFixYsW7YMHx+fKqu3KJYOvDl48CCTJ0+mVatW/Otf/yryPSjv+10WqamprFu3jlWrVnHz5k1eeuklJkyYQJs2bcq1PKH2Mcd2WtWKC7yxaNPN9SBdy4ZT8cTefUSaRoeTWoWvZx1GdC46If7o0aM0bdoUDw8PtFotX3zxBV999RUffPABb775JgpF+Y4PlYelmu7Dhw+ZOXMm27dvZ+nSpYSGhpbqS8XyvN/lcfHiRX744Qd++uknGjVqxMSJExk1ahTOzs6Vtg6h5jLXdloVimu6SJJU5L+AgADJmly6dEkKDg6WunTpIp0+fdps67169arUtGlTs63PaDRKa9eulTw9PaVp06ZJKSkpZlt3eeh0Omnbtm3SiBEjJGdnZ2nMmDHS7t27JYPBYOnSBKFKACelIvpqjWq6kpTTkL7//nupfv360owZM6T09PQqX6c5m+7169elQYMGSe3bt5eOHDlilnVWpqSkJGnp0qVSp06dpEaNGknvv/++dOXKFUuXJQiVqrimW+PuBiyTyZg4cSLnzp3jzp07+Pn5sWPHDkuXVWF6vZ5FixbRpUsXevbsSXR0NN27d7d0WWVWr1493nrrLU6dOsXmzZt59OgR3bt3p3fv3vzwww+kp6dbukRBqFpFdWPJSvd0n7Rjxw6padOm0ujRo6WEhIQqWUdV7+meOHFC6tSpk9SvXz/pzz//rLL1WIpWq5U2btwoDR06VHJxcZEmTJgg7d+/XzIajZYuTRDKhdq0p/ukgQMHcv78eXx8fPDz8+O7776zmtPL0tPTCQsLY/DgwUyfPp3du3fTooX1nAReWjY2NoSGhrJ582YuXrxIu3btmDp1Ki1btuTTTz8lLi7O0iUKQqWp8U0XwN7engULFrB7926++eYbgoODiY2NtXRZxdq6dSvt2rUjOTmZCxcu8PLLL9eKy509PDx49913OX/+PP/5z3+4c+cOHTt2ZMCAAaxdu5asrCxLlygIFVIrmm4uf39/jhw5wogRIwgKCuLjjz9Gq61et/i4e/cuL7zwAmFhYXz//fesXr0aN7fSRTDWJDKZjK5du7J8+XJu377NK6+8wg8//IC3tzdTp07l999/t5pPLIKQX61qugAKhYK33nqL06dPc/r0aTp27MjBgwctXRZGo5EVK1bQoUMHWrZsydmzZ+nXr5+ly6oW1Go1o0aNYufOncTExODt7c24ceNo3749CxcuJCEhwdIlCkLpFXWwV6ohX6SVZOPGjZKXl5c0adIkKTk5uVzLqOgXaefPn5d69OghdevWTTp79my5l1ObGI1G6cCBA9LEiRMlFxcXaciQIdJ///tfSavVWro0QajdX6SVJDQ0lAsXLmBra0u7du345ZdfqvRj68GDBzl9+jQAGo2GDz74gODgYMaOHcvhw4fx8/OrsnXXJDKZjKCgIL7//nvi4uIYMWIES5cuxdvbm7fffpuYmBhLlygIJlWLy4Cri2PHjvHaa6/h4+PD8uXLadKkSbHzJ6Vr2RAdz8krd9iz/zDDBw/E18OJkQGmL1NMTU2lcePG2NnZsWrVKv7617/i5+fH0qVLC9zxQSi/q1evsnr1alavXk3dunWZOHEiY8aMqfBx8dyxjk1II02jx0mtLHasqwtrrdvaVfvshepEp9OxePFiFi1axKxZs5g+fTpKZcE82jNxKSyLusL+y/cBCtwOJzeQI7i1O9N6t8Df53Egx+uvv87q1avR6/XY2dmxZs0ahg0bZpbXVdsYjUYiIyNZtWoV27Zto3///kycOJGBAwcWGs/ilHesLc1a664pRNMth6tXrzJlyhQePHjAN998Q5cuOe/fz8duMC8iFo3eQHFHIWSynHDlOSG+jOvWhNOnT/P000+j0+XcsdTGxoaTJ0+KwwlmkJKSwvr161m1ahU3btzgpZdeYuLEiSUmn5V3rC3NWuuuSYprurX+mG5Rmjdvzq5duwgLC2PIkCGEhYXx7f7LzIu4SJau+I0ZQJIgS2dgXsRFfj52g8GDB6PT6bC1tc273c2xY8fM82JqORcXFyZPnszRo0eJjIxEJpPRr18/unXrxr///W9SU1MLPSencZVvrC3JWuuuTcSebikkJSUxefY8ol2CkClNHwfTJd/mzndv4uAbiNvQdwtMs1MpmO4n0alxPXx8fKhfv75ZoyeFwvR6PTt37mTVqlXs2bOHwYMHM3HiRPr27cu522mMWnmMLJ2h4HNS7vFg13Kyb8eCUoVD60Bc+0/Ou1st5Iz1usndLJLzeiYuxWTduqQ4Huz6mux7V1DYOePaZyL2rQveyNSSdddEYk+3gtzc3HDrNRZ5EQ0XIHnXCmw9W5qcptEbOK11p2vXrnh6eoqGWw0olUoGDx7Mhg0buHr1Kt26dWPmzJk0adKEN7/eguaJxgXwYNdyFPYueL/1Ew0n/hNN3HkendpWYB6N3sDyqCvmehkFLIu6gkZfsG7JaCDxv3Oxb/EUPm+vpe6zb5K0dTG65NsF5rNk3bWNaLqlkJSuZf/l+xT1mSDjj/3I1Q6oG/ubnC5JsO/SfR6kV6+r34Qc+ZPPfvp1E7eNzibHWp96D4c2PZEpbVA4umLXNABd0q0C85gaa0mS2LdvH0eOHKmUejdt2sSFCxcKPJa3jT5RuO5BHIb0ZOo8NRyZXIFdE39svdqScT6yxLqFqiGabilsiI4vcppRm0nKwTW49n212GXIgA2nil6OUD1c1DijUqlMTnPqMoyMPw5g1GnQP0oi69pJ7Jp2LjRf7ljnNtsuXbrQv39/lixZUik1hoWF0bFjR4YOHZrXfIvcRk3uKUhk379ZZN1C1SrfvblrmdiEtAKn3OSXcuAnHP0HoHRyL3YZGr2R2LuPqqI8oRIVN9ZqHz/SY3YS948XQDLi0L4fdq0KZxpr9EZWbdzFu4NnkpmZidGYs7yoqCh69+5d4Rrv3r2LXq9n69atbNu2jbp169L21QVo5R6F5lXV80Zh70za7//F6anhaG6dRXPrPOrGhc+aEduoeYg93VJI05i+q232vWtobp7B6annSrkcXWWWJVSBosZakozcW/8h9q170Oid/+L99n8watJJiVplcn6DwqZQKpxMJkMul1f4n6ll6uWm985lCiXuf3mfrKsnif/nS6QdD8ehTU8UdUxfLCK20aon9nRLwUlt+m3S3DqHPvUe8csnAiBla0AycjfpbTwnfmViOaZ/MYTqo6ixNmY9wpB2nzqdhyBTqlAoVTh26E/KgZ9w7fNKofl7dg3gxOI09u/fz7vvvsupU6cIDg5m/fr1Fa6xadOmxMfHM2TIED777DN8fX2Zvu40m2LumJzfpn5TPMZ+nvdzwk/v4tDedJiS2Earnmi6peDr4YStMqHQx07HjgNxaNMr7+e04xvRp96j7sA3Ci1DrZTj61mnymsVKqaosVbYO6N0bsCj0xE4Pf08UnYW6ef2oqrftNAy8o917969OXHiBAcOHMDWtnIuu126dCktW7bE19e3xLoBshOvo6rrhSQZeXQqAn36Qxz9+hdbt1B1RNMthREB3izZc7nQ43KVGlTqvJ9lKnXON9v2hW8xLgEjOntXZZlCJShqrAHcn59D8p5vSDu2AeQK1I38qNvvtULzmRrrXr16FZqvvIYOHVroseLqzji/j/QzO5GMBmx92tFg1FxkysJ7tGIbNQ/RdEvBzdGW3q3c2X3xXrFX+bgEjTX5uEwGfVq7i4ARK1DcWNs0aFbgY7oplhrr4up27fsKrn0LHwLJT2yj5iO+SCulN4JboFaW76IGtVLBtOCad2+zmspax9pa665tRNMtJX8fF+aE+GKnKttbZqeSMyfEt0ZdXpmUrmXF/qtMX3eaV1afYPq606zYf7XGnFhvrWNtrXXXNuLwQhnkJjHV1gSn4uMCE1iy53KNiQu01rG21rprExF4Uw5n41NYHnWFfZfuIyPnpPJcuVmlfVq7My24RY3Ze6itcYHWOtbWWndNIfJ0q8iDdC0bTsVz8s87HDh2kpD+wfh6OjGic81K5X8cF2j6Si1Tcj6ytqkRjRcej/Xe6FgOHjvJqOeHWcVY59Yde/cRaRodTmoVvp51qn3d1k403So2btw41qxZw7Zt2wgJCbF0OZWqqLjApC2L0Nw4g1GnQeHgilO3v1DHf2CBeWpiXOCAAQPYvXs3e/bsEXdrFookoh2rUEJCAhs2bADg3XffrdKbWlqCqbhAAKduI/Ga+j2N/vYr9Ud8QMqBn9AmFIwGrGlxgfHx8URFRQHwzjvv1LixFsxDNN0Kmjt3bl6gya1bt9i+fbuFK6o8RcUFAti4N853gr0MGTL0D+8WmKemxQV+9NFHeWN95coVIiMjS3iGIBQmmm4FZGZmsnLlSpRKJTKZDL1ez6effmrpsipNcZGWAA92LufWor9wZ+UUFI51sWte+NNUTYkLTEtLY/Xq1XmxjzVtrAXzEaeMVYCdnR179+7l2rVr/N///R8//vhjjbqVenExhwD1Bk6j7jOvo70di+bWOWSKwpeW1pS4QEdHR/bu3cuBAwf4+OOP2bx5Mz4+PpYuS7BCoulWgEwmIygoCC8vL+zt7RkwYIClS6pURcUc5ieTK1D7tCPjwr6cMJguhW8pXxPiAuVyOb169SI9PR25XF7jxlowH3F4QShSUTGHJhmNhY7pPl6OiAsUhFyi6QpFyokLLLyJGDJSyPhjP8bsLCSjgaxr0WRc3G/yHnEiLlAQChKHF4QijQjw5h+7TcQFymQ8Or2dBzuXg2RE6Vwf136vYd+qW6FZRVygIBQkmq5QpNtXYzHEnwWPtiB7vMersHcuMeIQAMlIz2Z1xZVPgpCPaLpCIUajka+++or58+fzt0+/ZPVtJZoyXAKcS4GRPUtnsr/Zp5VyQ0bBuiSla9kQHU9sQhppGj1OaiW+Hk6MDKj6S5Atue6SiKYrFHDnzh0mTJhAeno6v//+O82aNcOn3NkL/tTtNZvRo0czfvx4Pv74Y2xsbKqweqE6sGQanTUk4Ykv0oQ84eHhdO7cmcDAQA4cOECzZs2AnLjAOSFtsFMpeOIGt4XIZDmZC7lhNyEhIcTExHDu3Dl69OjBpUuXzPBKBEv5+dgNRq08xu6L99DqjYXO89b877Fdf9xj1Mpj/HzsRo1Yd1mIPV2B9PR0wsLCiIyMJDw8nO7duxeaZ1y3JnTwdilXXGD9+vXZsmULK1asoGfPnsyfP59JkyYVukW5YN3KkkYnSZClMzAv4iJAhdPoLLnushJNt5Y7ceIEY8eOpUePHpw+fRonJ6ci5+3g7cKKcV14kK7l1+h4Plz8Nc7uDRkyoG+JcYEymYypU6cSHBzMmDFj2LZtG99++y1ubm5V9dIEMzoTl8K8iFjuHfuNjHN7yb5/A4c2vXEbElZo3pRD/yH10H+oP+pTaNKReRGxdPB2KXcaXUnr1qfc4/aKV5Hlu4msU7e/QODoCq+7PMThhVrKYDDw2WefMXjwYD799FN++OGHYhtufvUcbfF+dJGkrf/g+uqZfPBMI17v1bxUX1C0adOGY8eO0apVK/z9/dm1a1dFX4pQDeSm0Skd6+Hc40UcOzxjcj7dw7tkXjqMwrFu3mMVTaMr7bp9wtbR6J0NNHpnAz/mi7MAACAASURBVC6Boytl3eUhmm4tdPPmTfr27cuuXbuIjo7mhRdeKNPzJUkqEGP5xRdflOn5tra2fPHFF/z444+8+uqrhIWFodFoyrQMofrIn0Zn37oH9q26I7cz/Qc8efcKXIMngPzxh+yi0uiOHDnCzZs3AXj48CG7du3KS3krz7pNsUQSnmi6tczatWt56qmnGDx4MHv27ClXaMu2bdu4ceMGkLPH/NVXX5GcnFzm5fTr148zZ84QFxdH165dOXfuXJmXIVheSWl0uTJiDyGTK7Fr/lShafnT6A4cOEDXrl0JDAzk559/BmDv3r08++yztGrVio0bN+Y139KuG+D28onELxtP0rYvMWSmmly3OYhjurVEamoqb775JidOnGD79u0EBASUe1lXrlzB09OTuLg47Ozs8PDw4ObNm9StW7fkJz+hbt26/Prrr/zwww/07duXDz74gLfeekt8yWZFSkqjAzBmZ5GyfzX1X5xrcrpGb+THzXuZPfwp0tLSMBhygvPXrl1LTEwM8fHxKBQKrl69ygsvvIBarea5554jufUwtHrHYtctt3fCY/wSbBo0w5iVRvKur0nasogG/6vF3El4Yk+3Fjh06BAdO3bE0dGR6OjoCjVcgOnTp3P9+nW8vb156aWX+PPPP+nUqVO5lyeTyZg4cSJHjx7lP//5DyEhISQkJFSoRsF8SpNGl3JwDQ7t+qJy8ShynuRHWaSlpRU4hJCUlMSlS5e4fft23uNGo5HMzEwuXrzIg7SMEtctt7HD1rMlMrkChYMrdZ+Ziub6aYzazHyvwXxJeKLp1mA6nY4PP/yQESNG8NVXX/H111/j4OBg6bKK1KJFCw4ePMhTTz1Fp06d2Lx5s6VLEkqhNGl0mptneBS9hbh/jiPun+MwPEoiadPnpB7bkDfPs317k5mZyfLly3Fzc0OhUPDWW29x9uxZ/vGPfyCXy3F0dOTjjz8mNTWVU6dO0eOpcvyxz/0Qle+WKOZMwhOHF2qoK1euMG7cOFxcXIiJicHDo+g9jOpEpVLxySefMHDgQMaNG0dERASLFy+u1n8sarucNLoEtHojktEAuf8kI5I+G+QKGoyeB4bH99q7uzoM136TsGuW86krN43OxsaGKVOm8Morr/Djjz/SuXNnALp27crChQt59dVXqVOnTpnWnZ1wBbmtA8q6DTFq0kne/Q22jfyQqx0KrNtcRNOtYSRJ4ocffmDmzJl88MEHvPnmm8jl1veBJjAwkJiYGN58800CAgJYs2ZNhQ+LCFVjRIA3S/bkpNGlHv6F1MNr86ZlXNiHc+BoXILGFnySTI5c7Yjcxg4onEZnY2PDpEmT8n5u1KgR06dPL9e6VfW8ebj/R4yZKcht7FE36Yj7sJl585k7CU803RokOTmZ119/nUuXLhEZGYmfn5+lS6oQZ2dnfvrpJ9auXcugQYN45513ePfdd1EoFJYuTcjHzdGW3q3c2X3xHi5BYws3WBO8p32f93+ZLOdKxvIE0ZR23Q5tTQcuVWTd5WV9u0CCSZGRkfj7++Pt7c3x48etvuHmN3r0aE6cOEFERAT9+vUjLi7O0iUJT3gjuAVqZfn+GKqVCqYFt7DKdZeHaLpWTqvVMnPmTF566SW+++47lixZglqtLvmJVqZx48ZERkYycOBAAgICWL9+vaVLsgpJ6VpW7L/K9HWneWX1CaavO82K/Vcr/WIAfx8X5oT4YqcqW0vJSaPzrdBluJZcd3mIwwtW7OLFi4wZM4bGjRtz5syZGp9joFAomD17Ns888wxjxowhIiKCpUuXlvry5drEEhGHucEx8yJi0egN+U8OKEQmy9nLnBPiWymBM5Zcd1mJPV0rJEkSy5cvp1evXkybNo3w8PAa33Dz69KlC6dOncLGxoZOnTpx9OhRS5dUrVgy4nBctyasm9yNgW0bYKuUo37iHntqpRxbpZyBbRuwbnK3Sm16llx3WYg9XSuTmJjIK6+8QkJCAocOHaJ169aWLskiHB0d+eabbwgPDyc0NJQpU6bw/vvvo1TW7k26OkQc5k+j23Aqnti7j0jT6HBSq0pMo7PmdZdW7d5CrUxERASTJk1iwoQJbNy4UdyFAQgNDeXpp59mwoQJ9OrVi59//jkvfL22KU28YtaNGJJ3rcCQdh+bhq1wGxxGlnP9Kok4rOdoy+u9mlfa8qxl3SURhxesQFZWFm+++SZTp05l7dq1zJ8/XzTcfBo2bMiOHTt44YUXePrpp1m9enVeAlptUlLEoSEzlfvh83HpNQ6f6Wux9WjJ/d8WAJaJOKytRNOt5s6cOUOXLl1ISkoiJiZG3OCxCHK5nOnTp7N3714WLlzIqFGjePjwoaXLMpvSRBxmXj6KjVsjHHx7IlPa4NxzDLrE6+gexFkk4rC2Ek23mjIajfzjH/+gf//+zJo1i7Vr1+Lq6mrpsqq9Dh06cOLECRo0aIC/vz9RUVGWLsksShNxqLt/E1X9pnk/y23UKF08yL5/CzB/xGFtJY7pVkO3b99mwoQJZGZmcvz4cZo2bVryk4Q8dnZ2LF26lEGDBjFmzBhefvllPvnkkwofkklMTOT+/ftIkkRcXBwuLi4FcgAsqVTxijoNCnvnAo/JbR2QsrMA80cc1lZiT7ea2bhxI507dyYoKIj9+/eLhlsBgwYNIiYmhj/++IPu3bsTGxtb7mWlpqbi6enJ5MmT0el0NG/enJCQkEqstmJKE68oV6kLxBkCGLMzkf0v/yBnOeaLOKytRNOtJtLT05k0aRIzZszgt99+48MPP6z1pz9Vhvr16/Pbb7/x2muv0bNnT1asWFGuL9mcnZ0JCQlBp8tpSra2tkybNq2yyy230sQrqtwbo0u8nvezMVuD/mECNu6N8i3HfBGHtZVoutXA8ePH6dSpEwaDgZiYGLp162bpkmoUmUzGlClTOHjwIN988w3PPfcc9+/fL/NyPv/8c1SqnKbk6upa5nvLVaWciMOcX2fJaMiJNcwXcSgZDdi36k520k0yYg8j6bNJPbwWVf0mqOrl3LLJ3BGHtZVouhZkMBiYN28eQ4YMYf78+axataraHCOsiXLvRNymTRv8/f3ZsWNHmZ7frl07OnbsCMCCBQuqVdrZiIDH0YSph3/h1qLnSTu2gYwL+7i16HlSD/+Cwt4Z99D3SDnwE3FfjkJ755JFIw5rK/H51Yxu3brFkCFD2LFjBzqdjpdeegmlUsmpU6fw9hYbuznY2NiwYMECnn32WcaPH09oaCgLFixg586dfPnll0RGRhZ7f7a3336bl19+uVrt5ULpIw7tmnTEa/KKQo9bIuKwthJ7uhWQm+A0f99tjD0nl5jgNGPGDC5cuEBwcDABAQEMHTqUPXv2iIZrAX369CEmJoa7d+/SsWNHxo4dy9GjR9mwYYPJ+XPHeneGF43GzeedDWerJK2rIqwt4rC2khX3pUKXLl2kkydPmrEc61B8gpMcCQolOF24cIEuXbqg0WiQyWS89dZbfPXVV5Yov9I0adKEkJAQli9fbulSys1gMNC6dWuuXr0K5FzddvPmzbwvMcsz1pZUluyFXDkRh20sFgBTE8lksmhJkrqYmib2dMuovAlO48ePR6PRADkpYcuWLePWrVvmLl94wo8//si1a9fyfk5ISGDx4sWAZdO6ymtctybMCWmDnUpBSXexl8nATqUQDdfMxDHdMihvglNq2iNOnTqFm5sbnTp1olOnTvj5+VnNzSJrsgEDBrBs2TLOnj3LqVOnOH/+PIsWLcKr94sWT+sqr3HdmtDB24XlUVfYd+k+MnL+QORSK+VkaTS0qyvjs5cCzR7iXduJpltKuQlOZfnYBpClM/KvQ7eJuZUsNu5qyMvLi6lTpxZ47ExcCqNWHivXWFdFWld5lBRx+Nbgp7idlcanz54A73LcxlwoN9F0Syk3welJadFbiozRy5Wb4LRinMlDPEI1Y2qsJb2OB7uWo7kRg1GTjtLFE9feL2PXvOCYVrexNhVxqNPpmJqRgiRJ9O7dm927d/P0009bqMLaRxzTLYX8CU5PKipGLz+R4GQ9ihpryWhAWccNjzGf4xO2Dpde47j/2wL0KfcKzmcFYx0fH4+9vT0Ajx49onfv3pw7d87CVdUeoumWQnEJTkXF6D1JJDhZh6LGWm6jxiVoLEqXBshkcuxbdEXp3ABtQuEM2uo+1jdu3ECn0yGXy5HJZAwZMgRnZ+eSnyhUCtF0S6E0CU4lEQlO1qG0Y23IeIgu+XaB3IJc1X2sXVxcGDBgAH/961+RyWT88ssvNGpU+HUIVUM03VIoTYJT6ZYjEpyqu9KMtWTQk7R5EY5+/fJyCwovp/qOdadOndiyZQuLFy9GpVKxcuVKS5dUq4imWwqlSXAq3XJEglN1V9JYS5KRpK2LQaGk7jNTillO9R9ruVxOUFCQVV/cYo1E0y2F/AlO5SUSnKxDcWMtSRIPIpZiyEjBPfQ9ZArTDdqaxvr999/nwoULZGZmljyzUClE0y2F/AlOTyoqRu9J2TodPb3EGXrVyaNHjzhw4ABHjx4lOjqac+fOoYqLJjs72+T8yTuXoXsQR/0RHyJXFR0MY01pXb1798bBwYFFixZZupRaQ3SBUsif4PTkqUSph38h9fDavJ8zLuzDOXB0gZQnGdDAkETQU50YMWIEM2fOpEULES5iaVu2bOGll17C0dGR7OzsvMu0+/39F65qHck/1PrURNJjdoBCRfw/X8p7vO6zb+DYrk/ez9aY1jVo0CBWrVrFhx9+aOlSagXRdEvpjeAWHPwziSxdwb3Y4mL0cqlVCv79xvN4zhzK0qVL6datG8888wyzZs3C39+/KssWijFs2DCUSiVpaWkAKBQKNm/ejJdfj/9dkfZ4rJXO9Wk8a2uJy7TGtK4PP/wQPz8/EhMTqV+/vqXLqfHE4YVS8vdxYU6IL3aqsr1lOQlOvnTwdsHd3Z25c+dy7do1OnfuzKBBgxg8eDCHDh2qoqoFUzIzM5k0aRL16tVDkiSUSiV2dnbMmzePkJCQShlra9K+fXvc3Nz49NNPLV1KpcmN4py+7jSvrD5RYuyqOYmmWwaVleDk5OTEjBkzuHbtGsOGDWP8+PEEBQURERFRrvt3CaWTlJTEiBEjcHJyYuPGjcydO5fExERsbGzo168fM2c+votCbUvrev7551m/fr2ly6iwM3EpTP7pJIELIlmy5zKbYu4QGZvIppg7fLnnMj0WRPL6zyc5E5disRpFnm45nI1PKTbBSSLnuN604Bal2uvR6/X8+uuvfPbZZ8jlcmbNmsXIkSOr1e1gTLGWPN2bN28yadIk9u7di4eHB3PnzuXVV1/Nm37mzBlatmyZd2lsfpU91tXVnTt38PLy4vLly7Rs2dLS5ZRLTgpgLBq9weQl+7lkspzDQHNCfKvsj2Rxebqi6VZAUQlOIzp7l+uLFEmS2LZtG5999hn37t1j5syZjB8/Hlvb6vmlTHVvumfPnuW1117jxIkTNG3alCVLljBs2LByLauyx7o6atSoEUFBQaxZs8bSpZRZdQtvL67pIklSkf8CAgIkwfyMRqO0f/9+6dlnn5UaNmwoLVq0SEpLS7N0WYU0btxYmjp1qqXLKCQqKkpq27atJJPJJD8/P+ngwYOWLskqvPfee5Kzs7OlyyizmFsPJd8Ptkuuz7wu2Xi0kFAoJYf2/aTGs7ZKjWdtlTwnLZdsPFpIclsHSW7rIKkb+0uek5ZLjWdtlXw/2C6diXtY6TUBJ6Ui+qo4plsNyWQyevXqxfbt29m6dSvHjx+nWbNm/P3vf+fBgweWLq/a2rhxI02bNqVPnz64uLhw9uxZzp49S8+ePS1dmlWYNWsWaWlpHDt2zNKllEluFGdRiX9Kx7q4D5+N9/Rf8H77P9i1fJqk374AHkdxmpNoutVcp06dWLduHUeOHOHOnTu0bNmSsLAw4uOrb4qVuX3zzTd4eHgwcuRIWrduzY0bNzh8+DDt27e3dGlWpU6dOrRq1Yq5c+daupRSyx/FWVTin1zt+L90uJxvRGUyOfqHdwHLRHGKpmslWrZsycqVKzl37hxyuZwOHTrw6quvcvnyZUuXZhFGo5F58+bh4uLCtGnT6N27N/fv32fHjh0iMasCpkyZQmRkpKXLKLXiYlefdGvJi9xaGEry7n/j1H1k3uPmjuIUTdfKeHl5sXjxYv788098fHwIDAxk5MiRnDp1ymw1GI1GtFotkiRhMBjQas23l5Cdnc3f/vY3HB0dmTt3LqNGjeLRo0esW7eOunXrmq2OmuqNN94gOzub3377zdKllEpZYlcbha3DJ2w9dQdMwabB47tpmDuKUzRdK1WvXj0++ugjrl+/Tvfu3Rk2bBgDBw5k//79VX6u73vvvYdarebWrVusXLkStVpd5Rd4pKenM3HiRBwdHVm5ciVhYWGkp6ezYsUK7OzsqnTdtYlKpcLf358ZM2YQGBjI3//+d0uXVKyyxq7KbdQ4dhrEg63/wJDx+Fxdc0ZxiqZr5RwdHfnb3/7G1atXGTlyJJMmTSIwMJAtW7ZgNFYseL0oL774Yl6jkyQJNzc3unbtWiXrSkxMZPjw4bi4uLBlyxYWLFhAamoq8+bNQ6kUV7FXJq1Wy/Dhwzl37hx//vknR44cqfbpY1J2OeqTJCS9FsOjx19KmzOKUzTdGsLW1pZJkyYRGxvL9OnT+fDDD/H392fNmjXo9ZUTwp6rU6dO9OjRAwClUsknn3yCjY1Npa7j6tWr9O3bFw8PD06ePMmqVatISkoiLCwMuVxstlVBpVLx4MGDvItyVCpVtQtmMhqNHD9+nNmzZ+Pr68ueX1cjl3IyMopK/Mu6fprshKtIRgNGbSYP936LXO2Iyi0ngN7sUZxFnUsmifN0rZrRaJS2b98u9erVS2ratKm0fPlyKSsrq9KWf+rUKQmQ1Gq1pNVqK2250dHRUkBAgCSTyaSWLVtKERERlbZsoWQajUbq16+fJJfLJblcLu3YscPSJUnZ2dnS7t27pWnTpkleXl6Sr6+vNHv2bOn48ePSvdRMqdX7EVLjWVsl58DREjnJmnn/nANHS27DZ0nKut6STKWW5HZOkrpZgOT5yj/zzuNt9X6ElPRIU6k1U8x5uuKKtFrg8OHDfPbZZ0RHRzN9+nSmTp2Kk1PxN9IsDScnJ4KCgti2bVuFl7V3717efPNNLl26hL+/P19//TXdunWr8HKFssvOziYoKIjjx49z5swZOnToYPYaMjIy2LlzJ+Hh4URERNCiRQtCQ0MZPnw4vr6+Bead/NNJk7GrpSGTwcC2DVgxzvTFY+VV3BVp4qBYLRAYGMjWrVs5e/Ysn3/+Oc2aNWPKlCm8/fbbuLu7l3l5SelaNkTH03r8fPQe3kxfdxpfDydGBpT9kth169Yxc+ZM4uLiCAwMJDw8vNAvlWBeNjY2HD58mIYNG3LxWhxHHjoQm5BGmkaPk1pZ7rEuyYMHD9iyZQubNm1i3759dO3aldDQUD7//HO8vLyKfF5RsaulYYkoTrGnWwtdvXqVhQsXsn79esaNG8e7775Lo0aN2LdvH7NnzyYyMtJk+MuZuBSWRV1h/+X7AAVO1ckNfwlu7c603i3w9ykY/nLmzBnGjh3LkSNHcHJyYtmyZXz88cc8ePCAQYMG8e9//7vYXyzBvM7EpfDOdzu5qrHDRqUq01iXxa1bt9i0aRObNm0iOjqa/v37M3z4cIYMGYKrq2upl2NN2Qui6dZid+/eZcmSJXz33XcMHTqU48ePc/nyZYYPH86vv/6adwUPVCzB6eHDh7Rt25akpCR69erFyZMnyczM5MUXX+Rf//oXLi7Wm85VE+WNtc5AcZ/Yi0vrMhgM/Pnnn4U+tUiSxB9//MGmTZsIDw/nxo0bDB06lOHDh/PMM8+Y/GNf5rpFyphQ3T18+JCZM2fy7bffAqBWq/n88895++23gYrtRYzp2og+ffpw6NChvFPYpkyZwpIlS1Cr1ZX/YoQKqYw9Rp1Ox8iRI9mxYwcPHz7E1taW48ePEx4eTnh4OBqNhuHDhxMaGkpQUFClnvpXXaI4xTFdoViurq5cufI49EOj0TB9+nS8vLxo+XR/5kXElumXECBLZ+TTiIssfO+vnD1wIO9xlUpF+/btRcOths7EpZR7rOdFxNLB2wXf+vY899xz7N+/H7lczvPPP8+ZM2dwdXUlNDSUtWvX0rlz5wKfoipTB28XVozrkhfF+fPWfSjs6tCpbetqE8Upmq4AgJ+fH05OTtjY2KBSqbh9+zZZWVl5CU5PMmQ94kHEV2hunEZu54Rr7/E4tAsuME+WVk+WZ1eefjqRZs2akZ2djVarpU4d67g9eW2TO9Zp0VvIOLeX7Ps3cGjTG7chYQBIBh1JmxeivXsFQ1oiDUbPR90458wGjd7A0j2X+H3xJC5evIjBkLPN3Llzh6ioKFq1amXW11LP0ZbXezXn0qZleDt787cXXzTr+osjmq4AwNKlSws9lpSu5dMFkSaPjyXv+hqZQoX3Wz+Tfe8aiRs+RlW/KTbujfPmkcnl2DYLYNu/Z1h870IoXv60rtyIxKzrp5B0BW9Hb+vdjjpdniNp0+cFHpckiLp8n9vx95AkCUdHRwwGA1evXqV58+YIj4mmKxSpqAQnY7aGzEtHaDhpGXIbO9Q+7bBv8TQZF/ZhEzyhwLy5CU6v9xK/eNVZ/rG2b51ztaE24QoGXVLe4zKFCqennsv5wcRVgUqFgi9/O8pLXTy5fPkysbGxJCQkiCsInyCarlCkohKc9Mm3kcnlqOo+PsVLVb8p2lvnCs1r7gQnoXzKktZVlNyxtrdvTseOHenYsWMlVVeziKYrFKmoBCejLguZbcFTe+S29hizs4pYjvkSnITyKWtaV9HLqR5jHRMTw5YtWzh27BjOzs5kZGQwZsyYanGoQzRdoUhOatObh1xlh6Qt2GAlbSZyG9MRi+ZMcBLKp6ixLvtyCo61JElVdqZCcc6fP89HH32Ud5rizp07CQoKqhZNVxxsEYrk6+GErdLEsbu6XkhGA7rk23mPZSdeR5XvS7RcZk9wEsqlqLEuC1uljFtnjxIWFkbv3r3x9PTE2dk570wGcxo1ahT169fP+9nf35/evXubvQ5TRNMVijQiwNvk43IbNfatu5NycA3GbA2a+D/IvPI7Du36FJpXAkZ0Nr0cofrIP9ZFRSQCSHpdzjRAMupzpv3v9BaDQWLTkll8+eWXHDhwgISEBLy8vPKiIs1JqVTy2WefoVKpsLGxYdGiRRbZ4zZFXJEmFKuoBKfSnKdbVQlOQtXIHeuHB9aQenhtgWnOgaNxCRpL/PJXMKQlFpjmNeU7VK4NGNi2ASM9Uxk6dChZWVnIZDJsbGzyrj4LCQkx6znaer0eZ2dnXFxciI+PN2vTFZcBC+V2Ji6FUSuPlSvByU6lYN3kblV6uaVQeSprrA8dOsSzzz5LdnY2+/bt48KFC4SHh3P48GGCgoIIDQ1l6NChNGjQoApeRUGrV6+mQYMGPPvss1W+rvxE0xUqpLolOAlVp7LG+vjx4yxbtozVq1fnPZaamsr27dsJDw9n586d+Pn5ERoaSmhoKE2bNq3Ml5EXP2qOSEpTRNMVKqw6JTgJVcscY63RaIiMjCQ8PJzNmzfj4eGR14A7dOhQ7kMBFYkfrUyi6QqVorokOAlVz5xjbTAYOHr0aF4KGZB3HLhHjx6l/iKuOu0YiKYrVKrcBKfYu49I0+hwUquqTYKTULnMPdaSJHHu3Lm8Bnznzh2GDRtGaGgo/fr1KzKdrrodAhNNVxAEq3Tt2jV+++03wsPDOXv2LAMGDMg7E8LZ2Rl4/AXgvWObTKajaW/HknLwZ7ITroBMjrqRH67PvI7SsW6Vfdkrmq4gCFYvMTGRLVu2EB4ezoEDBwgMDGT48OEcUbTnwLUUMmKPgEyWl46W23Szrp7EqNNg17QzyOUk71qBIT2ZBi9+YpEbU4qLIwRBsAr169fn1VdfZevWrdy+fZuJEyey++Axoi4lIkk56Wj2rbojtyt4p2u75l1w8O2J3NYeuUpNnYAhaG9fBHIiKfddus+DdK3ZXodouoIgWJ06derwwgsv0P+198t8FxJt3AVUbo3yfs6NHzUX0XQFQbBaZY2kzE68Turhtbj2mZj3mLnjR0XTFQTBapUlklL38A6J6/+Oa//JqH3aP7Ec80VSiqYrCILVKm0kpT41kXtr38c5cBSO7fuaWI754kdF0xUEwWrlj6QsKh1N/yiJe2vfo07AYOp0Cim0DHPHj4oQc0EQrNaIAG+W7LkMQOrhXwqko2Vc2Idz4GiQydCnJJB6aC2phx5Pb/TOBsD88aOi6QqCYLXcHG3p3cqd3Rfv4RI0FpegsSbnc+k5xuTjMlnO5czmvJJSNF1BMANLp17VZG8Et+Dgn0nliqRUKxVMC25RBVUVTTRdQahCxadeJbBkz2WzpF7VZP4+LswJ8S1n9oKv2cOZRNMVhCpSUupVbnLXrj/uceBykojDrIDc9626pIwVRzRdQagCZUm9kiTI0hmYF5FzaapovOUzrlsTOni7VPv4UdF0BaGSnYlLYV5EbJk+6gJk6YzMi4ilg7eLyCMupw7eLqwY16Vax4+KpisIlWxZ1BUSj20i3UTMIIBRp+Fh5Pdkxh5CMuqxcW+Kx7gFAGj0BpZHXRE386ygeo62vN6ruaXLMEk0XUGoREnpWvZfvo/CsR7OPV7MixnML3nHv5CMBhq+9jVytSPZidfzpuVPvbL0HplQNcQVaYJQiTZE56RVFRUzqHsQT+afv1Pv2bdQ2Dsjkyuw9Sh4ypK5U68E8xJ7uoJQiUpKvdLeuYTSuT4pB9eQcWEfCkdXnAPH4OAbmDePuVOvBPMSe7qCUIlKSr0yPHqA7v5N5Lb2eL+5mrrPTOHBtiXokuKeWI75Uq8E8xJNVxAqUUmpVzKlDciVOAeOQqZQnK1/iwAAAXdJREFUoW7kh7qRH1nXTz2xHPOlXgnmJZquIFSi/KlXpqjqNylxGeZOvRLMSzRdQahEIwJy0qqKihlU+7RH6eRO6tH1SEYDmvg/0MSdx65Z57xlmDv1SjAv8UWaIFSi3NSr9d/8o0CMYG7MoEvQWNz/8j4Pti8l7dgGlE71cRschqqeD2CZ1CvBvETTFYRKlpN69TIuPU3HDNq4N8bz5cUmp1ki9UowL3F4QRAqWW7qlZ2qbL9elkq9EsxL7OkKQhWwptQrwbxE0xWEKmItqVeCeYmmKwhVyBpSrwTzEk1XEMygOqdeCeYlvkgTBEEwI9F0BUEQzEg0XUEQBDMSTVcQBMGMRNMVBEEwI9F0BUEQzEg0XUEQBDMSTVcQBMGMRNMVBEEwI9F0BUEQzEg0XUEQBDOSScVkzslksvvATfOVIwiCUCM0liTJ3dSEYpuuIAiCULnE4QVBEAQzEk1XEATBjETTFQRBMCPRdAVBEMxINF1BEAQz+n9feecNXs56zQAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "nx.draw_networkx(gexd, pos=nx.get_node_attributes(gexd, 'pos'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "No caso de grafos com direção, podemos ter um caminho do vértice $v_i$ para o $v_j$ mas não vice-versa. Por exemplo, no dígrafo acima podemos chegar do vértice 9 no vértice 6, mas não vice-versa. Porisso, introduzimos dois conceitos de componentes conectados:\n", "\n", "1. Um subconjunto de vértices é um componente **fortemente conectado** se é possível sair de qualquer vértice nesse componente e chegar em qualquer outro vértice.\n", "2. Um subconjunto de vértices é um componente **fracamente conectado** é existem caminhos ligando todos os vértices mas não necessariamente em ambas as direções." ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "4 {'4', '6', '7', '5'}\n", "6 {'9', '1', '3', '8', '2', '0'}\n", "2 {'11', '10'}\n", "1 {'12'}\n", "1 {'13'}\n", "2 {'15', '14'}\n", "1 {'16'}\n", "1 {'17'}\n", "1 {'18'}\n" ] } ], "source": [ "for c in nx.strongly_connected_components(gexd):\n", " print(len(c), c)" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 {'9', '5', '8', '3', '1', '2', '4', '0', '6', '7'}\n", "4 {'12', '11', '10', '13'}\n", "2 {'15', '14'}\n", "1 {'16'}\n", "1 {'17'}\n", "1 {'18'}\n" ] } ], "source": [ "for c in nx.weakly_connected_components(gexd):\n", " print(len(c), c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Métricas" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Métricas ou medidas são valores associados ao grafo, com o intuito de quantificar alguma característica sua.\n", "\n", "Dividimos as métricas em \n", "\n", "- Métricas de vértice, que associam um valor para cada vértice do grafo.\n", "- Métricas de grafo, que associam um valor para o grafo inteiro.\n", "\n", "As métricas de grafo pode ser baseadas sobre as métricas de vértice, como médias ou variâncias." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Grau" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Grau é uma das métricas mais simples de vértices.\n", "\n", "Podemos formar métrica de grafo calculando a média dos graus $\\langle k \\rangle$ ou a variância $\\langle k^2 \\rangle - \\langle k \\rangle^2$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Proximidade (closeness)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A **proximidade** é a média da distância de um vértice a todos os outros vértices do grafo.\n", "\n", "Essa definição só é válida quando o grafo tem apenas um componente, caso contrário não temos distância definida entre certos pares de vértices. Podemos extender essa mesma definição calculando as distâncias apenas entre pares que fazem parte de um mesmo componente. Se $d_{ij}$ é a distância (comprimento do caminho mais curto) entre os vértices $v_i$ e $v_j$, podemos definir:\n", "\n", "$$\\ell = \\frac{2}{n(n-1)}\\sum_{\\langle ij \\rangle} d_{ij},$$\n", "onde $\\ell$ é a distância média no grafo e a somatória deve ser feita apenas para os pares $ij$ que pertencem a um mesmo componente.\n", "\n", "A proximidade de um vértice $i$ é definida de forma equivalente como\n", "$$c_i = \\frac{n-1}{\\sum_j d_{ij}},$$\n", "onde a soma deve ser apenas entre os vértices $v_j$ que fazem parte do mesmo componente que o vértice $v_i$" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'0': 0.23684210526315788,\n", " '1': 0.25,\n", " '2': 0.25,\n", " '3': 0.23684210526315788,\n", " '4': 0.28125,\n", " '5': 0.23684210526315788,\n", " '6': 0.28125,\n", " '7': 0.23684210526315788,\n", " '8': 0.28125,\n", " '9': 0.1875,\n", " '10': 0.09999999999999999,\n", " '11': 0.16666666666666666,\n", " '12': 0.125,\n", " '13': 0.125,\n", " '14': 0.05555555555555555,\n", " '15': 0.05555555555555555,\n", " '16': 0.0,\n", " '17': 0.0,\n", " '18': 0.0}" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nx.closeness_centrality(gex)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O NetworkX não faz a generalização discutida acima para distância. O resultado é que ele só calcula a distância média se o grafo tiver apenas um componente conectado." ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "ename": "NetworkXError", "evalue": "Graph is not connected.", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mNetworkXError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0maverage_shortest_path_length\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mgex\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m~\\Anaconda3\\lib\\site-packages\\networkx\\algorithms\\shortest_paths\\generic.py\u001b[0m in \u001b[0;36maverage_shortest_path_length\u001b[1;34m(G, weight, method)\u001b[0m\n\u001b[0;32m 403\u001b[0m \u001b[1;32mraise\u001b[0m \u001b[0mnx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mNetworkXError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Graph is not weakly connected.\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 404\u001b[0m \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mG\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_directed\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mand\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mnx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_connected\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mG\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 405\u001b[1;33m \u001b[1;32mraise\u001b[0m \u001b[0mnx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mNetworkXError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Graph is not connected.\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 406\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 407\u001b[0m \u001b[1;31m# Compute all-pairs shortest paths.\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mNetworkXError\u001b[0m: Graph is not connected." ] } ], "source": [ "nx.average_shortest_path_length(gex)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Coeficiente de aglomeração (clustering coefficient)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O coeficiente de aglomeração quantifica a tendência de formação de triângulos no grafo, com três vértices $a, b, c$ e a presença de todas as arestas possíveis entre eles $(a, b), (a, c), (b, c)$.\n", "\n", "O coeficiente de aglomeração de um vértice $v_i$ é definido como a fração de triângulos existentes entre todos os possíveis do qual esse vértice participa. Se $v_i$ tem grau $k_i$, então o número de triângulos possíveis será\n", "$$\\frac{k_i (k_i - 1)}{2}.$$\n", "Se definimos $e_i$ como o número de arestas entre vizinhos de $v_i$, então o coeficiente de aglomeração de $v_i$ vale\n", "$$C_i = \\frac{2 e_i}{k_i (k_i - 1)}.$$\n", "\n", "Podemos definir a métrica de coeficiente de aglomeração médio como a métrica correspondente da rede:\n", "$$\\langle C \\rangle = \\frac{1}{n}\\sum_{i=1}^{n}C_i.$$" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'0': 0.6666666666666666,\n", " '1': 0.3333333333333333,\n", " '2': 0.3333333333333333,\n", " '3': 0.6666666666666666,\n", " '4': 0.5,\n", " '5': 1.0,\n", " '6': 0.5,\n", " '7': 1.0,\n", " '8': 0,\n", " '9': 0,\n", " '10': 0,\n", " '11': 0.3333333333333333,\n", " '12': 1.0,\n", " '13': 1.0,\n", " '14': 0,\n", " '15': 0,\n", " '16': 0,\n", " '17': 0,\n", " '18': 0}" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nx.clustering(gex)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.38596491228070173" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nx.average_clustering(gex)" ] }, { "cell_type": "code", "execution_count": null, "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.7.6" } }, "nbformat": 4, "nbformat_minor": 4 }