Курс: Théorie des Graphes | Caseine

В начало Shared Space

Тематический план

Graphes

Свернуть всё Развернуть всё
Contributors : Nadia Brauner (Université Grenoble Alpes), Nicolas Catusse (Grenoble INP), Hadrien Cambazard (Grenoble INP), Bernard Penz (Grenoble INP)
Contact : Nadia Brauner
- Vous devez être inscrit dans le cours pour avoir accès à l'éditeur des exercices de programmation (roue dentée en haut à droite).
- Polycopié sur les graphes (GI-INP) Файл
- Exercices (UGA) Файл
- Annonces Форум
- An article on this course Гиперссылка
- Some english activities in this course Страница
Un peu de combinatoire pour commencer
Les graphes
$what is graphe$
Modélisation à l'aide des graphes
Notions de base sur les graphes
Représentations des graphes
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 Файл
  
  Просмотреть
- Glossaire Français-Anglais Глоссарий
- Mots croisés Игра
- Test sur les graphes Тест
  
  Получить оценку
- Prise en main de la classe Graphe.java (listes d'adjacence) Виртуальная лаборатория программирования
  
  Получить оценку
- Javadoc de Graphe.java Файл
  
  Просмотреть
- Prise en main de la classe Graphe.java (matrice d'adjacence) Виртуальная лаборатория программирования
Cheminements
Chaîne
Connexité
Parcours de graphes / accessibilité
Graphes eulériens
- 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 Файл
  
  Просмотреть
- Transparents graphes Eulériens - Hamiltoniens Файл
  
  Просмотреть
- One idea, one story: meet the 1962 Procter and Gamble challenge ! Страница
  
  Просмотреть
- One idea, one story: when the salesman started its travel Страница
  
  Просмотреть
- Feuille d'exercices cheminement Файл
  
  Просмотреть
- Test Chaînes, Cycles et Connexité Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Test Cheminement complet Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Parcours d'un graphe Виртуальная лаборатория программирования
  
  Получить оценку
- Manipulation de la classe graphe, parcours et graphes eulériens - Python Виртуальная лаборатория программирования
  
  Получить оценку
Tree
Trees and Forests

Rooted trees

Minimum spanning trees
- Skills
  1. Proof technics
  
  Understand double counting proofs in the course or in the exercises
  
  Apply double counting proof technics to simple proofs on trees
  
  2. Tree properties
  
  Know the trees characterizations
  
  Prove the equivalence between the tree characterizations
  
  Prove properties on trees (at least one leaf, at least two leaves, single path between each pair of vertices...)
  
  Describe certificates for tree recognition
  
  3. Minimum spanning tree
  
  Formulate the minimum spanning tree (MST) problem
  
  Describe on of the classical greedy algorithms (Kruskal or Prim) to solve the MST problem
  
  Explain the main components of the proof
  
  Vocabulary : acyclic, tree, forest, root, parent, children, leaf, hight, depth of a vertex, greedy algorithm, arborescence, weighed graph
- Transparents Arbres Файл
  
  Просмотреть
- One idea, one story: Les Hydrocarbones saturés acycliques Лекция
  
  Просмотреть Пройти лекцию до конца
- Transparents Arbre couvrant de poids min Файл
  
  Просмотреть
- One idea, one story: Prim's Network for the capitals of the American states Страница
  
  Просмотреть
- Feuille d'exercice Arbres Файл
  
  Просмотреть
- Test sur les arbres Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Tests on trees and on Kruskal algorithm Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Algorithmes de Kruskal et Union Find - Java Виртуальная лаборатория программирования
  
  Получить оценку
- Javadoc de GraphePondere.java Файл
  
  Просмотреть
- Javadoc de Arete.java Файл
  
  Просмотреть
- Implementation of the Union-Find Class and of Kruskal Algorithm - Java (the same in English) Виртуальная лаборатория программирования
- Arbre Couvrant de poids min - Python Виртуальная лаборатория программирования
  
  Получить оценку
- Vidéo (10min): Optimalité de l'algorithme de Prim Страница
- Vidéo (8min): Algorithme de Prim Страница
- Kruskal in English 09 22 Виртуальная лаборатория программирования
Plus courts chemins
Graphes orientés
Plus courts chemins
DAG : l'algorithme de Bellman
Poids positifs : l'algorithme de Dijkstra
- Compétences
  1. Problèmes
  Décrire les trois problèmes de plus courts chemins
  Expliquer le principe de sous-optimalité
  2. Algorithmes et preuves
  Décrire les ingrédients d'un algorithme de plus court chemin
  Écrire l'algorithme BFS
  Pour les graphes non pondérés, décrire le certificat et la preuve que BFS renvoie bien les distances
  3. DAG et algorithme de Bellman
  Démontrer qu'un DAG a toujours une source
  Décrire un algorithme pour trouver un ordre topologique
  Décrire l'algorithme de Bellman pour les plus courts chemins dans un DAG
  Appliquer l'algorithme de Bellman sur un exemple
  4. Poids positifs, algorithme de Dijkstra et tas binaire
  Décrire l'algorithme de Dijkstra pour les plus courts chemins lorsque les poids sont positifs
  Implémenter l'algorithme de Dijkstra
  Démontrer la validité de l'algorithme de Dijkstra
  Connaitre et Implémenter la structure de données tas binaire
  Calculer la complexité de l'algorithme de Dijkstra
  
  Vocabulaire : Graphe orienté, arc, degré entrant, degré sortant, source, puits, chemin, longueur d'un chemin, circuit, graphe orienté pondéré, distance, DAG, ordre topologique, tas binaires
  Notations : $d^-(u)$ , $d^+(u)$ , $d(u, v)$
- Transparents plus courts chemins Файл
  
  Просмотреть
- Feuille d'exercices plus courts chemins Файл
- One idea, one story: the physics of shortest paths to detect useless streets ! Страница
  
  Просмотреть
- Test plus court chemin Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Trouver un plus court chemin lorsque les poids sont positifs Тест
  
  Получить оценку Получить проходной балл
- Trouver un plus court chemin dans un DAG Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Exécuter l'algorithme de Bellman Ford Тест
- "L'humour est le plus court chemin d'un homme à un autre."
  Georges Wolinski
- Implémentation de la structure de tas binaire et de l'algorithme de Dijkstra - Java Виртуальная лаборатория программирования
  
  Получить оценку
- Javadoc de Element.java Файл
  
  Просмотреть
- Javadoc de Arc.java Файл
  
  Просмотреть
- Javadoc de GrapheOriente.java Файл
  
  Просмотреть
- Javadoc de TasBinaire.java Файл
  
  Просмотреть
- Plus courts chemins - Python Виртуальная лаборатория программирования
  
  Получить оценку
- Vidéo (6min): Ordre topologique Страница
- Vidéo (8 min): Application de Bellman-Ford sur un exemple Страница
- Vidéo (10 min): Les idées clefs de Bellman-Ford Страница
- Vidéo (1 min): De Bellman-Ford à la programmation dynamique Страница
Notions plus avancées sur les graphes
Sous-graphes
Cliques et stables
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 Файл
  
  Просмотреть
- Test notions plus avancées Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Test et certificat de bipartition Виртуальная лаборатория программирования
  
  Получить оценку
Coloration
Coloration
Bornes et algorithmes
Coloration de graphes d’intervalles
Coloration de graphes planaires
- 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 Файл
  
  Просмотреть
- Feuille d'exercices sur les graphes bipartis et la coloration Файл
- One idea, one story: le théorème des 4 couleurs Страница
  
  Просмотреть
- Leçon sur la coloration de graphes Лекция
- Modélisation de problèmes pratiques avec la coloration Лекция
- Graphes planaires et coloration Лекция
- Test Cliques, Stables et Coloration Тест
  
  Просмотреть Получить оценку Получить проходной балл
- Test graphes d'intervalles et graphes planaires Тест
  
  Просмотреть Получить оценку Получить проходной балл
Couplages
Couplage
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 Файл
  
  Просмотреть
- Test sur les couplages Тест
  
  Получить оценку Получить проходной балл
- Des vidéos sur les couplages maximums dans les graphes bipartis Страница
Flots
- Reconnaitre un problème pratique de flot
  Modéliser un problème pratique comme un problème de flot
  Connaitre le problème de flot maximum dans un graphe
  description par les arêtes
  description par les chemins
  Décrire et appliquer l'algorithme de Ford Fulkerson
  Démontrer que l'algorithme de Ford Fulkerson donne un flot optimal
  Connaitre l'énoncé du théorème de Menger
  Modéliser le problème de couplage maximum dans un graphe biparti comme un flot
- Transparents flots Файл
- Feuille d'exercices Flots Файл
- One idea, one story: secret min-cut Страница
- S'entraîner sur l'algorithme de Ford Fulkerson Тест
- Algorithme de Ford Fulkerson Виртуальная лаборатория программирования
- Javadoc de la classe Arc.java Файл
- Javadoc de la classe GrapheOriente.java Файл
- Vidéo (10 min) : Flot maximum, Application de l'algorithme de Ford et Fulkerson Гиперссылка
- Flots maximum, Graphes bipartis, Coloration - Python Виртуальная лаборатория программирования
  
  Получить оценку
- Vidéo (11 min): Encore une application de Ford et Fulkerson sur un exemple Страница
- Vidéo (5 min): La notion de coupe dans un réseau de flot Страница
- Vidéo (5 min): Idées clefs sur l'optimalité de l'algorithme de Ford et Fulkerson Страница
Jeux
S'entraîner sur tout le cours
Jeux
Graphes et programmation linéaire
Bibliographie
- S'entraîner sur les notions du cours Тест
- Jeux
- Un guide pas très organisé Тест
- L'étudiant disparu Тест
- Compter... Тест
- Digicode Тест
- Triangle et anti-triangle Тест
- Euler Project Гиперссылка
- Une énigme de TED-Ed : poursuite interstellaire URL Гиперссылка
- Match the intervals Тест
- Graphes et programmation linéaire
- User guide 1 : Modeling LP problems with OPL using Caseine editor Страница
- User guide 2 : Analyse the value of the dual variables Страница
- User guide 3 : Modeling Integer/Boolean variables Страница
- User guide 4: using .dat files with OPL and the Caseine editor Страница
- Independent Set (Stable) Виртуальная лаборатория программирования
- Maximum Matching Виртуальная лаборатория программирования
- * Chromatic number Виртуальная лаборатория программирования
- ** The traveling Salesman Problem (TSP) Виртуальная лаборатория программирования
- Bibliographie
- Théorie des graphes et applications
  Jean-Claude Fournier
  2011
  ed. Hermes
  Pearls in Graph Theory: A Comprehensive Introduction
  Nora Hartsfield, Gerhard Ringel
  2004
  ed. Dover
  Algorithms
  S. Dasgupta, C.H.Papadimitriou and U. Vazirani
  2006
  ed. McGraw-Hill Higher Education
  L’agrapheur
  Alain Hertz
  2010
  ed. Presses internationales Polytechnique
- Collaborative collection of Tikz Graph drawing База данных
- Atelier de modélisation Лекция