Le dessin pour comprendre

”Faut t’faire un dessin?”. La repr´esentation d’un probl`eme par un dessin, un plan, une

esquisse contribue souvent `a sa compr´ehension. Le langage des graphes est construit, `a l’origine,

sur ce principe. Nombres de m´ethodes, de propri´et´es, de proc´edures ont ´et´e pens´ees ou

trouv´ees `a partir d’un sch´ema pourˆetre ensuite formalis´ees et d´evelopp´ees. Chacun d’entre nous

a, au moins une fois, vu ou utilis´e un plan de m´etro, une carte de lignes ferroviaires, un plan

´electrique, un arbre g´en´ealogique ou un organigramme d’entreprise; ainsi, tout le monde sait

plus ou moins intuitivement ce qu’est un graphe. Toutefois, entre cette notion vague o`u des

points, repr´esentant des individus, des objets, des lieux ou des situations, sont reli´es par des

fl`eches, il y a une longue ´elaboration des concepts. La premi`ere difficult´e `a laquelle on peut ˆetre

confront´e concerne la terminologie (tr`es abondante en th´eorie des graphes). Nous avons donc

choisid’isolerlesprincipalesd´efinitionsduresteducoursenutilisantunemiseenpagediff´erente.

La th´eorie des graphes constitue aujourd’hui un corpus de connaissances tr`es important.

Commesonnoml’indique,cecoursneconstitueradoncqu’uneintroduction`acetteth´eorie.Nous

le pr´eciserons ult´erieurement, le d´eveloppement de cette th´eorie doit beaucoup `a celui des calculateurs.

Il nous a donc sembl´e incontournable d’exposer quelques algorithmes de base (recherche

de chemin, d’arbre, de flots, etc.). Cependant, ceci ne constitue pas le corps de cet enseignemen

”Faut t’faire un dessin?”. La repr´esentation d’un probl`eme par un dessin, un plan, une

esquisse contribue souvent `a sa compr´ehension. Le langage des graphes est construit, `a l’origine,

sur ce principe. Nombres de m´ethodes, de propri´et´es, de proc´edures ont ´et´e pens´ees ou

trouv´ees `a partir d’un sch´ema pourˆetre ensuite formalis´ees et d´evelopp´ees. Chacun d’entre nous

a, au moins une fois, vu ou utilis´e un plan de m´etro, une carte de lignes ferroviaires, un plan

´electrique, un arbre g´en´ealogique ou un organigramme d’entreprise; ainsi, tout le monde sait

plus ou moins intuitivement ce qu’est un graphe. Toutefois, entre cette notion vague o`u des

points, repr´esentant des individus, des objets, des lieux ou des situations, sont reli´es par des

fl`eches, il y a une longue ´elaboration des concepts. La premi`ere difficult´e `a laquelle on peut ˆetre

confront´e concerne la terminologie (tr`es abondante en th´eorie des graphes). Nous avons donc

choisid’isolerlesprincipalesd´efinitionsduresteducoursenutilisantunemiseenpagediff´erente.

La th´eorie des graphes constitue aujourd’hui un corpus de connaissances tr`es important.

Commesonnoml’indique,cecoursneconstitueradoncqu’uneintroduction`acetteth´eorie.Nous

le pr´eciserons ult´erieurement, le d´eveloppement de cette th´eorie doit beaucoup `a celui des calculateurs.

Il nous a donc sembl´e incontournable d’exposer quelques algorithmes de base (recherche

de chemin, d’arbre, de flots, etc.). Cependant, ceci ne constitue pas le corps de cet enseignemen

”Faut t’faire un dessin?”. La repr´esentation d’un probl`eme par un dessin, un plan, une

esquisse contribue souvent `a sa compr´ehension. Le langage des graphes est construit, `a l’origine,

sur ce principe. Nombres de m´ethodes, de propri´et´es, de proc´edures ont ´et´e pens´ees ou

trouv´ees `a partir d’un sch´ema pourˆetre ensuite formalis´ees et d´evelopp´ees. Chacun d’entre nous

a, au moins une fois, vu ou utilis´e un plan de m´etro, une carte de lignes ferroviaires, un plan

´electrique, un arbre g´en´ealogique ou un organigramme d’entreprise; ainsi, tout le monde sait

plus ou moins intuitivement ce qu’est un graphe. Toutefois, entre cette notion vague o`u des

points, repr´esentant des individus, des objets, des lieux ou des situations, sont reli´es par des

fl`eches, il y a une longue ´elaboration des concepts. La premi`ere difficult´e `a laquelle on peut ˆetre

confront´e concerne la terminologie (tr`es abondante en th´eorie des graphes). Nous avons donc

choisid’isolerlesprincipalesd´efinitionsduresteducoursenutilisantunemiseenpagediff´erente.

La th´eorie des graphes constitue aujourd’hui un corpus de connaissances tr`es important.

Commesonnoml’indique,cecoursneconstitueradoncqu’uneintroduction`acetteth´eorie.Nous

le pr´eciserons ult´erieurement, le d´eveloppement de cette th´eorie doit beaucoup `a celui des calculateurs.

Il nous a donc sembl´e incontournable d’exposer quelques algorithmes de base (recherche

de chemin, d’arbre, de flots, etc.). Cependant, ceci ne constitue pas le corps de cet enseignemen

”Faut t’faire un dessin?”. La repr´esentation d’un probl`eme par un dessin, un plan, une

esquisse contribue souvent `a sa compr´ehension. Le langage des graphes est construit, `a l’origine,

sur ce principe. Nombres de m´ethodes, de propri´et´es, de proc´edures ont ´et´e pens´ees ou

...