| TD1: | Cyber-profiler |
| TD2: | Dans la forêt |
| TD3: | Algorithme de Floyd |
| TD4: | Champollion |
| TD5: | Sur Ford et Fulkerson |
|
Note : Il n'est pas demandé de rapport pour ces TD. Des questions concernant les TD pourront être incluses dans les examens partiel et/ou final.
Un graphe est dit hamiltonien s'il est possible de le parcourir en passant une et une seule fois par chacun de ses sommets et en revenant à son point de départ. Pouvez-vous prouver que le graphe ci-dessus est hamitonien ? Dans le cas général, montrer qu'un graphe donné est hamiltonien est un problème difficile. La similitude de ce problème avec celui du graphe eulérien n'est qu'apparente. Le mathématicien W.R. Hamilton a travaillé sur ce problème, il a également inventé un jeu de société sur le même thème. Pour en savoir plus... |
