saemath

Implémentation et comparaison d'algorithmes de graphes en Python — plus courts chemins et seuil de forte connexité.

Projet réalisé dans le cadre de la SAE Maths (exploration algorithmique d'un problème).
Auteurs : Alet · Decker · Antoine · Biais

---

Sommaire

• Présentation
• Fonctionnalités
• Structure du projet
• Prérequis
• Installation
• Utilisation
• Exemples de résultats
• Licence

---

Présentation

Ce projet explore deux problèmes algorithmiques sur les graphes :

1. Plus courts chemins — comparaison empirique de Dijkstra et Bellman-Ford (avec variantes BFS/DFS), mesure des complexités réelles par régression log-log.
2. Forte connexité — estimation statistique du seuil de probabilité à partir duquel un graphe orienté aléatoire est fortement connexe avec 99 % de certitude, puis modélisation de ce seuil par une loi puissance.

---

Fonctionnalités

Partie I — Plus courts chemins

Fonction	Description
graphe(n, a, b)	Graphe orienté aléatoire (~50 % d'arcs)
graphe2(n, p, a, b)	Graphe orienté aléatoire avec probabilité d'arc p
graphe3(n, p, a, b)	Graphe non orienté symétrique avec probabilité p
Dijkstra(M, d)	Plus courts chemins depuis d (poids positifs uniquement)
Bellman_Ford(M, d)	Plus courts chemins depuis d (poids négatifs autorisés, détection de cycles négatifs)
Bellman_Ford_variante(M, d, mode)	Bellman-Ford avec ordre BFS / DFS / aléatoire
parcours_largeur(M, s)	Parcours en largeur (BFS)
parcours_profondeur(M, s)	Parcours en profondeur (DFS)
plot_comparaison_temps()	Graphique comparatif des temps (densité fixe)
plot_comparaison_temps_variable()	Graphique comparatif des temps avec p = 1/n
estime_exposant(...)	Régression log-log pour estimer les exposants de complexité
afficher_graphe_oriente(...)	Visualisation PNG via Graphviz

Partie II — Forte connexité

Fonction	Description
graphe_connexite(n, p)	Graphe orienté binaire aléatoire
cloture_transitive(M)	Clôture transitive (Floyd-Warshall binaire)
est_fortement_connexe(M)	Test de forte connexité
taux_forte_connexite(n, p, nb_essais)	Estimation statistique par simulation
seuil_forte_connexite(n)	Seuil minimal p pour 99 % de forte connexité
plot_evolution_seuil(min_n, max_n)	Graphique d'évolution du seuil
analyse_seuil_log_log(min_n, max_n)	Régression log-log du seuil

---

Structure du projet

saemath/
│
├── functions.py   # Toutes les fonctions (bibliothèque pure, aucun appel direct)
├── main.py        # Interface utilisateur en console — point d'entrée
├── examples.py    # Démonstrations avec valeurs fixes pour chaque fonction
└── README.md

Lancer le projet :

python main.py

Les trois fichiers doivent se trouver dans le même répertoire.

---

Prérequis

• Python 3.8 ou supérieur
• Graphviz installé sur le système (pour la visualisation des graphes)

---

Installation

# Cloner le dépôt
git clone https://github.com/Jean-Alet/saemath.git
cd saemath

# Installer les dépendances Python
pip install numpy matplotlib scipy graphviz

Windows / macOS : installez également Graphviz depuis graphviz.org et ajoutez-le au PATH.

---

Utilisation

Lancer l'interface

python main.py

Le menu principal propose :

══════════════════════════════════════════════════════════
  SAE Maths — Exploration algorithmique
══════════════════════════════════════════════════════════
  1. Algorithmes de plus courts chemins
  2. Seuil de forte connexité
  3. Exemples de test (valeurs fixes pour chaque fonction)
  0. Quitter

Utiliser les fonctions directement

from functions import Dijkstra, Bellman_Ford, graphe3

# Créer un graphe aléatoire (10 sommets, densité 30 %)
M = graphe3(10, 0.3, 1, 10)

# Plus court chemin depuis le sommet 0
resultats = Dijkstra(M, 0)
for dest, val in resultats.items():
    print(dest, val)

Lancer tous les exemples

python examples.py

---

Exemples de résultats

Dijkstra — graphe à 5 sommets

→ Sommet 0 : distance = 5,   chemin = 1 → 4 → 0
→ Sommet 2 : distance = 3,   chemin = 1 → 2
→ Sommet 3 : distance = 5,   chemin = 1 → 2 → 3
→ Sommet 4 : distance = inf  (non joignable)

Seuil de forte connexité

n =  5  →  seuil p ≈ 0.64
n = 10  →  seuil p ≈ 0.47
n = 15  →  seuil p ≈ 0.39
n = 20  →  seuil p ≈ 0.34

La régression log-log identifie une loi puissance de la forme :

seuil(n) ≈ c × n^a   avec a ≈ -0.50

---

Licence

Ce projet est distribué sous licence CC BY-NC 4.0 (Creative Commons Attribution — Pas d'Utilisation Commerciale).

Vous êtes autorisé à :

• Consulter, utiliser et partager ce projet à des fins personnelles ou académiques
• Modifier le code pour un usage privé ou éducatif

Sous les conditions suivantes :

• Attribution — Vous devez créditer les auteurs (Alet, Decker, Antoine, Biais) et indiquer si des modifications ont été apportées
• Pas d'utilisation commerciale — Ce projet ne peut pas être utilisé à des fins commerciales ou lucratives

Toute utilisation en dehors de ces conditions nécessite une autorisation écrite préalable des auteurs.