INF 435 A : Théorie et applications des graphes


Retour
Imprimer la fiche programme
Code analytique: EDOINFMA2
Responsable  :    
Programmé en UV2 MAJ INF

Présentation :

Le but de ce module est d'apporter à l'élève les connaissances fondamentales de la théorie de graphes et la capacité de reconnaître l'apport des graphes dans une multitude de situations et de proposer et de mettre en œuvre une solution en utilisant les algorithmes appropriés. Cinq domaines de la théorie de graphes seront étudiés : les arbres couvrants, la planarité, la coloration, les réseaux de transport et les cycles hamiltoniens. Dans chaque cas on verra des exemples d'application, la théorie mathématique sous-jacente et les aspects algorithmiques. En Travaux Pratiques les élèves vont implémenter les algorithmes dans le langage Python.

La méthodologie pédagogique de ce module est basée sur la jonction et l'interaction entre théorie et pratique, en suivant le schéma : problème confronté en TP, modélisation de problème en terme de graphes, outils mathématiques appropriés, outils algorithmiques appropriés, implémentation de la solution. Ainsi, on n'écartera pas les démonstrations de propositions mathématiques, quand celles-ci comportent des idées qui permettent de mieux assimiler les concepts. De même, on n'écartera pas l'écriture et le débogage de code, lorsque ceux-ci permettent de suivre concrètement l'application d'un algorithme.

Il est un principe connu que le métier d'ingénieur demande aussi bien la compréhension (théorique) que l'application (pratique). Tour à tour mathématicien et programmeur, l'élève trouvera dans ce module une illustration de ce principe.


Volume horaire : 21h


Contenu détaillé :

Bureau d'études 1 (1 h 30)

Introduction aux graphes par des exemples :
- sommets, arcs
- les notions de degré et diamètre
- l'orientation, les cycles, les arbres
- les composantes connexes

Cours 1 (1h30)

Définitions générales et formalisation des concepts vus précédemment :
- sommets, arêtes, sous-graphes, graphes partiels, homomorphismes
- ordre, taille, degré, marche, chemin, connexité
- sommets d'articulation, isthmes, cycles
- discrétion, complétude, cliques, stables, graphes bipartis

Cours 2 (3h)

— représentation du graphe en mémoire
— matrices d'adjacence
— parcours du graphe en profondeur d'abord
— parcours du graphe en largeur d'abord
— détermination algorithmique de composantes connexes
— problème du plus court chemin, algorithme de Dijkstra

— PROBLÈME : la création d'un circuit électronique
— PROBLÈME : trois usines fournissent eau, gaz et électricité à trois maisons
— planarité
— théorème d'Euler
— théorème de Kuratowski

Cours 3 (3h)

— PROBLÈME : la distribution de gaz au niveau d'une ville
— arbres, arbres couvrants
— théorème de Cayley
— arbres minimaux
— calcul des arbres de recouvrement
— algorithmes de Kruskal, Prim, Sollin

Cours 4 (3 h)

— PROBLÈME : optimiser les performances d'une flotte marchande
— flots et réseaux de transport
— théorème de Ford-Fulkerson

— PROBLÈME : combien de couleurs faut-il pour colorier une carte ?
— nombre chromatique
— théorème des quatre couleurs (sans démonstration !)
— théorème des cinq couleurs
— polynôme chromatique d'un graphe

Travaux personnels encadrés :

TP 1 : le club de karaté (3h)

À partir du graphe «réseau social du club de karaté», deux questions :
- existe-t-il une chaine de relations entre deux individus ?
- quelle est la chaine la plus courte entre deux individus ?

Les étudiants rendent une argumentation de leur choix de représentation du graphe et des algorithmes proposés.

TP 2 : le téléphone arabe (3h)

À partir d'un graphe valué «réseau social» dans lequel à chaque arête est associée une durée en minutes, deux questions :
- quel est le temps minimal pour qu'une rumeur partant d'un individu atteigne tout le monde ?
- sachant qu'à chaque passage d'information, 10% du contenu est perdu, quelle est la déviation sémantique minimale ?

Les étudiants rendent une argumentation de leur choix de représentation du graphe et des algorithmes proposés.

TP 3 : la victoire est en nous (3h)

À partir d'un graphe valué «lignes de métro», le souhait est que le maximum de monde puisse atteindre la station Champs-Elysées depuis le Stade de France :
- combien de personnes peuvent atteindre les Champs-Elysées ?
- si certains transports doivent contenir au moins quelques personnes pour partir, la même question.

Les étudiants rendent une argumentation de leur choix de représentation du graphe et des algorithmes proposés.


Année 2007/2008
Dernière mise à jour le 14-NOV-07
Validation par le responsable de programme le


IMT Atlantique
Campus de Brest
Technopôle Brest-Iroise
CS 83818
29238 Brest Cedex 3
France

Tél  +33 (0)2 29 00 11 11
Fax +33 (0)2 29 00 10 00