Cours : 12 séances d'1h20
Cours #1
-
Généralités
- Rappels historiques : ponts de Königsberg, graphe eulérien,
problème des 4 couleurs
- Définitions sur les graphes non orientés
- Sommets, arêtes
- Arête multiple, boucle, graphe simple
- Degré
- Relations adjacence (sommets, arêtes) et incidence
- Voisin
- Ordre, taille
- Notation V(G), E(G), n, m, deg(v)
- Définitions sur les graphes orientés
- Ensembles de sommets et d'arcs
- Arcs entrant et sortant
- Prédécesseur, successeur
- Degrés entrant et sortant
- Définitions sur les graphes étiquetés et non étiquetés
- Notion d'égalité sur les graphes étiquetés
- Isomorphisme de graphes
- Cheminement
- Chaîne, chaîne simple, chaîne élémentaire, cycle
- Chemin, circuit, circuit élémentaire
- Théorèmes
- Le nombre maximum d'arêtes dans un graphe simple est égal
à n*(n-1)/2
- La somme des degrés d'un graphe non orienté est paire et
égale à deux fois le nombre d'arêtes
- Le nombre de sommets de degré impair dans un graphe non
orienté est pair
- Dans un graphe orienté, la somme des degrés entrants est
égale à la somme des degrés sortants et au nombre d'arcs
- Dans tout graphe simple ayant au moins deux sommets, il
existe deux sommets de même degré
Cours
#2
- Sous-graphes
- Sous-graphes induits
- Graphes partiels
- Connexité
- Graphes connexes
- Graphes fortement connexes
- Composantes connexes et fortement connexe
- Connectivité
-
Structures de données et complexité
- Notions asymptotiques
- Grand O, Oméga, Thêta
- Représentations
- Matrice d'adjacence
- Matrice d'incidence
Cours
#3
- Listes d'adjacence
- Ensembles de voisinage (tables de hachage)
- Taille mémoire selon la représentation
- Complexité selon la représentation
- Existence d'une arête ou d'un arc entre deux sommets
- Degré d'un sommet
- Degré de tous les sommets
-
Parcours
- Parcours en largeur
- Principe : utilisation d'une file et exemple de parcours
sur un graphe non orienté
- Algorithme
- Exemples
- Complexité
- Validité (jusqu'à : pour tout sommet v de V(G), d(v) ≥ dG(s,v))
Cours
#4
- Validité (suite et fin)
- Parcours en profondeur
- Principe: utilisation d'une pile et exemple de parcours
sur un graphe non orienté
- Énoncé de l'algorithme
- Exemple sur un graphe orienté
- Complexité
- Classification des arcs
- Classes des arcs dans le parcours en profondeur d'un
graphe non orienté
-
Cours
#5
- Couleur des sommets lors du parcours d'un arc en fonction
de sa classe
- Théorème des parenthèses
- Théorème du chemin blanc
- Applications du parcours en profondeur
- Tri topologique
- Principe
- Exemple
- Algorithme
- Théorème: tout graphe admet un tri topologique ssi il
est sans circuit
- Validité de l'algorithme
- Composantes fortement connexes
- Définition
- Exemple
Cours
#6
- Algorithme
- Validité de l'algorithme (voir sujet Examen 2011/2012 - session
1 exercice 4)
Cours
#7
-
Arbres couvrants de poids minimum
- Définition : graphe partiel
- Caractérisation des arbres (rappel du TD1)
- Cycle fondamental
- Algorithme de Kruskal
- Principe
- Exemple
- Énoncé
- Complexité
- Validité
- Algorithme de Prim
- Principe
- Exemple
- Énoncé
- Complexité
- Validité
-
Plus courts chemins
- Problématique
- Entre deux sommets
- Entre un sommet v et tous les autres
- Entre tous les sommets
- Existence
Cours #8
- Arborescence
- Principe du relâchement
- Principes des algorithmes de Dijkstra (fonction de poids
positive) et Bellman (graphe sans circuit)
- Dijkstra
- Algorithme
- Exemple
- Complexité avec file de priorité
- Validité
- Bellman
- Algorithme à partir d'un ordre topologique
- Exemple
Cours
#9
- Complexité
- Version "longue"
- Ford (détection d'un circuit absorbant)
- Principe
- Algorithme
- Complexité
- Exemple
- Plus court chemin entre toutes paires de sommets
- Complexité avec Dijkstra
- Calcul matriciel
- Principe
Cours
#10 et 11
- Algorithme
- Exemple
- Complexité
- Version accélérée
- Floyd
- Principe
- Algorithme
- Complexité
- Exemple
- Fin de l'exemple
- Application à la fermeture transitive
- Définition
- Algorithme de Warshall
- Algorithme de Johnson (non traité)
- Principe
- Graphe (G', w', s)
- Algorithme
- Complexité
-
Flots
- Problématique
- Notion de réseau : graphe orienté, source, puits, capacité
- Notion de flot : loi de Kirchhoff, arc retour
- Problème du flot maximum
- Programme linéaire associé
- Recherche d'une chaîne améliorante
- Marquage direct
- Marquage indirect
- Algorithme de Ford et Fulkerson
- Exemple
Cours #12
- Coupe minimum
- Notion de coupe
- Théorème "Flot max / Coupe min"
- Application : Recherche d'un couplage maximum dans un graphe
biparti
- Applications (suite)
- Problème du flot canalisé (voir sujet Examen 2011/2012 - session 2
exercice 3)
- Arête-connectivité