Titre :	Au delà des ponts de Königsberg : théorie des graphes ; problèmes ,Théorèmes ,Algorithmes
Type de document :	texte imprime
Auteurs :	Olivier Gogis ; Claudine Robert
Mention d'édition :	2e tirage revu et corrigé
Editeur :	Paris : Vuibert
Année de publication :	DL 2003
Importance :	251 p.
Présentation :	ill., couv. ill. en coul.
Format :	25 cm
ISBN/ISSN/EAN :	978-2-7117-5321-5
Note générale :	Autre tirage : 2005 Bibliogr. p. 249-251. Index
Langues :	Français
Mots-clés :	Graphes, Théorie des  Informatique:mathématiques  Résolution de problème :informatique  Algorithmes
Index. décimale :	511
Résumé :	Un graphe se définit simplement comme un ensemble de points dont certains sont reliés par des lignes. Un des exemples les plus répandus est le problème dit « du voyageur de commerce » : il s’agit de tracer le plus court chemin que pourrait emprunter un représentant pour rendre visite à ses clients dans une série de villes, en ne passant qu’une seule fois dans chaque ville. Cette méthode mathématique est une branche de la combinatoire; développée par des théoriciens à la fin du XIXe siècle, elle a trouvé des applications dans le calcul des probabilités avant d’être profondément renouvelée dans les années 60 (notamment par Claude Berge en France). Ses applications actuelles sont orientées vers l’informatique, d’où son intérêt grandissant. Les graphes ont récemment fait leur entrée dans les programmes de mathématiques de l’enseignement secondaire et dans de nombreux cursus post-bac, tant en France qu’à l’étranger. La théorie des graphes est régulièrement évoquée pour résoudre des problèmes classiques (la promenade sur les ponts de Königsberg, la coloration de cartes géographiques) ou d’autres problèmes liés au fonctionnement de notre société (transport, réseaux de communication, architectures informatiques). Si elle convainc par son utilité pratique, on peut légitimement se demander en quoi des objets aussi pauvres – des points reliés par des lignes – peuvent engendrer des problématiques incontestablement riches. Cet ouvrage rend compte des trois composantes de la théorie des graphes : la résolution des problèmes, les mathématiques discrètes et l’algorithmique. Les auteurs visent un double objectif : satisfaire une juste curiosité mathématique et procurer une base solide pour une étude approfondie.
Note de contenu :	1. Généralités : graphes, degré, isomorphisme 2. Euler et Hamilton 3. Comment colorer un graphe (graphe et algorithme glouton) 4. Arbres 5. Couplages et couvertures 6. Connexité 7. Graphes planaires 8. Graphes complets : algorithme de Prüfer Bicoloration : nombre de Ramsey 9. Algorithmes et preuves dÂ’algorithmes - Index et notations - Bibliographies et autres sources documentaires (Articles de revues, sites Web, logiciels)
Permalink :	./index.php?lvl=notice_display&id=12630

Au delà des ponts de Königsberg : théorie des graphes ; problèmes ,Théorèmes ,Algorithmes [texte imprime] / Olivier Gogis ; Claudine Robert  . -  2e tirage revu et corrigé . - Paris : Vuibert, DL 2003 . - 251 p. : ill., couv. ill. en coul. ; 25 cm.
ISBN : 978-2-7117-5321-5
Autre tirage : 2005
Bibliogr. p. 249-251. Index

Langues : Français

Mots-clés :	Graphes, Théorie des  Informatique:mathématiques  Résolution de problème :informatique  Algorithmes
Index. décimale :	511
Résumé :	Un graphe se définit simplement comme un ensemble de points dont certains sont reliés par des lignes. Un des exemples les plus répandus est le problème dit « du voyageur de commerce » : il s’agit de tracer le plus court chemin que pourrait emprunter un représentant pour rendre visite à ses clients dans une série de villes, en ne passant qu’une seule fois dans chaque ville. Cette méthode mathématique est une branche de la combinatoire; développée par des théoriciens à la fin du XIXe siècle, elle a trouvé des applications dans le calcul des probabilités avant d’être profondément renouvelée dans les années 60 (notamment par Claude Berge en France). Ses applications actuelles sont orientées vers l’informatique, d’où son intérêt grandissant. Les graphes ont récemment fait leur entrée dans les programmes de mathématiques de l’enseignement secondaire et dans de nombreux cursus post-bac, tant en France qu’à l’étranger. La théorie des graphes est régulièrement évoquée pour résoudre des problèmes classiques (la promenade sur les ponts de Königsberg, la coloration de cartes géographiques) ou d’autres problèmes liés au fonctionnement de notre société (transport, réseaux de communication, architectures informatiques). Si elle convainc par son utilité pratique, on peut légitimement se demander en quoi des objets aussi pauvres – des points reliés par des lignes – peuvent engendrer des problématiques incontestablement riches. Cet ouvrage rend compte des trois composantes de la théorie des graphes : la résolution des problèmes, les mathématiques discrètes et l’algorithmique. Les auteurs visent un double objectif : satisfaire une juste curiosité mathématique et procurer une base solide pour une étude approfondie.
Note de contenu :	1. Généralités : graphes, degré, isomorphisme 2. Euler et Hamilton 3. Comment colorer un graphe (graphe et algorithme glouton) 4. Arbres 5. Couplages et couvertures 6. Connexité 7. Graphes planaires 8. Graphes complets : algorithme de Prüfer Bicoloration : nombre de Ramsey 9. Algorithmes et preuves dÂ’algorithmes - Index et notations - Bibliographies et autres sources documentaires (Articles de revues, sites Web, logiciels)
Permalink :	./index.php?lvl=notice_display&id=12630