- introduction aux graphes
- cours sur les graphes. Term NSI
- algorithmes de parcours des graphes
- TP sur l’implementation en python des graphes
- TP sur les algorithmes de parcours des graphes (app en ligne)
- algorithme de Dijkstra
- Protocoles de routage
- Arbres
Utiliser un outil en ligne
Pour une première approche du traitement sur un graphe: Ouvrir l’application en ligne https://graphonline.ru/fr/
Plus court chemin
Vous pourrez alors créer un premier graphe de type: sous-réseaux en étoile. Ce graphe pourrait être la représentation d’un réseau social, ou bien de 2 sous-réseaux interfacés par un routeur.
Une fois le graphe réalisé, explorer le menu des Algorithmes, et sélectionner:
- le degré des sommets
- le rayon du graphe
- l’arbre couvrant minimal
- la Recherche du plus court chemin entre 2 sommets du graphe.
Combien d’arêtes séparent les sommets les plus éloignés de ce graphe?
Chemin Eulérien
La page wikipedia présente ce qu’est un chemin eulérien.
Représenter chacun des 2 graphes suivants, l’un après l’autre, et chercher la présence (ou non) d’un chemin eulérien dans une telle figure.
Q.a: Comment modifier (à minima) le graphe 2 pour qu’il présente un chemin eulérien?
Liens
- Documentation de python networkx
- Programmes python pour le parcours en largeur et en profondeur d’un graphe
- La sociologie structurale, appelée maintenant analyse de réseaux a développé une grande panoplie de métriques pour caractériser les réseaux sociaux… Mémoire de maitrise par FRANCK GOUDJO sur la Réalisation d’un outil de simulation de réseaux sociaux
