Introduction à la théorie des graphes

À partir des définitions générales sur de leur utilité algorithmique et pratique, nous allons raconter une histoire à priori simple dont les ramifications vont nous montrer de nombreuses facettes de la théorie des graphes.

Structure d'un graphe

Connexités :

Graphes Eulérien

L'origine de la théorie des graphe :

Et une conséquence inattendue (exercice de modélisation) :

ICI graphes eulériens.

1. combien il y en a
2. graphes : 1. nombre diff. à sommet fixer 2. pb de l'isomorphisme de graphe (aller plus loin dans une autre partie)
3. idée pour les trouver puis formules
4. générer un graphe aléatoire : Erdos reny. Intro + graphe Rado + isomorphisme
5. distribution des degrés pairs ? Y'en a qui existent pas.
6. formule générale + algo pour en trouver 1
7. suite décroissantes -> graphes EUlérien et généraux
8. les trouver tous ? Au moins aléatoirement.

TBD existence de ce que l'on cherche avec une forte proba mais impossible à trouver en pratique https://www.youtube.com/watch?v=4weMmFZSBtI 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 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 le montre avec des matrices, nous juste avec un graphe.

Graphes Hamiltoniens

TBD ce qu'on a fait avec ds arêtes pourquoi pas le faire avec des sommets ?

TBD :

1. définition du problème.
2. cas où on sait le faire :
3. tournoi + méthode probabiliste (cf ds 2026)
4. degrés
5. arbres + partie arbres (déf + ALM)
6. acyclique : et conséquence inattendue sr le BTP
7. cas général métrique et complet
8. pas simple : exhaustif avec backtrack + branch and bound
9. approximation : 1. 2-opt 2. performance garantie :
   1. algo + ALM
   2. idée du couplage (avec performance garantie mais si on pouvait faire ça mieux ce serait bien !)
10. couplage : ici juste complet avec méthode hongroise.

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. TBD ci NP algo