Théorie des graphes

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.

Introduction générale

Colorabilité d'un graphe

Graphes Planaires

TBD le reste est en chantier.

générer des graphes

• à sommets fixé

• Markov sur graphes : 2 cas : graphe de sommets ou structure

  • puis Markov sur euler
  • toutes les arborescence avec Markov

Euler et hamilton

TBD degrés : euler clair pair / ham et degré. Prop de Chvatal.

TBD générer des graphes avec degrés fixe pour essayer nos algorithmes TBD on random des nombres dans une borne et on continue le montre avec des matrices, nous juste avec un graphe.

postier chinois et chritofides après couplage. TBD voir comment faire pour aller mieux -> pb du couplage. TBD à la fin du couplage. Se poser la question de résolution exacte ? NP-complet. et on y va.

Projet graphes d'intervalles

1. meurtre
2. caractérisation Gilmore–Hoffman, forme "ordre des sommets"

Il existe n ordre linéaire entre les sommets te que x < y < z si xz est une arête alors xy aussi

, l'ensemble de ses voisins situés après lui dans l'ordre forme un bloc consécutif d'indices.

Chemins de longueur/poids minimum

Problème et algorithmes

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.

Chemins et cycles

Projet :

Graphe à degré fixé

• formule de Erdos-Gallai
• existence de graphes réguliers
• connexités des graphes à sommets fixé preuve de Ryker sur les matrices 0/1

tous les graphes à suite de degré fixé Bender–Canfield 1978, affiné par McKay et McKay–Wormald TBD connexité https://www.cambridge.org/core/services/aop-cambridge-core/content/view/4BE766CCFDF1704C196AA182C0C5EC88/S0008414X00044734a.pdf/combinatorial_properties_of_matrices_of_zeros_and_ones.pdf

Markov sur graphes

TBD MCMC : https://www.youtube.com/watch?v=nndtTssgtZE

TBD deux convergences possible si bi-parti ou pas.

TBD markov sur graphe 2 critères de convergence :

1. P^n > 0
2. 1./p P^n pour graphe bi parti (ex arbre)

Utilisation pour tirer :

• un graphe à sommet fixé aléatoire
• trouver une arborescence aléatoire : Aldous-Broder

TBD compter arbres couvrant markov simple TBD Amélioration sur arbre avec Kirchoff sur graphe valué.

application : créer un labyrinthe : https://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm https://epubs.siam.org/doi/10.1137/0403039

Chemins le plus long

graphes-hamiltoniens

TBD à transformer en voyageur de commerce

Hamilton : hamiltonian ciruits in random graph (posa) et Fast probabilistic algorithms for hamiltonian circuits and matchings

Projets chemin (mettre de l'ordre)

Arbres

TBD projets/applications Buneman ET MPCI 24-25 TBD X-arbre et représentation combinatoire des arbres par bi-partition. TBD c'est l'ET 2024-2025 TBD évolution arborée et distance d'évolution. Condition des 4-points.

Problèmes de flots

Problèmes de flots. Définition, algorithmes et applications

Principes et algorithmes

Modélisation

Graphe biparti

Une classe particulières de graphes cruciale :

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.

Graphes aléatoires

TBD Lemme local de Lovász https://www.imo.universite-paris-saclay.fr/~nicolas.curien/cours/cours-RG.pdf https://www.youtube.com/watch?v=LnApSsurrZU TBD méthode proba (debut) utilisation pour affiner la minoration des nbs de ramsey et lemme local de Lovasz (fin de la video): https://www.youtube.com/watch?v=dmOPl9RtG7o&list=PLUl4u3cNGP61cYB5ymvFiEbIb-wWHfaqO&index=3