Graphes et algorithme
  • Discovering and exploring graphs: part 1
    • Common thread problem and rules of the game
      • Common thread
      • Organization of the course
    • A “toy example”
    • Exo - Modeling the data with a graph
    • Course - Graph
      • Reminder on sets
      • First definition of a graph
      • Visual representation of a graph
      • Successor map (neighborhood)
    • Exo - Memory representation of a graph
    • Cours - Memory representation of a graph
      • Memory representation for the vertices of a graph
      • Memory representation of a subset of vertices: linked list and Boolean array
      • Memory representation of a graph using an array of linked lists
      • Memory reresentation of a graph by Boolean matrix
      • Memory reresentation of a graph by an array of arcs
    • Exo - One way graphs
    • Course - Symmetric and graphs
    • Exo - Implementing a first graph algorithm
    • Course - SYM Algorithm: computing the symmetric of a graph
    • General Knowledge Bonus - Some remarkable graphs
  • Discovering and exploring graphs: part 2
    • Common thread problem and rules of the game
      • Fil rouge
      • Organization of the course
    • A “toy example”: reminder
    • Exo - Successor search: dilation algorithm
    • Course - Exploration of successors: dilation
    • Exo - Paths
    • Course - Paths
    • Exo - Partial search
    • Course - Partial search of a graph
    • Exo - Graph search
    • Course - Graph search
    • Exo - Coding graph search algorithms
    • Course - Graph search algorithm
      • Course - Naive graph search algorithm
      • Course - Breadth-first search algorithm
    • Exo - Connectivity
    • Course - Connectivity
      • Connectivity (and strong connectivity)
      • Connected components (and strongly connected components)
      • A remarkable property of connected and strongly connected components
    • Exo - Coding connected component algorithm
    • Course - Connected Component and Strongly Connected Component Algorithms
  • Regroupement de données avec des graphes
    • Présentation du problème fil rouge et règles du jeu
      • Fil rouge
      • Organisation du cours
    • Exercices : cyber-profiler et composantes \(k\)-liées
  • Shortest paths
    • Goal and organization
    • Lecture notes
    • Exercises (understanding the lecture and discovering backtracking)
    • Practical work
  • Building and optimizing a spy network - part 1: arborescence
    • Common thread problem and rules of the game
      • Common thread
      • Organization of the course
    • A “toy example”
    • Exo - Modeling the data with a graph
    • Course - Edge-weighted graph
    • Exo - Sending a secret message without redundancy
    • Course - Trees and arborescences
      • Trees
      • Arborescences
      • Memory representation of an arborescence
  • Building and optimizing a spy network - part 2: minimum spanning tree
    • Common thread
    • Organization of the course
      • A “toy example”
      • Exo - Optimal solution for the toy example
      • Course - Minimum spanning tree
    • Situation
    • Formalization with graphs
    • Maximum spanning tree
      • Exo - Computing minimum spanning trees
      • Course - Kruskal’s Algorithm
    • Generic scheme for computing minimum spanning trees
    • Kruskal’s Algorithm
    • Choix des structures de données et Analyse de complexité
    • Proof of correctness of Kruskal’s Algorithm
      • To go further…
Graphes et algorithme
  • Docs »
  • Search

© Copyright 2021, Benjamin Perret, Jean Cousty.

Built with Sphinx using a theme provided by Read the Docs.