chap08.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programmation Python  pour les mathématiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Julien Guillod**, [Sorbonne Université](http://www.sorbonne-universite.fr/),\n",
    "Licence <a href=\"https://creativecommons.org/licenses/by-nc-nd/4.0/\">CC BY-NC-ND</a>\n",
    "\n",
    "L'entier des chapitres est disponible au format\n",
    "[HTML](https://python.guillod.org/) et [PDF](https://python.guillod.org/python.pdf).\n",
    "Ce notebook peut également être exécuté sur [GESIS](https://notebooks.gesis.org/binder/v2/gh/guillod/python/master?urlpath=lab/tree/chap08.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8 Théorie des graphes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"ch:graphes\"></div>\n",
    "\n",
    "Un graphe est un couple $G = (X, E)$ constitué d'un ensemble $X$, non vide et fini, et d'un ensemble $E$ de paires d'éléments de $X$. Les éléments de $X$ sont les sommets du graphe $G$, ceux de $E$ sont les arêtes du graphe $G$.\n",
    "Un graphe est orienté si les arêtes ont une direction, c'est-à-dire si les couples d'éléments de $E$ sont des listes ordonnées telles que $(i,j) \\in E$ n'est pas équivalent à $(j,i)\\in E$. Ici seuls des graphes non orientés, c'est-à-dire dont les paires d'éléments de $X$ sont des ensembles non ordonnés ($\\{i,j\\} \\in E$), sont considérés.\n",
    "\n",
    "Par exemple, le graphe complet à $n$ sommets $K_n$ est le graphe de sommets $X = {1,2,\\dots,n}$ ayant comme arêtes les parties à deux éléments de $X$. En particulier, $K_4 = (X,E)$ où $X=\\{1,2,3,4\\}$ et $E = \\big\\{ \\{1,2\\}, \\{1,3\\}, \\{1,4\\}, \\{2, 3\\}, \\{2, 4\\}, \\{3, 4\\}  \\big\\}$.\n",
    "\n",
    "**Concepts abordés:**\n",
    "\n",
    "* graphes non orientés\n",
    "\n",
    "* représentation comme dictionnaire\n",
    "\n",
    "* utilisation des frozensets\n",
    "\n",
    "* matrice d'adjacence\n",
    "\n",
    "* recherche de chemins et de triangles\n",
    "\n",
    "* fonction récursive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 8.1: Graphes comme dictionnaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une façon de représenter un graphe $G$ est de le faire avec un dictionnaire dont les clefs sont\n",
    "les sommets, et la valeur associée à chaque clef $x \\in X$ est un ensemble contenant les voisins de $x$.\n",
    "\n",
    "**a)**\n",
    "Construire sous forme de dictionnaire les graphes suivants:\n",
    "\n",
    "<center><img src=\"https://python.guillod.org/fig/graphes.png\" style=\"width:90%;max-width:800px;\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)**\n",
    "Écrire une fonction `complet(n)` qui construit comme dictionnaire le graphe complet $K_n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)**\n",
    "Un graphe donné sous forme de dictionnaire contient l'information plusieurs fois. Écrire une fonction `corriger(graphe)` permettant de rajouter les éléments manquants de sorte que pour tout sommet `x`, si `y` appartient à `graphe[x]`, alors `y` est aussi une clef et `x` appartient à `graphe[y]`. Tester cette fonction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d)**\n",
    "Écrire une fonction qui retourne l'ensemble (type `set`) de toutes les arêtes d'un graphe représenté par un dictionnaire.\n",
    "\n",
    "**Indication:**\n",
    "Les ensembles sont mutables et donc pas hashables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**e)**\n",
    "<span style=\"color:red\">!</span> Écrire une fonction permettant de déterminer si deux sommets sont connectés par un chemin ou non et qui retourne le chemin si oui.\n",
    "\n",
    "**Indication:**\n",
    "Utiliser une fonction récursive."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**f)**\n",
    "<span style=\"color:red\">!</span> Écrire une fonction qui retourne tous les chemins entre deux sommets (sans les cycles)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 8.2: Triangles dans un graphe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un triangle dans un graphe est un ensemble de trois sommets reliés entre eux par trois arêtes. La recherche et l'analyse des triangles dans un graphe sont importantes pour comprendre sa structure.\n",
    "\n",
    "**a)**\n",
    "Déterminer mathématiquement le nombre de sous-ensembles de cardinal trois que possède un ensemble de sommets $X$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)**\n",
    "Écrire une fonction retournant l'ensemble des triangles d'un graphe."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À chaque graphe $G=(X,E)$ correspond une unique matrice $A$ symétrique de taille $n \\times n$ avec $n=|X|$ définie par:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "A_{ij}=\\begin{cases}\n",
    "1\\,, & \\text{si}\\;\\{i,j\\}\\in E\\,,\\\\ \n",
    "0\\,, & \\text{si}\\;\\{i,j\\}\\notin E\\,.\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette matrice est appelée la matrice d'adjacence du graphe $G$.\n",
    "\n",
    "**c)**\n",
    "Définir une fonction retournant la matrice d'adjacence d'un graphe.\n",
    "\n",
    "**Indication:**\n",
    "Faire attention que les sommets ne sont pas forcément indexés par des entiers compris entre 0 et $n$ dans le dictionnaire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d)**\n",
    "Définir une fonction ayant pour argument une matrice d'adjacence et retournant le graphe correspondant sous forme d'un dictionnaire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**e)**\n",
    "En utilisant la matrice d'adjacence $A$ et la matrice $B=A^2$, écrire une fonction retournant l'ensemble des triangles d'un graphe."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**f)**\n",
    "En utilisant la matrice d'adjacence $A$, écrire une fonction calculant le nombre de triangles.\n",
    "\n",
    "**Indication:**\n",
    "Interpréter les entrées de la matrice $A^n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 8.3: <span style=\"color:red\">!!</span> Module NetworkX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "De nombreux algorithmes de la théorie des graphes sont implémentés dans le module networkX, voir la documentation [ici](https://networkx.org/documentation/).\n",
    "\n",
    "**a)**\n",
    "Suivre le tutoriel de networkX disponible [ici](https://networkx.org/documentation/stable/tutorial.html).\n",
    "\n",
    "**b)**\n",
    "Analyser un des graphes téléchargeables à l'adresse: <https://github.com/gephi/gephi/wiki/Datasets> ou <https://snap.stanford.edu/data/>."
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}