Théorie des graphes
- cours
- graphes
- François Brucker
Cette introduction a pour but d'exposer quelques définitions, concepts et méthodes de résolution de problèmes propre aux graphes.
Il a pour principal objectif d'allumer la petite flamme de l'intérêt pour cette structure, à la fois riche en problèmes intéressants et en solutions élégantes ; à la fois théorique — à l'intersection des mathématiques discrètes et de l'informatique théorique — et au cœur de nombre d'applications de tous les jours.
Le cours va être séparé en petites entités qui se suivent pour former un tout que l'on espère cohérent.
Structure d'un graphe
TBD ajouter exercices sur cliques/independent set
Parcours
Un parcours d'un graphe est une suite de sommets ou d'arêtes ayant un propriété donné. On en verra plusieurs types ayant chacun leur propre intérêt.
Types de parcours
Parcours spécifiques :
Algorithmes généraux :
Projets
Chemins de longueur/poids minimum
Problème et algorithmes
Projets
Arbres
exo : https://www.youtube.com/watch?v=OTfp2_SwxHk TBD : DFS et arbre. Tarjan pour fortement connexe.
Exercices
TBD
- Chritofides https://en.wikipedia.org/wiki/Christofides_algorithm (en gardant l'algorithme heuristique, 1/2 approximation donc 2 approximation. On verra plus tard que 3/2 approximation)
- Théorie de Buneman et X-arbres
Problèmes de flots
Problèmes de flots. Définition, algorithmes et applications
Principes et algorithmes
Modélisation
Graphe biparti
Un exemple particulier de graphes, les graphes bipartis :
Couplages
Problèmes de couplage dans un graphe. On passera un peu de temps sur le cas des graphes bi-parti avant d'aborder le cas général.
TBD couper en bi-parti et quelconque et ajouter des exercices
Graphe bi-parti
TBD
Graphe quelconque
TBD
Projet
TBD revenir sur le problème du voyage de commerce avec
Colorabilité d'un graphe
Graphes parfaits
Graphes Planaires
Projets Autres
TBD DM line graph
Graphes aléatoires
Process de Galton-Watson
erdos-rado
TBD https://fr.wikipedia.org/wiki/Processus_de_Galton-Watson
Graphes aléatoires et infinis
TBD erdos-rado graphe infini unique grosse partie connexe pas connexe puis tout d'un coup connexe mes amis ont plus d'amis que moi Beaucoup de graphes ne sont pas parfait en prenant H = C5 : https://math.stackexchange.com/questions/4729419/let-h-be-a-graph-prove-that-almost-every-graph-g-in-mathcalg-n-p-has
Algorithmes randomisés
TBD Partie 3, après algo random et hasard en algorithmie.
couplage
Algo randomisés :
- https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/pset3.pdf
- https://madars.org/projects/6854/AlgMatching.pdf
- https://www.cs.cmu.edu/~15850/notes/lec8.pdf
- https://www.math.uwaterloo.ca/~harvey/W11/Matching.pptx
TBD : https://web.eecs.umich.edu/~pettie/matching/Rabin-Vazirani-randomized-maximum-matching.pdf -> peut être amélioré. Micali-Vazirani : https://arxiv.org/pdf/2012.03582
TBD : Harvey 2006, le mieux, Las Vegas :