ROBERT TARJAN

PRIX TURING 1986
PAGE
BIO
DEDALE
GRAPHE




" Pour leur travaux sur la création et l'analyse de structures de données "
avec John Hopcroft



Robert Endre Tarjan (né le 30 avril en 1948 à Pomona en Californie ) est un informaticien américain. Il a découvert de nombreux algorithmes en théorie des graphes . Il a reçu le prix Turing

Il est professeur en informatique à l'université de Princeton

*

Les graphes et leurs algorithmes

La notion de graphe est une structure combinatoire permettant de représenter de nombreuses situations rencontrées dans des applications faisant intervenir des mathématiques discrètes et nécessitant une solution informatique. Circuits électriques, réseaux de transport (ferrés, routiers, aériens), réseaux d'ordinateurs, ordonnancement d'un ensemble de tâches sont les principaux domaines d'application où la structure de graphe intervient. ens uqac ca

On considère généralement que le problème des ponts de Königsberg, résolu par Euler, est le premier résultat formel de la théorie des graphes. Elle s'est surtout développée depuis la deuxième moitié du 19ème siècle (avec Hamilton, Heawood, Kempe, Kirchhoff, Petersen, Tait), et connait un grand boom depuis les années 30 (avec König, Hall, Kuratowski, Whitney, Erdös, Tutte, Edmonds, Berge, Lovász, Seymour, et beaucoup d'autres). Elle présente des liens évidents avec l'algèbre, la topologie, et d'autres domaines de la combinatoire. On trouve des applications de la théorie des graphes -- et souvent aussi la motivation de nouveaux problèmes -- en informatique, recherche opérationnelle, théorie des jeux, théorie de la décision.

La quantité de notions que l'on peut définir sur un graphe est très grande, et plusieurs d'entre elles sont à l'origine de problèmes ou conjectures célèbres (par exemple le problème des quatre couleurs). En fait, un certain nombre de ces notions et questions "théoriques" sont issues non pas de l'imagination des mathématiciens mais de problèmes pratiques qui se modélisent en termes de graphes. De plus, les chercheurs en théorie des graphes s'attachent souvent à trouver des algorithmes efficaces pour résoudre un problème donné.

Les grands problèmes classiques de la théorie des graphes sont : flots et connectivité ("fiabilité" d'un réseau), couplage (affectation), parcours eulérien (qui traverse chaque arête : problème du "postier chinois"), parcours hamiltonien (qui traverse chaque sommet : problème du "voyageur de commerce"), coloration, ensemble stable, ensemble absorbant. Certains de ces problèmes (flot maximum, couplage maximum, parcours eulérien) peuvent être résolus "efficacement", mais la plupart sont très difficiles ("NP-complets").

Une généralisation récente du concept de graphe, introduite par Claude Berge dans les années 60, est celle d'hypergraphe, où les arêtes peuvent être de taille arbitraire et non plus seulement de taille deux leibniz imag