Résumé de section

  • Replier Déplier

    Graphes

    Tout replier Tout déplier

    Contributors : Nadia Brauner (Université Grenoble Alpes), Nicolas Catusse (Grenoble INP), Hadrien Cambazard (Grenoble INP), Bernard Penz (Grenoble INP)

    Contact : Nadia Brauner

  • Replier Déplier

    Un peu de combinatoire pour commencer

  • Replier Déplier

    Les graphes

    what is graphe
    1. Modélisation à l'aide des graphes
    2. Notions de base sur les graphes
    3. Représentations des graphes
    4. Quelques graphes célèbres

    • Compétences

      1. Modélisation à l'aide de graphe
        • Reconnaitre un problème pratique qui peut être modélisé à l'aide de graphe
        • Modéliser un problème pratique à l'aide d'un graphe
      2. Notions de base sur les graphes
        • Identifier et décrire un isomorphisme 
        • Reconnaitre les principales variantes aux graphes simples : boucle, graphe orienté, mutigraphe, étiquetage 
        • Ecrire des preuves simples sur des propriétés des degrés 
      3. Représentation des graphes
        • Présenter un graphe dans différentes représentation : graphique, matrice d'adjacence, matrice d'incidence, liste d'adjacence 
        • Décrire un algorithme pour passer d'une représentation machine (matrice ou liste) à l'autre 
        • Choisir la représentation la plus adaptée (coût temps et espace) à un problème 
      4. Implémentation d'algorithme simples sur les graphes
        • Comprendre le fonctionnement de la classe Graphe.java
        • Implémenter quelques manipulations des graphes en java 


      Vocabulaire :  graphe, sommets, arêtes, ordre, complémentaire, auto-complémentaire, extrémité d'une arête, arête incidente à un sommet, sommets voisins, sommet isolé, voisinage d'un sommet, degré d'un sommet, graphe k -régulier, graphe complet, arc

      Notations :  G, V, E, n, m, d(v), N(v), K_n

    • Transparents d'introduction sur les graphes Fichier
      Les étudiants doivent
      Consulter
    • Glossaire Français-Anglais
      Les étudiants doivent
      Marquer comme terminé
    • Mots croisés Jeu
      Les étudiants doivent
      Marquer comme terminé
    • Test sur les graphes
      Les étudiants doivent
      Recevoir une note
    • Prise en main de la classe Graphe.java (listes d'adjacence) Virtual programming lab
      Les étudiants doivent
      Recevoir une note
    • Javadoc de Graphe.java Fichier
      Les étudiants doivent
      Consulter
    • Prise en main de la classe Graphe.java (matrice d'adjacence) Virtual programming lab
      Les étudiants doivent
      Marquer comme terminé
  • Replier Déplier

    Cheminements


    1. Chaîne
    2. Connexité
    3. Parcours de graphes / accessibilité
    4. Graphes eulériens
    		Spyked math cheminement

    • Compétences

      1. Techniques de preuve
        • Connaître les trois étapes d'une preuve algorithmique (exécution, terminaison, validité du résultat)
        • Avoir compris les preuves algorithmiques du cours
        • Appliquer le schéma de preuve algorithmique sur des problèmes simples
        • Avoir compris les preuves par contre exemple minimal/maximal du cours
        • Avoir compris les certificats du cours (accessibilité, distance)
      2. Propriétés
        • Montrer que l'existence d'un chemin entre deux sommets est une relation d'équivalence
        • Connaitre la propriété sur le nombre minimal d'arêtes d'un graphe connexe
        • Connaître et démontrer le théorème de Euler (caractérisation des graphes eulériens)
      3. Parcours
        • Décrire / Reconnaitre un parcours en profondeur ou en largeur d'un graphe
        • Ecrire l'algorithme pour faire un parcours en largeur et en profondeur d'un graphe

      Vocabulaire :       chaîne, extrémités, simple, élémentaire, longueur, graphe connexe, composante connexe, co-cycle, parcours en largeur, BFS, parcours en profondeur, DFS, st-coupe, cycle, cycle eulérien, chaîne eulérienne, graphe eulérien, cycle hamiltonien, graphe hamiltonien
    • Transparents cheminement Fichier
      Les étudiants doivent
      Consulter
    • Transparents graphes Eulériens - Hamiltoniens Fichier
      Les étudiants doivent
      Consulter
    • One idea, one story: meet the 1962 Procter and Gamble challenge ! Page
      Les étudiants doivent
      Consulter
    • One idea, one story: when the salesman started its travel Page
      Les étudiants doivent
      Consulter
    • Feuille d'exercices cheminement Fichier
      Les étudiants doivent
      Consulter
    • Test Chaînes, Cycles et Connexité
      Les étudiants doivent
      Consulter
      Recevoir une note
      Obtenir une note minimale de réussite
    • Test Cheminement complet
      Les étudiants doivent
      Consulter
      Recevoir une note
      Obtenir une note minimale de réussite
    • Parcours d'un graphe Virtual programming lab
      Les étudiants doivent
      Recevoir une note
    • Manipulation de la classe graphe, parcours et graphes eulériens - Python Virtual programming lab
      Les étudiants doivent
      Recevoir une note
  • Replier Déplier

    Arbres

    1. Arbres et forets
    2. Arbres enracinés
    3. Arbres couvrants de poids minimum
    		How a graph theorist draws a "star"
  • Replier Déplier

    Plus courts chemins

    1. Graphes orientés
    2. Plus courts chemins
    3. DAG : l'algorithme de Bellman
    4. Poids positifs : l'algorithme de Dijkstra


    		Spyked math cheminement
  • Replier Déplier

    Notions plus avancées sur les graphes

    1. Sous-graphes
    2. Cliques et stables
    3. Graphes bipartis

    • Compétences

        • Reconnaitre un sous-graphe, un sous-graphe engendré (ou induit), un graphe couvrant d'un graphe
        • Calculer  \omega(G) et \alpha(G)  à la main sur de petits graphes 
        • Connaitre et démontrer la caractérisation des graphes bipartis avec les cycles impairs 
        • Donner un certificat qu'un graphe est biparti ou non 


      Vocabulaire : sous-graphe, sous-graphe engendré ou induit, graphe couvrant, complet, stable, clique, graphe biparti, graphe biparti complet

      Notation : G[W] , \omega(G) , \alpha(G) , K_{a,b}

    • Transparents graphes bipartis Fichier
      Les étudiants doivent
      Consulter
    • Test notions plus avancées
      Les étudiants doivent
      Consulter
      Recevoir une note
      Obtenir une note minimale de réussite
    • Test et certificat de bipartition Virtual programming lab
      Les étudiants doivent
      Recevoir une note
  • Replier Déplier

    Coloration

    1. Coloration 
    2. Bornes et algorithmes 
    3. Coloration de graphes d’intervalles 
    4. Coloration de graphes planaires

    Coloring book (spikedmath.com)

    • Compétences

      1. Bornes et algorithmes
        • Connaitre les preuve sur les bornes de coloration avec la clique max et le degré max
        • Décrire l'algorithme glouton de coloration 
        • Utiliser l'algorithme glouton pour prouver la borne sur le degré max 
        • Modéliser des problèmes pratiques commme des problèmes de coloration de graphe 
      2. Graphes d'intervalles
        • Construire le graphe d'intersection associé à une famille d'ensembles 
        • Utiliser l'algorithme glouton pour résoudre optimalement la coloration de graphes d'intervalles 
        • Montrer l'optimalité de l'algorithme 
      3. Graphes planaires
        • Expliquer la formule d'Euler 
        • Démontrer qu'un graphe planaire est 6-coloriable 
        • Utiliser l'algorithme glouton pour 6-colorier un graphe planaire

      Vocabulaire : k -coloration, nombre chromatique, graphe d'intersection, graphe d'intervalles, graphe planaire

      Notations :  \chi(G) , \Delta(G) , \omega(G)

    • Transparents coloration Fichier
      Les étudiants doivent
      Consulter
    • Feuille d'exercices sur les graphes bipartis et la coloration Fichier
      Les étudiants doivent
      Marquer comme terminé
    • One idea, one story: le théorème des 4 couleurs Page
      Les étudiants doivent
      Consulter
    • Leçon sur la coloration de graphes
      Les étudiants doivent
      Marquer comme terminé
    • Modélisation de problèmes pratiques avec la coloration Leçon
      Les étudiants doivent
      Marquer comme terminé
    • Graphes planaires et coloration Leçon
      Les étudiants doivent
      Marquer comme terminé
    • Test Cliques, Stables et Coloration
      Les étudiants doivent
      Consulter
      Recevoir une note
      Obtenir une note minimale de réussite
    • Test graphes d'intervalles et graphes planaires
      Les étudiants doivent
      Consulter
      Recevoir une note
      Obtenir une note minimale de réussite
  • Replier Déplier

    Couplages

    1. Couplage
    2. Couplage dans les graphes bipartis

    • Compétences

        • Connaitre le théorème qui lie les couplages max et les chaines altérnées augmentantes. 
        • Reproduire la preuve de ce théorème
        • Connaitre le lien entre  couplages et transversals dans les graphes quelconques et dans les graphes bipartis
        • Comprendre la preuve du théorème de Koning

      Vocabulaire : couplage, couplage parfait, Chaine M -alternée, Chaine M -augmentante, différence symétrique, transversal

      Notation : \nu(G) , X\Delta Y , \tau(G)
    • Transparents sur les couplages Fichier
      Les étudiants doivent
      Consulter
    • Test sur les couplages
      Les étudiants doivent
      Recevoir une note
      Obtenir une note minimale de réussite
    • Des vidéos sur les couplages maximums dans les graphes bipartis Page
      Les étudiants doivent
      Marquer comme terminé
  • Replier Déplier

    Flots

  • Replier Déplier

    Jeux

    1. S'entraîner sur tout le cours
    2. Jeux 
    3. Graphes et programmation linéaire 
    4. Bibliographie