Ch4_TD_Corrigés.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Ch4-TD-Corrigés.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyPlLJYoNkCLWkRl634lTdrN",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/othoni-hub/ECG1/blob/main/Ch4_TD_Corrig%C3%A9s.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BcbmTQPILsdU"
      },
      "source": [
        "# **Ch4 - TD - Corrigés**\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=12Wo3LubGGT4qOvYFAuLP4CyCuwjKNVuk\" width=\"230\" height=\"150\" align = \"right\"/>\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "**O.Thöni - Lycée Saint-Charles Sainte Croix - LE MANS**\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lZGt3keXMCst"
      },
      "source": [
        "## **Ex1 : graphe des diviseurs**\n",
        "\n",
        "*source : \"Mathématiques appliquées et Informatique\", Bruno Grebille, Éd. Studyrama*\n",
        "### **1°) Constitution du graphe**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "O17Gi8Z7MHA_",
        "outputId": "4a365bda-9154-46fe-8d21-089703bf323c"
      },
      "source": [
        "E = set(range(7))\n",
        "#E = set((0,1,2,4,8,16,32))\n",
        "E"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{0, 1, 2, 3, 4, 5, 6}"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 1
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pHuKcRTSoj8M"
      },
      "source": [
        "def divise(i,j) :\n",
        "    '''fonction qui reçoit deux entiers i et j\n",
        "    et renvoie 1 si i divise j et 0 sinon'''\n",
        "    if i == 0 :\n",
        "        return False\n",
        "    else :\n",
        "        if j%i == 0 :\n",
        "            return True\n",
        "        else :\n",
        "            return False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "s7irR5FrMk1B",
        "outputId": "781c7287-84ee-4421-f898-cc36dfbbc110"
      },
      "source": [
        "V = set((i,j) for i in E for j in E if divise(i,j)) # graphe par compréhension\n",
        "                                                    # on a retiré 0 des i possibles, pour ne pas avoir de division par 0 ;)\n",
        "V"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{(1, 0),\n",
              " (1, 1),\n",
              " (1, 2),\n",
              " (1, 3),\n",
              " (1, 4),\n",
              " (1, 5),\n",
              " (1, 6),\n",
              " (2, 0),\n",
              " (2, 2),\n",
              " (2, 4),\n",
              " (2, 6),\n",
              " (3, 0),\n",
              " (3, 3),\n",
              " (3, 6),\n",
              " (4, 0),\n",
              " (4, 4),\n",
              " (5, 0),\n",
              " (5, 5),\n",
              " (6, 0),\n",
              " (6, 6)}"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1M9nqPJgOxTs"
      },
      "source": [
        "### **2°) Matrice d'adjacence**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MbrifV-cO1O9",
        "outputId": "e882f581-c052-40e6-b742-a4b361cc59cd"
      },
      "source": [
        "import numpy as np\n",
        "\n",
        "def matrice_adjacence(Ens) :\n",
        "    '''Fonction qui reçoit un ensemble d'entiers Ens\n",
        "    et qui renvoie la matrice d'adjacence A du graphe des diviseurs'''\n",
        "    l = len(Ens)\n",
        "    A = np.zeros((l,l),dtype=int)# On crée la matrice à la bonne dimension\n",
        "    for i in Ens:\n",
        "        for j in Ens: # on parcourt la matrice\n",
        "            if divise(i,j) :      # si le n° de ligne divise le n° de colonne, on met un 1\n",
        "                A[i,j] = 1\n",
        "    return A\n",
        "\n",
        "A = matrice_adjacence(E)\n",
        "A"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[0, 0, 0, 0, 0, 0, 0],\n",
              "       [1, 1, 1, 1, 1, 1, 1],\n",
              "       [1, 0, 1, 0, 1, 0, 1],\n",
              "       [1, 0, 0, 1, 0, 0, 1],\n",
              "       [1, 0, 0, 0, 1, 0, 0],\n",
              "       [1, 0, 0, 0, 0, 1, 0],\n",
              "       [1, 0, 0, 0, 0, 0, 1]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JuVTgWtRq-SB"
      },
      "source": [
        "\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=1R2skeFWCtZqyDiq4XKXwFanUP4sFzJxx\" width=\"550\" height=\"350\" />\n",
        "\n",
        "**outil de tracé :**\n",
        "\n",
        "https://wims.univ-cotedazur.fr/wims/fr_tool~geometry~graphviz.fr.html"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cahZhQiGuIFo"
      },
      "source": [
        "### **3°) Degré des sommets**\n",
        "Dans un graphe orienté, le **degré** d'un sommet est le nombre d'arcs qui en partent ou y arrivent (les boucles comptant double)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cmzOxMzrwrpQ"
      },
      "source": [
        "def degre(E) :\n",
        "    ''' Fonction qui reçoit un ensemble, \n",
        "    calcule la matrice d'adjacence du graphe des diviseurs dans cet ensemble\n",
        "    renvoie, grâce à un procédé matriciel, un vecteur colonne égal aux degrés entrant, sortant, total de chaque sommet'''\n",
        "    L = len(E)\n",
        "    A = np.matrix(matrice_adjacence(E), dtype = int) # par défaut, zeros et ones renvoient des matrices de flottants, on convertit en entier\n",
        "                                                     # penser à doubler les parethèses derrière zeros et ones\n",
        "    U = np.matrix(np.ones((L,1), dtype = int)) # matrice de 1, à L ligne et 1 colonne\n",
        "    # @ désigne le produit matriciel pour les variables de type  np.matrix\n",
        "    De = A @ U      # A @ U compte le nombre d'arcs sortant de chaque noeud (c'est-à-dire le nombre de multiples)\n",
        "    # A.T est la matrice transposée de la matrice A\n",
        "    Ds = A.T @ U    # A.T @ U compte le nombre d'arcs entrant dans chaque sommet (c'est-à-dire le nombre de diviseurs) \n",
        "    D = De + Ds                   \n",
        "    return De,Ds,D"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "f7RXeBDbxT3c",
        "outputId": "825897ef-0d71-4dbf-fd8c-9df5292df448"
      },
      "source": [
        "De,Ds,D = degre(E)\n",
        "print(\"Degrés sortant (c'est-à-dire nombre de diviseurs)\")\n",
        "Ds"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Degrés sortant (c'est-à-dire nombre de diviseurs)\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[6],\n",
              "        [1],\n",
              "        [2],\n",
              "        [2],\n",
              "        [3],\n",
              "        [2],\n",
              "        [4]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uPV53kcu19NU"
      },
      "source": [
        "def degre0(E) :\n",
        "    ''' Fonction qui reçoit un ensemble, \n",
        "    calcule la matrice d'adjacence du graphe des diviseurs dans cet ensemble\n",
        "    renvoie, grâce à un procédé algorithmique, des matrices-colonnes égales aux degrés entrant, sortant, total de chaque sommet'''\n",
        "    L = len(E)\n",
        "    A = np.matrix(matrice_adjacence(E))\n",
        "    De = np.matrix(np.zeros((L,1), dtype = int))\n",
        "    Ds = np.matrix(np.zeros((L,1), dtype = int))\n",
        "    for i in range(L):\n",
        "        for j in range(L) :\n",
        "            De[i] = De[i] + A[i,j]\n",
        "            Ds[i] = Ds[i] + A[j,i]\n",
        "    D = De + Ds\n",
        "    return De, Ds, D\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7qt8abhW4j6z",
        "outputId": "925981f5-3b4f-49f8-c847-a9f4a57e8083"
      },
      "source": [
        "De,Ds,D = degre0(E)\n",
        "print(\"Degrés sortant (c'est-à-dire nombre de diviseurs)\")\n",
        "Ds"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Degrés sortant (c'est-à-dire nombre de diviseurs)\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[6],\n",
              "        [1],\n",
              "        [2],\n",
              "        [2],\n",
              "        [3],\n",
              "        [2],\n",
              "        [4]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4sqsde85tuyo"
      },
      "source": [
        "def nb_chemins(A,l,i,j) :\n",
        "    '''Fonction qui reçoit  * une matrice carrée A, matrice d'adjacence d'un graphe\n",
        "                            * 3 entiers l, i et j\n",
        "    et qui renvoie le nombre de chemins de longueur l reliant i à j'''\n",
        "    A = np.matrix(A)\n",
        "    pA = A**l\n",
        "    n = pA[i,j]\n",
        "    return n, pA"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JEAl9y8E4iXY",
        "outputId": "3175a68c-e4fe-4c3a-9c6a-3a56b7430913"
      },
      "source": [
        "l = 3\n",
        "i = 1\n",
        "j = 6\n",
        "\n",
        "\n",
        "n, pA = nb_chemins(A, l, i, j)\n",
        "print(pA)\n",
        "print('Il y a ', n, ' chemins de longueur ', l , ' reliant ', i , ' à ', j )"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[ 0  0  0  0  0  0  0]\n",
            " [14  1  3  3  6  3  9]\n",
            " [ 5  0  1  0  3  0  3]\n",
            " [ 3  0  0  1  0  0  3]\n",
            " [ 1  0  0  0  1  0  0]\n",
            " [ 1  0  0  0  0  1  0]\n",
            " [ 1  0  0  0  0  0  1]]\n",
            "Il y a  9  chemins de longueur  3  reliant  1  à  6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9mflHrus9ROo"
      },
      "source": [
        "### **4°) connexité ?**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mxMsYVu69QrO"
      },
      "source": [
        "def connexe(A) :\n",
        "    '''Fonction qui reçoit la matrice d'adjacence d'un graphe \n",
        "    et qui renvoie la matrice somme des puissances de A (jusqu'à sa taille - 1)\n",
        "    et la valeur \"vrai\" si le graphe est connexe, \"faux\" sinon'''\n",
        "    l,L= np.shape(A)\n",
        "    S = np.matrix(np.eye(L), dtype = int)\n",
        "    for p in range(1,L) : \n",
        "        S = S + A**p # S est la matrice contenant la somme des puissances de A de 0 à L-1\n",
        "    return S, 0 not in S # Si 0 n'est dans la matrice S, A est fortement connexe"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Xsj00yEx7WqE",
        "outputId": "3953cd0a-4ab2-45b4-e6ae-59ab763de222"
      },
      "source": [
        "S, boo = connexe(A)\n",
        "print(S)\n",
        "print(boo)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[1 0 0 0 0 0 0]\n",
            " [6 7 6 6 6 6 6]\n",
            " [6 0 7 0 6 0 6]\n",
            " [6 0 0 7 0 0 6]\n",
            " [6 0 0 0 7 0 0]\n",
            " [6 0 0 0 0 7 0]\n",
            " [6 0 0 0 0 0 7]]\n",
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gRPVxofMbEVl"
      },
      "source": [
        "## **Ex 2 :** \n",
        "\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=1BoXid2oLeRtrUrZetpMB8J8qXlChlScn\" width=\"550\" height=\"350\" />"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gaHjbYb5t8Ld"
      },
      "source": [
        "### **1°) Matrice d'adjacence et caractéristiques du graphe**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F9-gHhIFsTOF"
      },
      "source": [
        "* noms de sommets (\"*Vertices*\")"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ppbDC9k0sT_d",
        "outputId": "20c1c0e1-e328-451d-9e0a-d614e22af7c5"
      },
      "source": [
        "V = [\"A\",\"B\",\"C\",\"D\",\"E\",\"F\",\"G\"]\n",
        "V"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['A', 'B', 'C', 'D', 'E', 'F', 'G']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "okwk8DTzso29"
      },
      "source": [
        "* Matrice d'adjacence"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8MttEBzFd-fT",
        "outputId": "68ef395e-dda4-43a6-c62a-a558b91bf191"
      },
      "source": [
        "# Matrice d'ajacence\n",
        "A = np.matrix([\n",
        "[0,1,0,0,1,0,0,0],\n",
        "[1,0,1,0,1,1,0,0],\n",
        "[0,1,0,1,0,1,1,0],\n",
        "[0,0,1,0,0,0,1,0],\n",
        "[1,1,0,0,0,1,0,1],\n",
        "[0,1,1,0,1,0,1,1],\n",
        "[0,0,1,1,0,1,0,0],\n",
        "[0,0,0,0,1,1,0,0]])\n",
        "l,L = np.shape(A)\n",
        "A"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[0, 1, 0, 0, 1, 0, 0, 0],\n",
              "        [1, 0, 1, 0, 1, 1, 0, 0],\n",
              "        [0, 1, 0, 1, 0, 1, 1, 0],\n",
              "        [0, 0, 1, 0, 0, 0, 1, 0],\n",
              "        [1, 1, 0, 0, 0, 1, 0, 1],\n",
              "        [0, 1, 1, 0, 1, 0, 1, 1],\n",
              "        [0, 0, 1, 1, 0, 1, 0, 0],\n",
              "        [0, 0, 0, 0, 1, 1, 0, 0]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2P6WXycXszut"
      },
      "source": [
        "* connexité"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "d0bIGt45-g5r",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1d221768-5454-4f54-9b9b-bb2d5118cafa"
      },
      "source": [
        "S, boo = connexe(A) # on recycle la fonction \"connexe\" de l'Ex1\n",
        "print(S)\n",
        "print(boo)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[ 557 1029  927  441  958 1167  711  607]\n",
            " [1029 1862 1759  858 1747 2203 1323 1095]\n",
            " [ 927 1759 1667  856 1589 2063 1299 1019]\n",
            " [ 441  858  856  433  780 1005  670  497]\n",
            " [ 958 1747 1589  780 1613 2029 1212 1030]\n",
            " [1167 2203 2063 1005 2029 2527 1598 1294]\n",
            " [ 711 1323 1299  670 1212 1598  995  766]\n",
            " [ 607 1095 1019  497 1030 1294  766  646]]\n",
            "True\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tQwOb6IOuR_d"
      },
      "source": [
        "* complétude"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "P1AqKwFtkYoD"
      },
      "source": [
        "def complet(A) :\n",
        "    '''Fonction qui reçoit la matrice d'adjacence d'un graphe et renvoie vrai s'il est complet'''\n",
        "    l,L = np.shape(A)\n",
        "    if 0 not in (A + np.eye(L)) : # les 0 sur la diagonale, c'est-à-dire l'absence de boucles, \n",
        "                                # n'empêchent pas un graphe d'être complet\n",
        "        return True\n",
        "    else :\n",
        "        return False\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Fa7VUyl_lJaP",
        "outputId": "23a8b74b-d484-400f-895a-5df96684b950"
      },
      "source": [
        "complet(A)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qXWYaSbixDf0"
      },
      "source": [
        "### **2°) Distances dans un graphe**\n",
        "- On appelle **distance** entre deux sommets la longueur du plus court chemin qui les joint.\n",
        "- L’**excentricité** d’un sommet est la plus grande des distances qui le joint aux autres sommets\n",
        "- Le **diamètre** d’un graphe est la plus grande des excentricités de ses sommets.\n",
        "- Le **rayon** d’un graphe est la plus petite des excentricités et les **centres** sont les sommets ayant cette excentricité minimale."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oNxbTzcBxdHP"
      },
      "source": [
        "* **Calcul de la matrice des distances entre les sommets**\n",
        "\n",
        "S'il existe un chemin de longueur L entre deux sommets, alors qu'il n'existait pas de chemin de longueur L-1, c'est que la distance entre ces deux sommets vaut L.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Z7jsZfI-xqSH"
      },
      "source": [
        "def matrice_des_distances(A) :\n",
        "    r,c = np.shape(A)\n",
        "    M = np.zeros((r,c), dtype = int) # penser aux doubles parenthèses pour \"zeros\"\n",
        "    M = (A != 0)*1 # gère le cas d'un graphe pondéré\n",
        "\n",
        "    P = np.copy(A)\n",
        "    \n",
        "    for p in range(2,r) :\n",
        "        PA = P @ A # on calcule la puissance suivante de A\n",
        "        for i in range(r):\n",
        "            for j in range(c): # gère le cas des graphes orientés, sinon, on pourrait s'occuper uniquement d'une demi-matrice\n",
        "                if i!=j :           # hors de la diagonale\n",
        "                    if PA[i,j] != 0 and P[i,j] == 0 : # un élément de la puissance de A est non nul \n",
        "                                                      # alors qu'il l'était à la puissance précédente\n",
        "                        M[i,j] = p\n",
        "        P = np.copy(PA)\n",
        "    return np.matrix(M)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dijsud6d29rc",
        "outputId": "61113ef9-3aeb-4117-e2dd-46fbf2ea0c31"
      },
      "source": [
        "M = matrice_des_distances(A)\n",
        "M"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[0, 1, 2, 3, 1, 2, 3, 2],\n",
              "        [1, 0, 1, 2, 1, 1, 2, 2],\n",
              "        [2, 1, 0, 1, 2, 1, 1, 2],\n",
              "        [3, 2, 1, 0, 3, 2, 1, 3],\n",
              "        [1, 1, 2, 3, 0, 1, 2, 1],\n",
              "        [2, 1, 1, 2, 1, 0, 1, 1],\n",
              "        [3, 2, 1, 1, 2, 1, 0, 2],\n",
              "        [2, 2, 2, 3, 1, 1, 2, 0]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eiAGbwn_HWZp",
        "outputId": "7572a517-60ba-48dc-9dec-0cc44bc9f17e"
      },
      "source": [
        "i = 3\n",
        "j = 0\n",
        "print(V[i], 'est à la distance', M[i,j], 'de', V[j])\n",
        "print( '{} est à la distance {} de {}'.format( V[i], M[i,j], V[j]))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "D est à la distance 3 de A\n",
            "D est à la distance 3 de A\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jvP5i_WFAbTN"
      },
      "source": [
        "* excentricité"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "O6QsNKnNBjEd",
        "outputId": "b9850947-237b-40f5-a167-1db27d87c3a7"
      },
      "source": [
        "exc = np.max(M, axis = 1)   # axis = 1 indique que l'on met en colonne (axis = 1)\n",
        "                            # les résultats de la recherche du max de chaque ligne de M\n",
        "exc"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[3],\n",
              "        [2],\n",
              "        [2],\n",
              "        [3],\n",
              "        [3],\n",
              "        [2],\n",
              "        [3],\n",
              "        [3]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2Zq5CwZNBfLE"
      },
      "source": [
        "* diamètre du graphe"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kGJ372AmAhxf",
        "outputId": "8391952b-30f2-4150-abf7-868023a43120"
      },
      "source": [
        "diam = np.max(M)\n",
        "diam"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SfOoThNACg-T"
      },
      "source": [
        "* rayon du graphe"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "10Ot5kJUClv-",
        "outputId": "910fefa4-c01e-4f8f-bc4e-5eb6700a20ff"
      },
      "source": [
        "ray = np.min(exc)\n",
        "ray"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4USLndmoEHwL"
      },
      "source": [
        "* centres"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZLpJf_OXFfby",
        "outputId": "7e047836-0f4e-4907-9853-e956c2446265"
      },
      "source": [
        "exc[2]"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[2]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4QITn17OEPS5",
        "outputId": "7879cc36-e61c-44ea-fdf3-a0cd967a18a5"
      },
      "source": [
        "centres = set([V[i] for i in range(L) if exc[i] == ray])\n",
        "centres"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{'B', 'C', 'F'}"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 25
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nQNJgn47uUlD"
      },
      "source": [
        "### **3°) Graphe eulérien**\n",
        "\n",
        "\n",
        "* graphe eulérien, semi-eulérien\n",
        "\n",
        "**Théorème : un graphe est eulérien si et seulement s'il est connexe et que tous ses sommets sotn de degré pair.**\n",
        "\n",
        "**Théorème : Un graphe comporte un nombre pair de sommets de degré impair..**\n",
        "\n",
        "Un graphe est semi-eulérien s'il ne comporte que deux sommets de degré impair. Il suffit alors de relier ces deux sommets pour obtenir un graphe eulérien"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XsKEMrrNlK1F"
      },
      "source": [
        "# Graphe eulérien\n",
        "# Rappel : un graphe est eulérien si et seulement si il est connexe et tous ses sommets sont de degré pair\n",
        "\n",
        "def degre_mat(A) :\n",
        "    ''' Fonction qui reçoit la matrice A d'adjacence d'un graphe \n",
        "    et renvoie un vecteur colonne égal aux degrés de chaque sommet'''\n",
        "    l,L = np.shape(A)\n",
        "    U = np.matrix(np.ones((L,1), dtype = int)) # matrice de 1, à L ligne et 1 colonne\n",
        "    # @ désigne le produit matriciel pour les variables de type  np.matrix\n",
        "    D = A @ U      # A @ U compte le nombre d'arête de chaque noeud \n",
        "    return D"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "To1qsmxkrVMm",
        "outputId": "cf852f98-6962-41ee-ca31-f0f6d6ea9e8e"
      },
      "source": [
        "degre_mat(A)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[2],\n",
              "        [4],\n",
              "        [4],\n",
              "        [2],\n",
              "        [4],\n",
              "        [5],\n",
              "        [3],\n",
              "        [2]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RcZfXvQZrZFv",
        "outputId": "bbcd7015-60e3-40b4-bcb6-374c6b3a245f"
      },
      "source": [
        "parite_sommets = degre_mat(A)%2 # on teste si les sommets sont de degré pair\n",
        "parite_sommets"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[0],\n",
              "        [0],\n",
              "        [0],\n",
              "        [0],\n",
              "        [0],\n",
              "        [1],\n",
              "        [1],\n",
              "        [0]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 28
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2GsWI7uJwIu_",
        "outputId": "981f37ce-c9fa-460f-d4f4-6d3bc25fba44"
      },
      "source": [
        "int(sum(degre_mat(A)%2)) # nombre de sommets de degré impair"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 29
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "foiUcvGltJgr"
      },
      "source": [
        "def eulerien(A):\n",
        "    '''Fonction qui reçoit la matrice d'adjacence d'un graphe \n",
        "    et retourne une chaîne indiquant si ce graphe est eulérien, semi-eulérien, ou non'''\n",
        "    S, boo = connexe(A)\n",
        "    rep = \"non eulérien\"\n",
        "    if boo == True : # Le graphe est connexe\n",
        "        if sum(degre_mat(A)%2) == 0 :# tous les sommets sont de degré pair \n",
        "            rep = \"eulérien\" # Le graphe est eulérien\n",
        "        elif sum(degre_mat(A)%2) == 2 : #Deux sommets de degré impair seulement\n",
        "            rep = \"semi-eulérien\"\n",
        "        \n",
        "    return rep\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        },
        "id": "pyrBFJ9Uu4Sw",
        "outputId": "70bc3905-d815-4f3e-ca1f-dba2c28c9570"
      },
      "source": [
        "eulerien(A)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'semi-eulérien'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 31
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i6r5zC5iwJ9Y"
      },
      "source": [
        "* Liaison des sommets impairs d'un graphe semi-eulérien"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "730OTuLD1dc1",
        "outputId": "08bd99ae-33ef-4591-e3ec-fd79f9ee81bb"
      },
      "source": [
        "liste_sommets_impairs = [i for i in range(L) if parite_sommets[i] == 1  ]\n",
        "liste_sommets_impairs"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[5, 6]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 32
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cDS6asMhvK_3",
        "outputId": "be717e4b-33b6-4848-a9f6-21b6832a471c"
      },
      "source": [
        "if eulerien(A) ==\"semi-eulérien\" :\n",
        "    liste_sommets_impairs = [i for i in range(L) if parite_sommets[i] == 1  ]\n",
        "    print(\"Le graphe est semi-eulérien, pour le rendre eulérien, relier les sommets : \", V[liste_sommets_impairs[0]], \" et \", V[liste_sommets_impairs[1]])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Le graphe est semi-eulérien, pour le rendre eulérien, relier les sommets :  F  et  G\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z1fhESSWcHQp"
      },
      "source": [
        "## **Ex 4 : réseaux sociaux**\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "W2Y54iWscNh3",
        "outputId": "7857013d-59f0-4537-c6f4-8d9521f4b040"
      },
      "source": [
        "import numpy as np\n",
        "\n",
        "M = np.matrix([\n",
        "    [0,0,1,1,0,0,1],\n",
        "    [0,0,0,0,1,1,0],\n",
        "    [1,0,0,1,0,0,0],\n",
        "    [1,0,1,0,0,0,1],\n",
        "    [0,1,0,0,0,1,0],\n",
        "    [0,1,0,0,1,0,0],\n",
        "    [1,0,0,1,0,0,0]])\n",
        "M"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[0, 0, 1, 1, 0, 0, 1],\n",
              "        [0, 0, 0, 0, 1, 1, 0],\n",
              "        [1, 0, 0, 1, 0, 0, 0],\n",
              "        [1, 0, 1, 0, 0, 0, 1],\n",
              "        [0, 1, 0, 0, 0, 1, 0],\n",
              "        [0, 1, 0, 0, 1, 0, 0],\n",
              "        [1, 0, 0, 1, 0, 0, 0]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "c1hR5eDddAOK",
        "outputId": "436835bc-e4d6-4819-a1dd-eb5815bf56bd"
      },
      "source": [
        "N = np.matrix([\n",
        "    [0,0,1,0,0,0,0],\n",
        "    [0,0,0,0,1,1,1],\n",
        "    [1,0,0,1,0,1,1],\n",
        "    [1,0,0,0,0,0,1],\n",
        "    [0,0,0,1,0,1,1],\n",
        "    [0,0,0,0,1,0,1],\n",
        "    [1,0,0,0,0,0,0]])\n",
        "N"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "matrix([[0, 0, 1, 0, 0, 0, 0],\n",
              "        [0, 0, 0, 0, 1, 1, 1],\n",
              "        [1, 0, 0, 1, 0, 1, 1],\n",
              "        [1, 0, 0, 0, 0, 0, 1],\n",
              "        [0, 0, 0, 1, 0, 1, 1],\n",
              "        [0, 0, 0, 0, 1, 0, 1],\n",
              "        [1, 0, 0, 0, 0, 0, 0]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "erHDQoYod3O4"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}