Tangent e
Tangent e
Tangent e
Représenter
et les
Bibliothèque
'.I'cing L ' aventure ?nat'ké?natiq"e
e
Tangente Hors-série n° 54
les graphes
Représenter les données
et les stratégies
i;DITIONS ~
POLE ~
EDITIONS.
POLE
les graphes
Les onze états du taureau de Picasso
Tous les chemins mènent à Konigsberg
DOSSIER
Quelques points et des traits pour les relier suffisent à
créer un graphe. Une idée aussi simple se devait
d'engendrer un monde foisonnant d 'objets : les idées
les plus élémentaires sont souvent les plus riches !
DOSSIER
La théorie des graphes permet de comprendre, voire
de résoudre une grande quantité de jeux de réflexion
ou de jeux mathématiques et logiques, parfois de
manière inattendue (voir à ce sujet le numéro 46 de la
Bibliothèque Tangente). A contrario, les graphes
peuvent être à la source d ' une catégorie de
récréations dont les plus classiques sont des
problèmes de labyrinthes.
En bref
Glossaire
Il peut paraître urprenant que le mot graphe soit apparu dans notre langue assez récemment, vers
le début du xx:e iècle, et qu'il nou vienne ... de l' anglais. Pourtant, ce terme e retrouve comme
seconde partie de mot beaucoup plu anciens. Ainsi « orthographe » voit le jour à la Renaissance ;
ile t calqué sur un homonyme latin orthographia, à une époque où l'on devient soucieux d' une écri-
ture acceptée par tous . Le mot « télégraphe », pour sa part, est créé en 1792 pour désigner un appa-
reil pouvant tran mettre graphiquement des signaux. Leur suffixe commun est bien sûr issu d'une
racine grecque, graphein, qui signifie «écrire » ; le terme graphê désigne quant à lui tant l'écriture
que ce qui est écrit.
Si l'on en croit le Dictionnaire historique de la langue française dirigé par Alain Rey, le mot graph
apparaît en anglais comme abréviation de graphicformula d'abord dans le langage de la chimie. On
le trouve utilisé en mathématiques ver 1880. Cependant, sa première atte tation dan notre langue
daterait seulement de 1926. Son utilisation devient alors courante pour désigner la repré entation gra-
phique d' une fonction.
L'émancipation de la théorie des graphes comme di cipline autonome.juste avant la Seconde Guerre
mondiale , donne une nouvelle jeune e à ce terme, avec comme point de départ le livre du mathé-
maticien hongroi s Déne Kônig , Theorie der endlichen und unendlichen Graphen, paru en 1936.
Cet ouvrage est uivi en 1958 de celui de Claude Berge, Théorie des graphes et ses applications .
Le mathématicien français introduit peu après la notion et le terme « hypergraphe ».
De nos jour , le mot graphe, par-delà e acceptions mathématique , est devenu un terme courant,
montrant que la science concourt elle aussi à enrichir la langue .
N
0
0
N
ô
V,
V,
"'
(.)
0::
c::
0
,;;
V,
<1)
(.)
(.)
;::I
r/J
(Q
Que lle est donc la structure mathé ma- avec un squelette n'éta it pa u urpée. 11
tique qui permet de rendre compte le plus est par a ill e urs c lair qu e, dans cette
efficaceme nt poss ible de la s itu ation figure, la forme préci e des lignes reliant
des sept ponts ? Que l est ce sque lette les points n' a pas d ' importance : seul
abstra it qui résume toute les données compte que ce ligne indiquent les li ai-
de la configuration topographique de la sons poss ibles entre les points (c'est, là
ville de Konigsberg? Ce squelette, c'e t e ncore, une illu stration du ca ractère
un g raphe : lorsque Euler résout le pro- topologique et non géométrique du pro-
blème des sept ponts, il fonde ainsi du blème étudié).
même coup la théorie des graphes, appe- À partir du graphe de Konigsberg, la
lée à jouer un rôle majeur avec l'émer- question des sept ponts se reformule de
gence de l' informatique. la manière sui vante : comment , partant
de l' un des quatre points (G , D, I ou J),
Un squelette de sept points peut-on colorier au crayon la totalité des
lignes du graphe ans repasser deux fo is
L' idée est la sui vante: la ville de Konig- par la même ligne et sans lever le crayon ?
sberg est la réunion de quatre morceaux
re liés entre eux par différents pont . La Ce qui est en jeu ici est la con truction
forme de ces morceaux n'a guère d ' im- de ce que l' on appelle depui s un che-
portance : seul s comptent les ponts qui min eulérien , c'est-à-dire un chemin qui
les re lient. 11 est donc possible de repré- parcourt tout le graphe ans pa ser deux
senter chaque morceau de la ville par fo is sur la même arête et sans que oit
un simple point (une î le, i l' on veut), effectué de « saut ». Euler a donné la
duque l partent des pont vers les autres olution générale à ce problème ; plus
points (ou les autre île ). Si l'on nomme préc isément , que l que so it le graphe
G et D les points repré entant les deux considéré (ce lui de Konigsberg ou un
ri ves, 1 la petite î le et enfin J la terre autre), il est poss ible, d 'ailleurs assez
émergée entre les deux bras de la ri vière, fac ilement , de savoir si un chemin eulé-
la représentation de la situation est alors rien ex iste ou non (voir en encadré) : il
la sui vante : suffit de compter, pour chaque sommet,
J le nombre d 'arêtes qui en partent. S' il
y a plus de deux sommets pour lesquels
le nombre en question est impair, alors
la répon e e t négati ve. Sinon , un che-
min ex iste .
S 'agissant du graphe de Koni gsberg, le
décompte n'est pas long : un no mbre
impair d 'arêtes part de chacun des som-
mets, un touriste ne peut donc pas vi i-
ter tous les pont une fo is et une eule.
G D
Dans une autre ville, avec de ponts dis-
po és di ffé remme nt , un chemin eulé-
rien aurait pu ex ister et, dans ce cas, on
P,
peut penser que les habitants aura ient
C' est le graphe de Konigsberg. Chaque eu tôt fa it de trouver eux-mêmes la solu-
ligne re li ant deux points symboli se un tion. À Koni gsberg, tant que les essais
pont , et l'on vo it que la comparaison de me urai e nt infructueux, la question
À part pour les points de départ et d'arrivée, on voit donc que, les arêtes étant retirées de
deux en deux, il est nécessaire que chaque sommet dispose au départ d'un nombre pair
d'arêtes pour que puisse exister un chemin eulérien. Si un sommet possède un nombre
impair d'arêtes, alors ce sommet est le point de départ ou d'arrivée.
Inversement, un graphe dans lequel ne se trouvent pas plus de deux sommets desquels par-
tent un nombre impair d'arêtes est toujours un graphe eulérien (c'est-à-dire qu'il existe un
chemin eulérien le parcourant) : de même que le mouvement se montre en marchant, on se
persuade facilement de ce résultat en faisant quelques essais (qui ne remplacent pas, bien
entendu, une démonstration dans les règles).
Enfin, si aucun sommet n'a un nombre impair d'arêtes, alors un chemin eulérien est aussi
un cycle, c'est-à-dire que le point de départ se confond avec le point d'arrivée.
demeurait en suspe ns, et le serait res- trouver tous les arbres à 3n + 2 éléments
tée si Euler ne s'était pas attaqué au pro- tels que de chaque élément (chaque som-
blème sous l'angle des graphes et n'avait met) partent exactement une ou quatre
pas eu cette idée d ' un genre si particu- arê tes (sy mboli sant le li aiso ns c hi -
lier consistant à vouloir démontrer qu ' un mique) .
problème ne possède pas de olution. En 1869,enfin , le mathématiciens redé-
couvrent les graphes, par la voix de Jor-
Rprès Kiinigsberg dan qui , sans connaître les travaux de
Cayley, retrou ve ses résultats .
C ' est en 1737 Les jeux ne sont pas en reste : en 1859 ,
qu 'E ul e r a soi t cent vingt-deux ans après les tra-
réso lu le pro- vaux d ' Euler, le mathématicien William
Sir William Rowan blème des sept Hamilton invente le « jeu icosien » (The
Hamilton , père des ponts. Bien que lcosian Game), dans lequel il s'agit de
quaternions point de départ visiter tous les sommets d ' un icosaèdre
et du jeu icosien. de la théorie des régulier (voir la figure) une fois et une
graphes, il fa ut seule. Dans la version de Hamilton , les
tout de même sommets sont dés igné par des villes
a tt e ndre plu s dont la première lettre est une con onne
d ' un siècle avant que celle-c i ne fasse (un e conso nne par vill e , l' icosaèdre
son retour dans l' actualité sc ientifique. ayant autant de sommets que l'alpha-
Alors que la question d'Euler est avant bet possède de con onnes, à savoir 20) :
tout ludique, le x,xe siècle voit un déve- Bruxelles , Canton, Delhi , Francfort, etc .
loppement de la théorie de nature beau- Le problème du jeu icosien est celui des
coup plu s co nc rè te. C 'es t d 'a bord chem ins appelés depui s hamiltoniens ,
Kirchhoff qui , en 1847 , s' intéresse à la dans lesquels il faut visiter tous les som-
quantité de courant qui circule dans les mets une fois et une seule .
différentes branches d'un circujt électrique. Apparemment vois in du problème des
L'auteur des loi s qui portent son nom chemjns eulériens (dans lesquels il fa ut
(aussi appelée la loi des nœuds ou la loi vis iter toutes les arêtes une fois et une
des mailles) développe pour ses pro- seule) , le problème des chem ins hamil-
blè mes la notion d'arbre, c'est-à-dire toni e ns est en réa lité bea ucou p plu s
de graphe sans boucle. difficil e !
Dix ans plus tard , c' est au tour de la chi-
mie de s'attaquer aux graphe . En 1857, Le xxe siècle voit la théorie des graphes
Cay ley s' intéresse en effet aux diffé- prendre son véritable e sor. Utile dans
re nte tructures po ss ibles (o n parl e des domaine comme l'électricité, ell e
d' isomères) d ' une mol éc ule aya nt n a auss i servi à des ét udes psyc ho lo-
atomes de carbone et 2n + 2 atomes giques ou soc iologique (le sommets
d ' hydrogène (ce sont les alcanes). De repré entant des individus et le arêtes
contraintes de nature chimique fo nt que, les relations entre eux) . Toutefois, c'est
dan les alcanes, un atome de carbone surtout l'inform atiqu e qui a favo ri sé
est toujours lié à quatre autres atomes (de l'étude des graphes. Aujourd ' hui , la
carbone ou d ' hydrogène) alors qu ' un théori e des graphes est omniprésente
atome d ' hydrogène est lié à un unique dans la technologie contemporai ne.
atome de carbone . Enfin , les cycles ne
sont pas permis. La question est donc de B.R.
Lestvpes
de graphes
Quelques points et des traits pour les relier suffisent à créer un
graphe. Une idée aussi simple se devait d'engendrer un monde
foisonnant d'objets: les idées les plus élémentaires sont souvent les
plus riches ! Ainsi, l'énoncé du théorème des quatre couleurs est
élémentaire ; pourtant, sa démonstration nécessitera l'utilisation
d ' un ordinateur. Depuis, l'obstination des mathématiciens a eu
raison d'autres résultats puissants. Deux résultats structuraux, le
théorème des graphes parfaits et le théorème des mineurs, comptent
parmi les plus profonds des mathématiques.
Hors-série n°54. Les graphes Tangente (E)
SAVOIRS par Jean-Paul Delahaye
cr' 0 1 3 9 19 36 62
Z(n)=4·1[n]2 .[n-1]
-2- .[n-2]
-2- .[n-3]
-2- . ce n 'est pas le cas, on s'y ramène faci-
le me nt e n dé plaçant légère me nt le des-
sin d ' une arête) ; (b) on interdit à une
L'égalité a été démontrée jusqu'à 12, mais cela a demandé un tra- arête re li ant a et b de se cro iser e lle-
vail considérable. La difficulté provient de ce qu'il existe un très
même, e t e nfin , (c) on inte rdit à une
grand nombre de façons différentes de dessiner le graphe Kn sur
arê te re liant a e t b de pa ser par des
le plan et qu'il fa ut surtout ne pas en manquer pour identifier les
nœ uds du graphe a utre que a et b. JI
dessins qui conduisent à un nombre minimum de croisements.
Les dessins optimaux (voir encadrés « Les meilleurs dessins ,. ) résulte de tout ce la que l'emplace me nt
pour K5 et K6 ne sont pas trop difficiles à trouver. Pour K7 et K8 , des nœuds du graphe G sur le plan est
cela devient déjà plus subtil, surtout qu'il n'y a pas unicité de la solu- sans importance pratique quand on s'oc-
tion donnant le nombre minimum de croisements. L'idée de trou- cupe de cr(G). En effet, s'il existe un des-
ver une disposition optimale de proche en proche en utilisant celle s in des arê tes de G avec r cro iseme nts,
de Kn- • pour trouver celle de Kn est une mauvaise idée, car on a mon- pour une certaine disposition des nœuds
tré que, dans certains cas, les dessins optimaux pour une valeur sur le plan , en déplaçant continûment les
de n ne contiennent aucun dessin optimal pour n - 1. nœ uds e t les arêtes (que l'on a ll o nge
Aller au-delà de 12 est un défi informatique et mathématique. ou déforme i nécessai re), il y a ura un
À défaut d'une démonstration de l'inégalité cr(Kn) .!e Z(n) , on a
dessi n de ar ê te avec r cro ise me nts
réussi récemment à avoir celle-ci : cr(Kn) .!e o,86 x Z(n) , qui s'en
pour n •importe que lle autre di position
approche.
des nœ uds. Voici un exempl e :
Références
• Th e graph crossing number and irs varianrs:
a survey. Marcus Schaefer, Elecrronic
Journal ofCombinarorics 1000, 201 3.
• Crossings and Planarizarion. Christoph
Buchheim er al., in Handbook of Graph
Drawing and Visualizarion. Chapman &
Hall/CRC, 201 3.
• Th e Erdos and Guy conjecrured equa/iry on
rhe crossing number of hypercubes .
Yuansheng Yang er al ., 2012 (
http://arxiv.org/abs/ 1201.4700 ).
• Th e Early Hisrory of rhe Brick Facrory
Problem. Lowell Be inke et Robin Wil son,
The Marhemarica/ ilue//igencer 32 (2) . 201 0.
• Crossing number problem. Paul Erdos et
Richard Guy, American Mathemarical
Monrhly 80. 1973.
• On a Problem of P. Turan Concerning
Graphs. Casimir Zarankiewicz. Fundamenra
Marhemaricae 41 , 1954 .
• Obsrmcrion er srabiliré pour classifier les
graphes. Jean-Paul Delahaye ,
pages 12 et 13. doss ier « Les types de
graphes ».
Aujourd'hui la question du nombre minimum de croise- • Le principe de rransferr en analyse infi nirési-
ments des graphes complets n'est résolue que pour n s 12. male. Jacques Bair et Valérie Henry, Tangenre
SUP70-71 ,201 3.
D
ans le des in ci-des us , on a la plu acce sible étant d'étudier les dif-
représenté trois maisons et férents cas, selon les manjères dont une
trois puits. Le but du jeu est de route peut relier une maison à un puits.
relier chaque maison à tous les puits, par En effet, deux routes sont manifeste-
des routes aussi sinueuses que l'on veut ment équivalentes si l'on peut passer de
mais ne devant pas se croiser. l' une à l'autre par petites défonnations
Il se trouve que ce jeu n'a pa de olu- successives san jamai passer par un
tion. La démonstration de cette impo - puit ou une maison. Une fois remarquée
sibilité peut se faire de plusieurs façon , cette équivalence, le nombre de routes véri-
tablement distinctes joignant une maison à
Il n 'est pas possible de joindre un puits est fini, et il est pos ible de tester
sans croisement trois maisons à trois puits. tous les cas à la main.
Graphes planaires
Puits 3
Dans cette configuration, la maison 2 ne peut pas être reliée au puits 3 en même temps
que la maison 3 aux puits t et 2.
Même si notre critère est mani- trois sommets voi sins sont reliés aux
festement incorrect, on remarque deux autres à la fois (auquel cas on a
tout de même que le graphe de la une contraction du grand graphe en (5))
page précéde nte est issu du et lorsque quatre sommets voisins sont
graphe (3, 3) via une modifica- reliés alternati vement aux deux som-
tion simple : le dédoublement de mets (auquel cas on a une contraction
la première maison . Cela donne du grand graphe en (3, 3)).
une nouvelle condition suffisante L'algorithme issu de ces observations
de non-planarité : si un graphe permet de conclure à la planarité ou à la
peut être ramené à (3, 3) ou à (5) non-planarité d' un graphe en au plus
par amalgame de sommets en 3n4 étape (où n est le nombre de som-
contractant certaines arêtes, alors mets du graphe), par une méthode
il n'est pas planaire. C' est par consistant à contracter certaine arêtes
exemple le cas de la fi gure précé- vérifiant des conditions fac iles à tester
dente si l'on amalgame les mai- et réduisant l'ensemble du graphe au
son s I et 1' en contractant l' arête graphe des quatre villes toute reliées
rouge. entre elles . Ce graphe est bien entendu
pl anaire et l'on part alors de ce lui-ci :
le bon critère on lui applique les dédoublements de
sommets réalisant l'opération inverse
Il se trouve que ce critère est non de la contraction et l'on vérifie qu ' à
seulement suffisant , mais auss i chaque étape , on n'a jamais l' un des
nécessaire ; par conséquent , un deux cas de dédoublement interdit. JI
graphe est planaire si, et seule- existe de algorithmes beaucoup plus
ment si, il ne peut pa être rame- rapides: l' un d 'eux met un temps
né au graphe (3 , 3) ou au graphe d' exécution proportionnel à n , ce qui
(5) par contraction d' arêtes le est difficilement imaginable, mais les
composant. Il ex iste aujourd ' hui choses se compliquent sérieusement ...
de nombreuses démonstrations de
ce résultat, et autant de méthodes Enfin , il ex iste des algorithmes per-
pratiques pour le vérifier. En mettant de déterminer si un graphe
effet, utiliser ce critère directe- donné peut être placé dans une surface
me nt e n testant toutes les comme la sphère ou le tore. Toutefo i ,
contractions d 'arêtes prendrait un le nombre d 'étapes nécessaires aux
temps incroyablement long pour algorithmes connus dépend de la nature
des graphes trè grand . Pour de la surface con idérée , et l' on ignore
trouver de méthodes plus effi - s' il peut exi ter un algorithme qui
caces, il faut s' intéresser d ' un peu répondrait à la question en un nombre
plus près à l'étape de contraction d'étapes à peu près indépendant de la
d' une arête . nature de la surface. Cela illustre une
Partons d ' un sommet d' un graphe fo is de plus l' idée qu 'en théorie des
que l'on dédouble. L'en emble graphe , les que tions dont on connaît
des sommets voi sins de celui-ci les réponses sont omme toute peu
peut être représenté par un cercle nombre uses, et sont souvent très
autour de lui . JI n'y a que deux proches dans leurs termes de que tions
cas où le dédoublement pose un encore ouvertes .. .
problè me de pl anarité : quand J.-C. N.
ans un graphe non orienté, dan l'autre selon les besoins. Dans ce
.
1/\ .
3 .
1/\ .
3 à deux sommets, deux graphes à trois
sommets, quatre graphes à quatre som-
·----i. . .
1
01
2
.. 012
.. 111
mets. À chac un de ce graphes, on peut
assoc ier une matrice. Dans chacune
de ces matrice , le terme a IJ.. vaut I s' il
ex iste une arête d 'origine i et d 'extré- seaux (elle casse les c iseaux), les c i-
mité j, et O dans le cas contraire. seaux gagnent contre la fe uille (ils la
coupent) et la fe uille gagne contre la
pierre (e lle la recouvre).
[~~] [O
1O I]
0 1
0 0 0
[°
1 0 0I]
0 10
01 0 12 Ill
10 0 1
["0 1 01 0 ·i ·i[oo,ol [oo" ]
01 0 1 1
0 0 0 0
1 000
0 1 00
1 010
0000
I
1 0 10 1 0 10 1 1 10 0 1 10
11 22 0 123 0222 111 3
est égale au nombre total d 'arêtes du Dans le jeu à quatre objets, pierre-
graphe. Dans un graphe non orienté, fe uille-ci eaux-puits, le puits gagne
une telle matrice serait symétrique par contre la pierre et contre les ciseaux
rapport à la diagonale. Dans la matrice (ceux-ci tombent dedans) et la feuill e
associée à un multigraphe (dans lequel gagne contre le puits (elle le recouvre).
plusieurs arêtes peuve nt aller d ' un
sommet i ver un sommet )), les « l »
pourront être remplacés par le nombre
n d 'arêtes correspondantes.
,,/:, .. / 7
Pierre, feuille, ciseaux !
L' intérêt des graphes orienté est
qu ' il ex iste de nombreuses situations
où ils sont utiles, notamment dans les
tX !
.. e
sc iences ociales ou écono miques.
Voici un exemple tiré du do maine des Cette situation correspond
jeux : le chi-fou-mi. Dan un tel jeu à au graphe codé 1122.
trois objet , de type pierre- fe uille-ci-
seaux, la pierre gagne contre les ci-
0 N \.,.)
Dans un certain nombre de situations (") (") (") (")
:r :r :r :r
concrètes représentées par un graphe,
les différentes arêtes n' ont pas la même êi êi ~ ~
~ ~
L'arbre de
probabilité du 421.
Jcr lancer
2• lancer 3• lancer
3
6
Obstruction et stabilité
pour classifier les graphes
Certaines propriétés d'un graphe sont conservées par ses
sous-graphes particuliers appelés mineurs. Cette stabilité est
à la base de la définition d'un certain nombre de types de
graphes qui sont énumérés dans cet article.
n peut définir la notio n de ous- respecte mie ux et de maniè re plus abs-
Tout arbre par exemple e t planaire exté- • Graphes sans cycle noué
rieur. Les graphes planaires extérieurs peu-
ve nt être co lorés avec troi s coule urs
(sans que deux nœ uds vo isins aient la
même couleur).
L'ensemble des graphes planaires exté-
rie urs est stabl e par minorati o n . Un
Un graphe planaire graphe G est pl ana ire ex térie ur si, et
extérieur. seule ment i, ni K2.3 ni K 4 ne sont des
mineurs de G .
• Graphes sans imbrication de cycles
Un graphe est sans imbrication de cycles Les graphes sans cycle noué sont ceux
si o n pe ut arra nger ses nœ ud s e t ses que l' on peut placer dans l' espace sans
arêtes dan l'espace de te lle faço n que que j ama is le arêtes d ' un cyc le fas-
j amais deux cycles du graphe ne soie nt sent un nœud autre que la simple boucle .
imbriqués l' un dans l'autre. Il est immé- Ils constitue nt un ensemble de graphes
di at que la fa mill e des g raphes sans stable par mino ration . On ne connaît
imbri cation de cycl es es t sta bl e pa r pas de caractéri ation de ces graphes en
minoratio n, car en réalisant les opéra- te rmes d ' obstructi o ns . Le graphe c i-
tions (a) , (b) et (c) à partir d ' un graphe dessus po sède un cycle noué (en orange).
placé dans l'espace sans imbrication on Ces que lques exemples couvrent une
ne crée pas d ' imbrication . grande partie de graphes communé-
Les graphes pl ana ires sont sans imbri- ment rencontrés dans les applicatio n
cation de cyc le . Si on prend un graphe de plu s en plu s fréque ntes qui en utili -
pl anaire dess iné sur un pl an et que l' on sent la théo ri e. Leur carac té ri sati on ,
relie chaque nœ ud du graphe à un nœ ud selon le ca par obstructions ou par sta-
en dehors du pl an, on obtient encore un bilité, ouvre de nouvea ux horizons, en
graphe sans imbrication de cyc les. particulier car connaître leur ensemble
On montre qu ' un graphe est sans imbri- d ' ob tru cti o ns pe rme t d ' obte nir de s
cation de cyc les s i , et se ul e me nt si , a lgorithmes rapides qui teste nt si un
aucun des ept graphes sui vant (consti- graphe est dans la classe ou pas.
tuant l'ensemble de Petersen) n'est un
mineur de G . J.-P. D.
Un graphe étiqueté est un graphe orienté, dont les L'état probabiliste du systè me est une lo i de pro-
arêtes sont affectées d 'étiquettes. Si toutes les éti- babilité sur l'ensemble des états possibles : cette
qu ettes sont des nombres pos iti fs, o n parle de loi sera ic i représentée par une matrice ligne. Un
graphe pondéré. Da n ce cas, le poids d ' une g raphe probabili ste pe ut auss i être utili sé pour
chaîne est la somme des po ids des arêtes orientées décrire l'évolution d ' un ystème formé de plu-
qui la composent. sieurs composants pouvant se trou ver dans diffé-
Une plus courte chaîne entre deux sommets, est rent états (l'en emble de états est le même pour
parmi les chaînes qui les re li ent , une chaîne de chaque composant). L'état du systè me à un in s-
po ids minimum . tant do nné est la matrice ligne donnant le nombre
de compo ants du système dans chaque état.
0,9 0, 1
c 2 F
Le graphe orienté ci-dessus est pondéré. (
0,3
0,2
0,2 o~s)
0,8
0
La chaîne (C-B-A-G-F), a pour poids
=
1 + 1 + 2 + 4 8. Le graphe d ' ordre 3 précédent est un graphe
probabiliste. Sa matrice de transition
Une clique es t un o us-e nsembl e de so mme ts est donnée ci-dessus. La somme des éléments
connectés les uns aux autres ; une clique forme un d'une ligne vaut l.
ensemble complet. Pour un graphe, le nombre de
sommets de sa plus grande clique est le nombre • La somme des degrés d ' un graphe no n orienté
de clique . Ce no mbre est to ujo urs in fé rie ur au est égal à deux foi s le nombre d 'arêtes du graphe.
nombre chromatique. Un graphe est parfait si pour • So it A la matrice assoc iée à un graphe. Le terme
tout sous-graphe induit H le nombre chromatique (i ,j ) de la matrice A' donne le nombre de chaînes
est égal au nombre de c lique de H . La c lique K 11 de longueur r re liant i àj.
e t un graphe parfa it. • Le nombre chromatique d ' un graphe est inférieur
Un graphe probabi- ou égal à D - 1, D étant le plus grand degré des
liste es t un g ra ph e sommets.
0,9
o rie nté, po ndé ré, te l • Théorème d 'Euler : un graphe connexe admet une
qu e la so mm e d es chaîne eulérienne si, et seulement si, le nombre
0,2 po ids de arêtes sor- de sommets de degré impair vaut O ou 2. Un graphe
tant de chaque som- connexe admet un cyc le eulérien si, et seule ment
met donné vaut l. Le si, tou ses sommets sont de degré pair.
graphes probabili tes • Si M est la matrice de transition d'un graphe pro-
s ont utili sés pour babili te, i P0 est la matrice ligne décri vant l'état
0,2 0,8
modéliser l'évolution initial, et Pk l'état probabiliste à l' étape k, on a
d 'un système pouvant changer aléatoirement d 'état : pk =Po Mk.
les sommets du graphe sont les états possibles du • Pour tout graphe probabili ste d 'ordre 2, do nt la
système et le po ids d ' une arête orientée issue du matrice de tran sition ne comporte pas de 0 , l'état
sommet i et d 'extrémité} e t la probabilité de tran- Pk à l'étape k converge ver un état P indépendant
sition de l' état i à l'état j. de l'état initial P0 . De plus, P vérifie P = PM .
entrent en scène
Non, la règle de multiplication des matrices ne sert pas qu'à
poser des exercices calculatoires aux examens. En théorie des
graphes, elle reçoit des interprétations précieuses autant
qu'inattendues.
Références
Les matrices.
Bibliothèque Tangente 44,
POLE, 2012.
Graphes et hypergraphes.
Claude Berge,
Dunod, 1970 .
le graphe de l'amitié
et le moulin à uent
Si, lors d'une réunion, vous partagez avec chaque personne de
rencontre un et un seul ami commun, alors, il existe un indivi-
du ami avec tout le monde. On l'appelle le politicien. Ce résul-
tat surprenant est dû à trois mathématiciens hongrois.
n\ ité à l' occas ion d ' une soirée les autres sommets. On va établir de
Des arbres
au secours des probabilités
Des urnes, des boules de couleurs différentes, des tirages : le
décor est planté pour une bonne vieille question d e
probabilités« élémentaires ». Pour éviter de s 'embrouiller, il
est conseillé d'avoir recours à un auxiliaire efficace: l'arbre.
a question qui va nous occuper vertes, de ux boul es ro uges et cinq
L'énoncé est infernal, certes, mais vous Les deux branches qui parte nt de la raci-
ne pouvez pas dire que vous n'étiez pas ne reflètent les deux issues possibles
prévenus. D'ailleurs, la question elle- lors du premier lancer (« 6 » ou « non-
même est assez simple , et il n'est pas 6 ») . Au bout de chacune d' elles partent
difficile de reproduire l'expérience. deux nouvelles branches, qui concer-
La question a beau se comprendre assez nent l' issue du second lancer. Chaque
fac ilement , il semble que la réponse branche est surmontée d ' une probabili-
soit proprement introuvable. Il est vrai té, qui est celle de l' issue vers laquelle
que si l'on tente de la trouver unique- elle mène (à chaque foi s, une chance sur
ment à l' aide de calculs (à partir des six d ' avoir 6 et cinq chances sur six
propriétés cl ass iques des probabilités) , d' avoir non-6).
on y passe la nuit : on tombe sur d ' in-
terminables fo rmules desquelles on a Bifurquer pour régner
toutes les chances d'extraire un résultat
fa ux, pour cause d'erreurs de calcul , Les feuilles de l'arbre représentent donc
bien compréhensibles , d 'ailleurs. tou s les résultats poss ibles, les frac-
Or il ex iste un moyen de s'en sortir, tions à côté d 'elles la probabilité de
d ' une simplicité et d ' une élégance chaque fe uille. La feuille correspondant
remarquables : ce moyen consiste à uti- au double-6 est de probabilité 1 / 36 ,
liser un arbre . Pour comprendre en quoi celle correspondant au « double-non-6 »
cette structure peut nous être utile , pre- est de probabilité 25 / 36 : chacune de
nons une situation un peu plu s simple ces valeurs s' obtient simplement en
que celle de l'énoncé précédent. multipli ant entre elles les probabilités
Lançons un dé deux foi s de suite et des branches menant de la racine à la
intéressons-nous à la probabilité d'ob- fe ui lie considérée . La justification de ce
tenir soit deux fo is 6 , so it aucune fo is fait est donnée par la .formule des pro-
6. Le cheminement de l' expérience peut babilités conditionnelles :
se représenter à l'aide d' un arbre de la P(A n B)
faço n sui vante : P(B / A) = P(A)
+ ~ + ---1L + ~ = .111...
1000 1000 1000 1000
so it p = ~~.
Et vo il à ! C'est un peu long, mais ce
n'est pas di ffic ile (d' autant que l' on
aurait pu se dispenser de faire toutes les
branches) et cela peut très bien se pro-
grammer sur ordinateur. L' utili sation
d' un arbre rend donc accessible un cal-
cul qui serait beaucoup plus fas tidieux
si non. Cela dit , vous pouvez toujours
essayer d'écrire le calcul en question :
ce n' e t pas imposs ible, mais bon cou-
rage quand même .. .
B.R.
2.4.6=48
S.4.3=60 3.2.1=6
d'un carré
Selon la surface sur laquelle est dessiné un graphe, ses
propriétés diffèrent, comme on l'a vu dans le précédent
article. Pour compléter l'étude de ces divergences, voici un
sujet d'étonnement: une recension des surfaces qui peuvent
être engendrées à partir d'un simple carré.
armi les surfaces que considère
On ne coud rien :
1. Si on ne colle rien : on a un plan.
on obtient un plan.
2. Si on co lle le côté gauche et le côté
droit dans toute leur hauteur en res-
pectant le haut et le bas, on obtient un
anneau simple , ou cylindre creux. Les
graphes dess inables sur un cylindre
On coud 2 côtés opposés On coud 2 côtés oppo és creux (sous-entendu « sans croise-
dans le même sens : dans le sens contraire :
ment d'arêtes») sont les mêmes que
on obtient un cylind re creux. on obtient un ruban de Mobius.
ceux dessinables sur le plan , car (i) en
déformant un cylindre creux conti-
nûment on le met sur le plan , et (ii)
un graphe dess iné sur un pl an l'est
dan s un rectangle dont on peut bien
sûr faire un cy lindre creux.
Le ruban de Mobius.
On coud un couple de côtés dans le même sens et le second en sens contraire : 3. Si on co ll e le côté gauche et le côté
on obtient une bouteille de Klein. droit en inver ant le haut et le bas,
Le tore.
6. Si on co ll e à la foi s le côté gauche En haut :
4. Si on colle à la fo is le côté gauche et et le côté droit en respec tant le haut construction d'un
le côté dro it en respectant le haut et et le bas e t le côté du bas avec le cylindre.
le bas et le côté du bas avec le côté côté du haut e n in versant la gauche Juste en dessous:
du haut en respectant la droite et la et la droite , on obti ent la bouteille construction d'une
gauche, cela donne le tore (la chambre de Klein , qui comme le pl a n pro - bouteille de Klein
à air). jecti f ne pe ut pas vraime nt se placer à partir d ' un
dans l'espace usue l à troi s dimen - cylindre.
s ions .
Le plan Ch ac une d e ces s urfaces dé finit un
projectif. ensemble de graphes stables par mino-
rati o n (voir l'articl e e n pages précé-
dentes) quand on considère les graphes
qu ' on peut y dessiner sans croisement
5. Si on colle à la foi s le côté gauche et d 'arêtes. Ces ensembles ne sont pas tous
le côté droit en in versant le haut et le identiques . En effet, le graphe K 33 ne peut
bas (comme pour la bande de Mobius), pas être dess iné sur le cylindre creux
et le côté du bas avec le côté du haut (ni sur le pl an), mais il peut l'être sur la
en in versant la gauche et la droite, bande de Mobius et la bouteille de Klein .
alors on obtient le plan proj ectif. Il Le graphe K 5 , qui ne peut pas être des-
est assez di ffic ile à visualiser car c'est siné sur le pl an (et donc sur le cy lindre
une surface qui ne peut pas se pl acer creux), peut l' être sur le tore.
dans l'espace usuel de dimen ion trois
(sauf en introduisant des intersections
de la surface avec e lle- même).
La bouteille de Klein.
• ••
Q uatre faço ns de dessiner K, sur le tore
• • •
• •
D 'après le théorè me des mine urs (vo ir • • •
l'article qui y est consacré) , c hac un des • • • •
e nsembles de g raphes défini s pa r les
'..
surfaces é lé me nta ires que nous e nvisa-
geo ns e t carac té ri sé par un ensemble •
d'obstructions. Pour le carré ou le cylindre • • •
cre ux, l'e nse mbl e d ' obstru c tion s es t
{K5 , K 3 .3}· Po ur le ruban de Mo bius e t
le plan projectif, Dan Steven Arc hdea-
con a ré ussi (non sans mal ) à établir que
.. .. . '•
l'ensemble d ' obstructions est constitué
de tre nte-c inq graphes. J.-P. D.
Pour le tore et po ur la boute ille de Kle in ,
personne po ur l' instant n 'a réuss i à tro u-
ver l'ensemble d ' ob tructions. On sa it
juste que pour le to re, il contient plu-
Les trente-cinq s ie urs milli e rs de gra phes, ce qui est
graphes vraime nt très é tonnant : pourquo i do nc
d 'obstructions du le tore conduit-il à quelque chose d ' aussi
ruban de Mobius. complexe?
:\t:• en 1948 ù Budapest. l.."1s1lù Lm.isz est connu pour ses tr,l\,IU'> l'n informatique tht'.•orique.
l ' i\rnmbin atoin· l'i en tht"•ori e des graphes (il a tlonn t:• son 110111 ù un nombre il). Il tlirige
aduclknwnt lïnstitut dt• 111atht•111atiqut•s de J"unin•rsit t:· dt• Budapest. Pour un graphl' C ù Il
somnwts. consitkrons toutt•s ks 111atrit·t•s ,\ s_\·mt•triqut•s et d "ordrc Il tl'lll's que u = 1 si i = j
ou si i - j 1Ù'st pas unt• arde de c;. La matrice t·ompkmentain· dt• la matrice d"adjan·m·e .
obtenue t•n !I intl'rchangcant les o
et les 1. est d e CL' t_\l1L' . Soit ,\ , (.\)
la , , 1lcur propn· ma,;imalt• d"unc Le théorème de l'amitié amélioré
telle matrit'l'. Alors k nomhrc de
Lot •û9 t•st ·"} ( G 1 ~ rn i 11 \ ( :\ ) •
La« condition de l'amitié» rencontrée dans l'article le
Il l'St !l'i que k tht"·on:O nll' du sand- Graphe de l'amitié et le Moulin à vent (voir en page 34)
\,ich lt> ((; ) :s il ((;) :s \ (G) t·~t ,éri- peut se réécrire sous la forme suivante : pour chaque
fü'· pour tout graplll' G. où 1n ( c;) est paire de sommets, il existe exactement un chemin de
la taille dt• la plus grandt• clique dl' longueur 2 entre eux. Cette reformulation permet une
G l'i le nomhrl' chromatiqut• \ (G)
généralisation en cherchant les graphes, notés P}k),
il' plu~ pl'lit nomhrl' dt• couleurs
nfrl'ssairl's pour colorit'l" de fa,on dans lesquels chaque paire de sommets est connectée
difft"•rt•nte dt·~ somml'ls adjacl'nts. par exactement j chemins de longueur k. Le théorème
de l'amitié énonce que les P1(2) sont exactement les
R f: F f:RE'.'.'\ l ' ES moulins à vent. En 1974, Anton Kotzig conjectura qu'il
• .\/<1th< lll<1IÎ</ll1'.,
0
discri·tc., n'existe pas de graphes tels que P,(k) avec k <!: 3, et le
l'i 1'Clllliii11<1lelirt·. démontra pour 3 s k s 8. Alexandr Kostochka prouva
Bihli1ltlù·qu1· Tangt'llk :\lJ. :..>0111. en 1988 que la conjecture était vraie pour k s 20. De-
• Do-.-.il'r '" l\i 1 Lrdii, ··. puis, les autres cas ont été vérifiés, et la conjecture est
F<1ll1/<'lll1' l ;):..'. :..'O t:{. devenue un théorème !
Un résultat profond
le théorème des mineurs
Le théorème des mineurs - ou théorème de Robertson-
Seymour - a été énoncé en 1937 par Klaus Wagner - ce n'était
alors qu'une conjecture - et démontré soixante-sept ans plus
tard, en 2004, par Neil Robertson et Paul Seymour.
e « théorème des mineurs » est affirme que les graphes planaires - c'est-
·X
Dans toute suite infinie de graphes, L'un
·X
d' une arête
est le mineur d'un autre.
·X X
nœud i olé
est possible de trouver deux graphes G;
et Gk avec i -:f. k e t tels que G; est un
mineur de Gk.
Il ne s'ag it pas d ' une év idence. Si par prend un graphe dess inable sans cro i-
exemple, on e pose la même question sement d 'arête ur un plan et qu'on lu i
pour les sous-en embles finis de nombres applique une de opérations (a), (b) ou
entier , on ne trouvera pa de théorème (c), il est c lair que le graphe obtenu e t
équi valent : il est en effet poss ibl e de encore dess inable sur un pl an sans croi-
définir une suite infinie de sous-ensembles sement d 'arêtes : ni la suppression d'arêtes
de no mbres E 1, E2 , ... , E,,, ... te ls qu 'au- o u de nœ uds iso lés, ni la cont ract ion
cun n 'est une partie d ' un autre (au sen d 'arêtes n'obligent des arête qui ne se
habitue l de l' inclusio n d 'en embles). 11 cro isa ient pa à e croiser, et do nc tout
suffit par exemple de considérer : graphe obtenu à parti r d ' un graphe pla-
E 1 = {O, 1}; E 2 = { 1, 2}, E3 = {2, 3}, nai re en effectuant une ou plusieurs fo is
etc. les opérati ons (a), (b) ou (c) est encore
De même, on trouve fac ilement une infi- un graphe pl anai re.
nité de fo ncti ons de R (l'ensembl e des
no mbres réels) dans R , sans qu 'aucune De la même faço n, si on cons idère l'en-
ne so it plu s petite qu ' une autre (J est se mbl e des graphes dess inab les sans
plus petite que g, sif(x) ~ g (x) pour tout croisement d 'arêtes sur un tore (ou sur
x). On prend par exemple le fo nctions une bande de Moebius ou sur n' importe
J0 ,f1,f2 ,f3 ... définies par : que lle surface auss i co mpliquée so it-
J,,(x) = (x - n)2. elle), il est c lair - par le même rai on-
li ex iste une infinité d 'ensembles d 'en- nement - qu' il s'agit encore d' un ensemble
tiers deux à deux non comparables, il de graphes tables par minoration.
ex iste une infinité de fo nctions deux à Un e nse mble de g raphe E peut être
deux non comparables, mais il n'ex iste défi ni par la donnée de graphes inter-
pas d ' infi nité de graphes deux à deux dits : on ne veut pas que tel ou tel graphe
non comparables ! soit un mineur des graphes de E. L'en-
semble des graphes pl anaires , d'ap rès
minoration et obstruction le théorème de Ku ratovsk i, est définis-
sabl e de cette façon : les graphes pla-
Sous sa pre mière fo rme, le théorème de na ires sont les graphes n'ayant aucun
Robertson et Seymour est un peu abs- des graphes K5 ou K33 comme mi neurs.
tra it. La econde fo rme du théorème - La seconde forme du théorème de Robert-
qui permettra de comprendre le lien avec son et Seymour est j ustemen t l'affir-
le rés ultat de Kuratovs ki - est plu s matio n que ce qui se produit pour les
concrète et c'est e lle qui a des consé- graphes pl anaires -stables par mino-
quences dan s le domaine de l'algorith- ration et défi nissables par interd iction-
m ique des graphes. est général.
Pour l'énoncer il fa ut comp re ndre les
notions d 'ensemble « stabl e par mino- Vo ici donc le théorème de Robertson
rati o n » e t d ' « e nse mbl e d 'obstru c- et Seymour (seconde forme)
tions ».
Un ensemble E de graphes est dit stable Tou t ensemble Ede graphes stable par
par minoration (ou clos par mineur) si minoration est définissable comme l'en-
tout mineur d ' un graphe de E est lui - semble des graphes n'ayant pour mineur
mê me dans E. aucun des graphes d'une liste finie ,
L'ensemble des graphes pl ana ires est caractéristique de E, et appelée « ensemble
stabl e par mino ratio n . En effet , si on d'obstructions de E » .
Nous sommes dans un domaine où finalement il faut distinguer trois types de résultats
algorithmiques :
• ceux indiquant qu'un algorithme existe pour une tache donnée ;
• ceux formulant précisément l'algorithme pour la tache;
• ceux conduisant à l'écriture d'un programme réalisant la tache.
Pour le dire autrement l'effectivité peut être existentielle, théorique ou réelle, et seule
bien sûr la troisième est susceptible d'utilisations concrètes !
La situation est assez désagréable et le contraste entre le plan (obstruction avec deux
graphes seulement, algorithme linéaire utilisables en pratique) et le tore (ensemble obs-
tructions inconnu aujourd'hui, et programmes exponentiels) est ahurissante. La surface
d'un tore est l'une des plus simple qu'on puisse imaginer!
On a le sentiment que le monde mathématique nous fait des farces. Moyennant un long
et difficile raisonnement, il accepte de nous dire que pour le tore comme pour le plan, il
existe un algorithme en n3, facile à programmer, indiquant quels sont les graphes qu'on
peut y dessiner sans croisement d'arêtes, mais il ne nous le donne pas. De plus, tout porte
à croire que le trouver est à nouveau un long travail. Parfois, on croit trouver un algorithme
efficace, mais il se révèle impossible à mettre en œuvre du fait de sa complexité. L'exis-
tence d'algorithmes polynomiaux dont on pensait qu'elle déterminait la frontière entre le
faisable et l'infaisable n'est finalement pas le critère ultime pour qu'un résultat mathématique
soit pratiquement utilisable : à y regarder de près, cette frontière semble se diviser en une
série de zones délicates à préciser.
Des diagrammes
pour la physique
Les physiciens ont souvent besoin d'une représentation
graphique des phénomènes qu'ils essaient de décrire. Des
circuits électroniques à !'infiniment petit, du système solaire
au boson de Higgs, voici quelques exemples d'utilisation de
graphes et diagrammes en physique.
ertain~ problèmes de phys ique lunette astro no mique. Cet acces oire est
10-
Î o--.-----== ·I".
i -10 · G • Odll
e+
Mettre un diagramme
de Fevnman en équation
g
L'image ci-contre
montre un exemple de
diagramme de Feyn-
man avec les termes e
g à prendre en compte 4
pour « calculer ~ Exemple de diagramme de Feynman.
(mettre en équation)
ce diagramme. Un diag ramme de Feynman se lit de
e Le terme ..fa fournit gauche à droite . L'axe horizontal cor-
q la probabilité que, lors- respond au temps et l'axe vertical à l'es-
qu'un électron et un positron se rencontrent, ils don- pace. Tout à ga uche , c'es t-à-dire a u
nent naissance à un photon (noté y). début , ava nt la collision, on observe
Le terme 1 / q 2 est appelé propagateur. Il correspond à deux particules, un électron (e-) et un anti-
la propagation du photon : des particules différentes vont électron (e+). Lorsque l' on e déplace
se propager de manière différente et affecter la pro- ver la droite , on voit que ce deux par-
babilité du processus total. ticules e rapprochent , jusqu ' au point
Les termes Qq ..fa et Jii; donnent les probabilités de où elles entrent en colli ion. À cet endroit,
production des particules correspondantes. elles disparai sent en donnant naissance
Tous ces termes regroupés permettent de calculer la à une nouvelle particule , appelée z0 .
probabilité que deux électrons produisent deux quarks Cette particule possède des propriétés par-
et un gluon dans l'état fmal (les physiciens appellent cela ticulières, et par convention a trajec-
la section efficace de ce processus). Cet état final étant toire est représentée par une sinusoïdale.
identique à celui décrit dans le texte, où c'est un z0 qui Le z0 se propage pendant quelques ins-
se propageait au lieu d'un photon, il faut ajouter ces sec- tants (en fait moins d ' un milliardième de
tions efficaces pour trouver la probabilité totale. seconde !) avant de se désintégrer en
deux nouvelles particules. Ces deux par-
'
d
fornien de technologie (CalTech). Là, il développe la théo-
rique de l'électrodynamique quantique, qui met en équation '
la propagation des particules fondamentales à haute éner- 10''
gie. Cette théorie lui vaudra le prix Nobel en 1965, conjoin- 100 200 300 400 !IIJO 800
"1, (GeVJ
tement avec Julian Seymour Schwinger et Sin-Itiro Tomonaga
Dans cette théorie, il décrit la propagation des particules Sur l'axe vertical, on visualise la limite
grâce à une équation appelée lagrangien. Afin d'établir ce sur la probabilité de produire un boson
lagrangien, il met au point la méthode graphique décrite dans de Higgs par rapport à la prédiction
l'encadré de la page précédente. théorique dans le cas standard. Sur
De ses années à CalTech, il reste également un ensemble l'axe horizontal est repérée la masse
d'ouvrages destinés aux étudiants de premier cycle et appe- dudit boson de Higgs. La courbe noire
lés Cours de physique de Feynman . Ces cours de physique donne la limite obtenue par les mesures
sont très appréciés pour la clarté des explications données expérimentales et les bandes jaunes et
par Feynman. Sur la fin de sa vie, il fait partie de la com- vertes les incertitudes liées à la mesure.
mission d'enquête qui cherche les causes de l'explosion de Il y a quelques années encore, la courbe
la navette Challenger en 1986 ; il y jouera un rôle déterminant. noire était nettement au dessus de J sur
une grande partie du graphe. Elle est
progres ivement descendue en dessous
Références Jusqu 'à très récemment, l'un des objec- de 1, partout sauf dans une petite bande
• Mathématiques et tifs de la physique des particules était de qui correspond à l'énergie à laquelle le
chimie. Bibl iothèq ue trouver une particule appelée boson de boson de Higgs a été effectivement
Tangente 43 . 20 12. Higgs . La recherche de cette particule a découvert.
• Des nouvelles duré de nombreuses années : il s'est écoulé
sol11tio11s au problème prés de cinquante an entre sa prédiction Ces quelques exemples ne ont pas limi-
des trois corps. et sa découverte ! L' une de raisons pour tatifs. Les graphes sont utilisés dans de
Nicolas Delerue, lesquelles cette recherche a duré auss i nombreux domaines de la physique, par-
Ta11ge111e SVP 69 , longtemps est que la probabilité de pro- foi s implement pour sché mati ser ce
20 13. duire un boson de Higg , même sur les que le physicien observe. D'autres foi s,
• Fey11ma11 . Jim accélérateurs les plu s énergétiques au comme dans le cas des di agrammes de
Ottav iani et Leland monde , était trè faible. Cette probabilité Feynman , il s apportent une aide réelle
Myrick, Vuiben. elle-même n'était pas connue avec cer- à la mi se en équation des observations.
20 12. titude tant quel ' on ne connaissait pas les L' importance des graphes et diagrammes
• Le lagra11gie11 pour propriétés détaillées du boson de Higgs. est telle que l'on trouve très peu de publi-
décrire la dy11amique Au fur et à mesure de leur quête , les phy- cations e n phy ique qui ne comportent
des systèmes. siciens ont été capables de dire que si le pas au moins un graphe ou un diagramme.
Tangente 15 1,20 13 . boson de Higgs existait alors la probabilité
de le produire était de plus en plus petite. N.D.
l
L =D - A. Dans notre exemple,
0 1 0 0
1 0 1 1 1 -1 0 0
A=o101 · _ -1 3 -1 -1
0 1 1 0 L- 0 -1 2 -1.
D'autre part, chaque sommet a un degré égal au 0 -1 -1 2
nombre de sommets auxquels il est relié. Cela
permet de définir une matrice (diagonale) des La matrice Lest diagonalisable (car symétrique
degrés. Ici : réelle) et O est l'une de ses valeurs propres
(puisque la somme des éléments de ses lignes
1 0 0 0 est nulle). Un vecteur propre associé à la valeur
0 3 0 0 propre O e t le vecteur composé uniquement de
0
=0020· 1.
[
0 0 0 2
Le théorème des
quatre couleurs
Tous les cartographes savent que l'on peut colorier n'importe
quelle carte avec quatre couleurs, deux pays de frontière
commune ayant des couleurs différentes. Mais peut-on le
prouver?
Colorier
Un défi innocent et redoutable
Comme l'illustre l'histoire du théorème des quatre couleurs,
d'innocents problèmes de coloriage peuvent cacher de redou-
tables difficultés. Pour apprendre à les résoudre, on peut essayer
de colorer les graphes planaires avec six couleurs.
L
es gra phes pe rme tte nt de pré- tus De Morgan la conjecture des quatre
sente r des question s de mathé- coule urs: il semble to ujo urs possible de
matiques d 'appare nce a nodine colori e r propre m e nt toutes les cartes
qui résistent aux me illeurs spéc ialistes et planes avec seulement quatre couleurs (voir
défient le plu pui s ants ordinate urs. le précéde nt article). Bie n que l'é no ncé
Les questions de coloriage de cartes e n de la que ti o n so it a isé à fo rmul e r, y
sont un excelle nt exemple. Ains i, une répondre se révèle bien plus difficile : deux
carte plane est le découpage d ' un espace démonstrations erro nées seront publiées
plan en plusieurs zanes. Deux zones sont dans les années 1880 , suffi amment tech-
voi sines si elles partage nt une frontiè re niques et convai ncantes pour être tenues
(un simple point n 'est pas une frontiè re) . pour justes pe ndant plus de di x an .
Une carte plane est proprement coloriée En 1976 , le mathé matic ie n a mérica in
s i chaque zone est coloriée et que deux Ke nneth Appel et l' Allemand Wolfgang
zones voi sines sont to ujours de di ffé- Hake n , travaill ant e nsemble à l' uni ver-
re ntes couleurs. sité de l ' Illinois, annoncent avoir résolu
En 1852, le jeune Francis Guthrie, ancien la conjecture, mainte nant vie ille de cent
étudiant à !'University College London , vingt-quatre ans. Le (désormais) théorème
propose à son ancien professe ur Augus- des quatre coule urs e ntre dans ! ' hi stoi re
des sciences comme l' un des tout premiers
théorè mes mathé matiques aya nt néces-
sité l' intervention de ! 'ordinateur dans sa
dé monstration . Ce tte preuve est auss i
considérée comme !' une des plus contro-
ver ées des mathé matiques modernes :
les nombreux précédents de preuves erro-
nées, le recours à un calcul informatique
La présence d'un sommet réductible gra phe re présente un é mette ur- récep-
te ur, chaque coule ur une fréque nce, et
Un graphe connexe est un graphe dans lequel, pour les sommets sont re liés par une arête si
chaque paire de sommets, il existe un chemin les les é me tte urs qu ' il s re présente nt sont
reliant. Montrons que chaque graphe planaire connexe suffisamme nt « proches» pour que leurs
possède un sommet de degrés (afortiori, ce sera fréque nces respectives se do ivent d 'être
également le cas pour les graphes non connexes). é lo ignées afi n d 'éviter les interfé rences .
On commence par établir la Formule d'Euler, selon Le problè me de gestio n d 'empl o i d u
laquelle pour tout graphe planaire connexe avec n te mps, que les institutio ns cola ires et
sommets, m arêtes etf faces, on a la relation uni ver itaire connai ent bien , peut être
n - m +J = 2. Cette formule se démontre facilement vu comme un problème de coloration de
par récurrence sur le nombre d'arêtes: elle est vraie graphe : générer un emploi du temps pour
pour un graphe sans arêtes (m = o), et augmenter m les cour d ' un collège rev ie nt a in s i à
de 1, c'est ajouter une arête. Pour ajouter une arête, représenter chaque cours de chaque classe
il faut soit ajouter un nouveau sommet, soit relier à l'aide d ' un sommet, de les re lier s' il s
deux sommets déjà existants (ce qui coupe une face ne peuvent être effectués en même temps
en deux). (parce qu 'assurés par le même enseignant
Ensuite, on observe que le nombre d'arêtes m est égal o u destinés à la mê me classe), et à attri-
à la moitié de la somme des degrés des sommets du bue r propre ment des horaires (c'est-à-
graphe ; dans un graphe où chaque sommet est de dire des coule urs) à chaque sommet.
degré 6 ou plus, on a m ~ 3n. On le comprend , la conjecture des quatre
Le nombre d'arêtes m est aussi égal à la moitié de la coule urs n 'a pas été e ule me nt un défi
somme des tailles des faces du graphe Oa taille d'une tenace pour la communauté scientifiq ue,
face est son nombre d'arêtes). Comme chaque face e lle fut éga le me nt le précurseur d ' un
est de taille au plus 3, tout graphe planaire vérifie doma ine de la théorie des graphes lar-
donc m ~ 3f/ 2 . geme nt é tudié de nos jours .
S'il existait un graphe planaire où chaque sommet S ' il semble di ffic ile de colo re r propre-
serait de degré 6 ou plus, on aurait donc me nt un g ra phe pl a na ire do nné avec
m = 1/2 m + 1/2 m ~ 6n/ 4 + 3!/ 4. quatre coule urs, a n doute est-il plus
En remettant ces valeurs dans la formule d'Euler, et simple de le faire avec ix. On va démon-
en se souvenant que n ~f, on aboutit à une contradiction. tre r que to ut g raphe pl ana ire est pro-
pre ment colorable avec ix couleurs. La
pre uve, tructurée imila ire me nt à celle
champ de la coloration de carte géo- du théorè me des quatre couleurs, utili -
graphiques. On peut e demander quelles sera une version embryonnaire des outil
sont les me illeure méthodes pour colo- de la pre uve de 1976 . Il suffi t de di spo-
rer proprement d'autres classes de graphes ser d ' un ré ultat classique de la théorie
que les graphes plana ire , avec de nom- des graphes, selon lequel dans tout graphe
bre uses application , pui qu ' il s'ag it , pl ana ire o n pe ut trouver a u mo in un
e n réalité, d ' une que tion de ré partition sommet dont le degré (le nombre de voi-
de ressources avec c ontra inte . P a r sins) est de c inq o u mo ins. On va appe-
exemple, dans les té lécommunications, ler un te l sommet un sommet réductible.
les problè mes de colo ration de graphes La dé monstratio n de ce résultat est e lle-
ont utili sés pour mo dé li ser les pro- mê me to ut à fai t access ible (voir l'en-
blè mes d 'attribution de fréquences radio cadré c i-contre) .
(voir en encadré) dans un système d 'émet- Considéro ns donc un graphe G , planaire,
te urs-récepte urs : c haque somme t du que l' on souhaite colore r pro pre me nt
TYPES DE GRAPHES
avec six couleurs . So it v un sommet l' une de ces configurati ons réductibles,
réductibl e de G : s' il est poss ible de en utilisant les propriétés de la classe
co lorer pro prement G - v (le graphe considérée (ici, la formule d'Euler).
obtenu en supprimant v et toutes ses La complex ité de ce type de preuves
arêtes), alors il sera poss ible de colorer dépend du nombre et de la taill e des
G. En effet, il ne restera plus qu 'à colo- configurations réductibles (il faut démon-
rer v, et comme c 'est un sommet qui trer que chacune d'entre e lles est bien
possède au plus cinq voisins, avec nos réductibl e, et surtout montrer la pré-
six couleurs, il y aura toujours au moins sence obligatoire d'au moins l'une d'entre
une couleur di sponible pour le colorer ! elles, ce qui demande des calculs de plus
en plus méticuleux). On peut raisonna-
blement considérer qu ' une telle démons-
tration devient ardue aux alentours d' une
dizaine de config uration di ffé rentes.
La pre mi ère version de la preuve du
théorème des quatre couleurs, celle de
l'article ori ginel de 1976 , en contenait
mille neuf cent trente-s ix . . .
c.c.
le théorème des
graphes partails
L'un des plus spectaculaires résultats mathématiques de ces
dernières années est un théorème permettant de caractériser
de manière « simple » la structure de toute une classe de
graphes. Les grandes lignes de la démonstration permettent
d'introduire de nombreuses familles de graphes.
e théorème des graphes parfa its cent une preuve, qu ' ils pub lieront en
le nombre chromatique
L'un des domaines les plus anciens et les plus étudiés de la théorie des graphes concerne la colo-
ration. Le théorème des quatre couleurs, par exemple, énonce que l'on peut colorier tous les
sommets d'un graphe planaire avec seulement quatre couleurs. Un problème naturel est de déter-
miner le nombre minimal de couleurs nécessaires pour colorier un graphe G (qu'il soit planaire
ou non) sans que deux sommets adjacents soient coloriés de la même manière. Ce nombre, noté
x(G), s'appelle nombre chromatique du graphe G. Trouver le nombre chromatique d'un graphe
quelconque est non seulement une question NP-complète dans le cas général, mais même le fait
de décider si x(G) = 3 est déjà un problème NP-complet.
Plusieurs résultats partiels existent cependant: on sait déjà que x(G) est inférieur au degré maxi-
mal Ll(G) plus 1. (Le degré maximal d'un graphe Gest le maximum des degrés de ses sommets.)
Le résultat se prouve facilement : on colorie les sommets un par un, dans n'importe quel ordre,
et vu qu'ils n'ont au plus que Ll (G) voisins, donc Ll (G) couleurs interdites, on peut toujours trou-
ver une couleur à assigner à tout sommet.
B
Trois couleurs sont nécessaires pour colorier n'importe quel cycle
de longueur impaire. Ici, l'exemple de C7 : chaque sommet a un
degré égal à 2, mais il faut bien trois couleurs pour le colorier car
le cycle est de longueur impaire.
les graphes de Berge ponibl e auj ourd ' hui fai t plus de cent
ci nquante pages) . Tous ces graphes sont
Un graphe G est parfait quand le nombre par contre fo rtement reliés aux graphes
c hrom atique de c hac un de es sou - cordaux, qui eux n 'ont (par défi nition)
graphes induits est égal à la taille de la pas le dro it d ' avoir un cyc le sans corde
plu s grande c liqu e co mpri se dans le de longueur supéri eure ou éga le à 4 .
sous-graphe. En vocabul ai re coura nt , Le graphes cord aux ont éga le ment
cela signifie que si l'on pre nd un sous- appelés graphes triangulés car on peut
graphe de G , et que l' on cherche sa plus déco mpose r c hac un de le urs cyc les
grande clique, alors il fa udra autant de comme un ensembl e de triangles.
coule urs pour colorier le sous-graphe
D
que pour colorier la clique. Cette propriété
confère à un graphe une grande régul a-
rité , ce qui ex plique l'attention qu 'ont
reçue le graphes parfaits depuis la fin
des année 1950.
Certaines cl asses sont connues depuis A
longtemps comme étant parfaites , dont
le graphe biparti s (et leur co mplé-
ments) ou les graphes cordaux. L' uti -
lité des graph e pa rfa its est qu e de
nombreux problèmes réputés di fficile
(des problèmes NP-difficiles par exemple) A
dev iennent fac iles à résoudre sur cette
cl asse (comme les plus grandes clique Un seul des deux graphes est cordai : le
ou plus grands ensembles indépendants, premier (le second possède un cycle
ain si que le colori age). Le problè me induit de longueur 4, qui est ECFD).
était donc d ' identifier et de caractériser
ces graphes, ce qui est pe rmi s par le On pe ut donc reformul er de mani ère
nouveau théorè me. condensée le théorème de graphes par-
Les graphes de Berge - d'après le mathé- fa its : les graphes de Berge sont exac-
matic ie n et arti ste Cl aude Be rge, qui teme nt les graphes parfaits.
fut l'un des pères de la théorie moderne
des graphes et un me mbre fondateur de Induits, complémentaires
!' Ouvroir de litté rature pote nti ell e - ou adjoints
sont ceux qui ne possèdent ni trou, ni
a ntitrou . Un e a rê te inte rn e d ans un Bien que ! 'étude des graphes so it rela-
graphe e t appelée corde . Un trou est un ti vement récente, un vocabul aire pré-
cycle de longueur impaire supérieure à cis a été adopté . Plusieurs notions assez
5 , sans aucune corde. Un antitrou est le techniques sont nécessa ires pour com-
complémentaire d ' un trou. pre nd re pl e in e me nt le théo rè me des
Ayant introduit ces notions, il remarque graphes parfaits. Tro is types de graphe
qu ' un graphe avec un trou ou un anti- interviennent notamment. Tout d'abord ,
trou ne peut être parfait et conjecture que les sous-graphes induits sont des sous-
les deux défi nitions ont équi valentes . graphe dan le quels toute les arête
Il ne dispose pas alors des outils néces- pré e ntes dans le graphe orig inal sub-
saires à la démonstration (l a preuve di s- i tent. On enlève donc un ensemble de
Le graphe G',
graphe complémentaire de G.
Le graphe G.
prenant les arêtes de G comme nou-
veaux sommets et en reljant deux tels som-
mets si les a rêtes corres po nd a ntes
partageaient une extrémité . Bien que
faisant partie des plus ancie ns graphes
étudiés, il existe toujours des problèmes
ouverts les concernant , notamment sur
les itérations de graphes adjoints (comme
caractériser l'adjoint de l'adjoint de J'ad-
joint( ... ) d'un graphe) .
Le graphe ci-de sus, H, est un
sous-graphe induit de G (et en
particulier un sous-graphe de G).
Le graphe
K2,2,3.
~ 1 ) . Le théorème de
2
A= ; ( 1- p
Turan affirme que cette expression,
obtenue dans ce cas particulier des
graphes Turan (vo ir en encadré) , est la
valeur maximale du nombre d 'arête
d' un graphe den sommet ne compor-
tant pas de p-cl iques.
a :S ( 1 - p ~
2
donc a 0
< ( 1 - p _J
_
) (n - p + 1) seur de problème devant l' Éternel, le
1 2 Hongrois Pal Erdôs, utilise la structure
Puisque G est san s p -clique, chaque des graphes de Turan . Le graphe G
sommet de D est au maximum étant fini, il ex iste un sommet m dont le
adjacent à p - 2 sommets de C, et donc
degréestmaxi mal: d(m) = maxd(u) .
O'. c.o s (p- 2) (n - p + 1). Au bilan final, uES
O'. = O'. c + O'. c.o + 0'. 0 , ce qui , tous ca lcul Notons M l'ensemble des d(m) om-
G à n sommets sans triangle possède au pris en compte pour chacune des d(u)
plus n• / 4 arêtes. arêtes partant du sommet u (quelconque),
En voici une première preuve : puisque G cette quantité apparait d(u) fois dans la
est sans triangle, les voisins d'un sommet somme,d'où L (d(u)+d( v ))= Ld 2 (1t).
ueS
forment un ensemble indépendant ; on
note x la taille de l'ensemble indépendant En s'inspirant des
maximal X. On a donc d(u) s x pour tout définitions en sta-
sommet u. En comptant les y = n - x arêtes tistique de l'espé-
ayant leurs extrémités dans le complémen- rance et de la va-
taire Y de X dans S, on obtient : riance (toujours
< ""d( u ) <
a -w _xy <
_ (X+2 y )2-- Jr_4 . positive ou nulle),
on obtient:
uEY
I:d(u)]'
On a utilisé une inégalité algébrique clas- L [d ( u )- uES n
sique, qui exprime que la moyenne géomé- uES
I
de devenir indépendant de la clique des RÉFÉRENCE
bipartis , de ne pas tourner en boucle, Raisonnements divins. Martin Aigner et Günter Ziegler,
de savoir s'arrêter pour reprendre des Springer-Yerlag, 2013.
la formule d'Euler
et les solides de Platon
Comment une formule découverte par le génial Leonhard
Euler au XVIIIe siècle permet de vérifier que les Grecs de
l'Antiquité n 'avaient oublié aucun solide platonicien ...
Les solides de Platon et leurs graphes planaires. (hexa = six) mais nous préférons l'ap-
où n. et p sont égaux à 4 ou 5. Il ne reste peler cube.
plus que cinq possibilités.
n= 5, p= 3
n= 3, p= 3
D'après les formules précédentes, on
D' aprè les formules précédentes , on a obtient a= 30, s = 20 etf = 12 . Les
a = 6, s = 4 etf = 4. Les Grecs fon- Grecs le nommaient dodécaèdre (ckxléca
daient leur terminologie sur le nombre = douze).
de faces, c'est pourquoi ce solide est Le couple (n., p) correspondant à chaque
appelé tétraèdre (tétra = quatre) . polyèdre s'appelle symbole de Schltifli.
À chaque fois que (n., p) apparaît
n= 3, p= 4 comme symbole de Schlafli d ' un soli-
de platonicien , on trouve aussi le
D'après les formules précédentes, on couple inversé (p, n.). Ce n'est pas un
trouve a = 12 , s = 6 et f = 8. Les hasard : à partir d' un polyèdre donné, on
Les solides
Grecs le nommaient donc octaèdre (octo peut toujours construire un nouveau
de Platon et
leurs graphes = huit). polyèdre , appelé polyèdre dual, dont
planaires. les sommets sont au centre des face du
n= 3, p= 5 premier. li a le même nombre d'arêtes
mais les nombres de sommets et de
D'aprè les form ules faces sont inversés. Le dual d'un solide
précédentes, a = 30, platonicien est encore un solide plato-
s = 12 et f = 20. nicien. Le dual du tétraèdre est un
Les Grec le nom- tétraèdre.
maient icosaèdre
(icosi = vingt). É. J. & T. R.
W
n= 4, p= 3
l616re1c1
D 'apres le formules
précédentes, a = 12 , http://mathworld.wolfram.corn/
s = 8 et f = 6 . Les PlatonicSolid .html
Grecs le nommaient hexaèdre
Le théorème de Ktivari-Sos-Turan
Une questio n clas igue e n théorie extré male des gra phes est de dé te rmine r le
no mbre max imal d 'arête d ' un g raphe simple G à n somme ts qui ne contie nt
pas de sous-graphe H de type donné . C'e tune générali ation du théorè me de
Turan (voir l'article qui lui est consacré dan ce dossier) po ur lequel H = K p ,
le graphe comple t à p sommet . Un exemple en est le théorè me de Ko vari-
S6s-Turan, qui stipule que si le graphe simple G = (S, A ) à n sommets de S et
m arêtes de A ne contient pas K 2_,, avec r ~ 1, alors :
Inté ressons-no us au cardinal (ou no mbre d 'é lé ments) IEI de l'ensemble E des
sommets (u, v, w) de G te ls que u-v e t u-w soie nt des arêtes de A (voir la fi -
gure). Po ur un sommet u de degré d(u), il ex iste autant de config uratio ns c her-
chées que de couples poss ibles parmi d( u) é lé ments, soit ( d~u )} , d 'où :
V w
I E= L (d(u))
1 = ~ [I: d (u)- L2
d(u) ].
2
ue S uE S ueS
D 'autre part, chaque couple de sommets de S, parmi les (; ) possibles, ne peut avoir plu s de r - 1
voisins communs. On a do nc JE J .:S (r - l)~(n- l), soit Ld2 (u)- L d(u) ~ (r - l)n( n -1).
ue S ueS
2
Puisque L d(u) = 2m, et que, par l' inégalité de Cauc hy-Sc hwarz, 4m 2 = (L d(u)) .:S (L d 2 (u)),
11 ES ueS uES
2 2
on obtie nt : 4m s (r - 1) n (n - 1) + 2nm. Cette inégalité du second degré fo urnit le résultat c he rc hé :
m ~ ~ (J 4 ( r - 1)( n - 1) + 1 + 1).
Ce théorè me est souve nt utili sé e n géomé trie discrète po ur borne r le incide nces e ntre di ve rs types
d ' objets géométriques.
Le polyèdre de csaszar
Un monstre topologique
La célèbre formule d'Euler appliquée à un graphe complet
bien choisi permet d'imaginer qu'un polyèdre à sept sommets,
vingt et une arêtes, quatorze faces triangulaires et un trou
pourrait exister. C'est le polyèdre de Csâszâr ! Cet objet per-
met de résoudre des problèmes ardus de combinatoire.
n graphe est complet lorsque Il est aisé de construire ces objets par
Structure du polyèdre de
Csâszar. li peut être .....e~~~~~~~~~t~
-;
..;
colorié de deux couleurs
O" - - - ~ - - - '=
à la façon d'un échiquier.
Le polyèdre, qui se projette sur le plan
suivant un pentagone, est une projection
tridimensionnelle d'un hyper-tétraèdre
quadridimensionnel.
RÉFÉ RENCES
• La formu le magique des polyèdres. Jean-Jacques Dupas, Leonhard
Euler, Bibliothèque T angente 29, 2005.
• Les polyèdres, le gang des Hongrois. Jean-Jacques Dupas,
Tangente 126, 2009.
• On the remarkable Csâszâr polyhedron and ifs applications in problem
solving. Martin Gardner, Scientific American, 1975 .
• A polyhedron without diagonals. Akos Csaszar, Acta Scientiarum
Mathematicarum 13, 1949- 1950.
• Euler'sformulafor polyhedra and related topics. Donald Crowe,
Excursions into Mathematics, Worth Pub, 1969.
• A New Type of Magic Square. Thomas Room, The Mathematical
Gazette 39, 1955 .
Diagrammes de Schlegel :
les polyèdres sont des graphes !
Le vocabulaire des polyèdres nous parle aussi de sommets et
d'arêtes. Alors, les polyèdres sont-ils des graphes ? Eh bien
oui, grâce aux diagrammes de Schlegel. La représentation de
polyèdres convexes sous forme de graphes permet de
résoudre de nombreux problèmes combinatoires.
a difficulté inhé re nte à l' étude n'aura pas d ' image. À tout po int de la
la fourm
et le problème du uoyageur de commerce
Certains problèmes de mathématiques ont des solutions
évidentes mais irréalistes en termes de temps de calcul. Peut-
on alors trouver des solutions efficaces, des algorithmes
rapides et universels ?
n "oJageur de commerce veut
J
soit unique ; plusieurs chemins opti-
maux peuvent avoir la même longueur). n ! ,. ~2mr ( ~
Cette méthode souffre d'un défaut réd-
hibitoire : dès que le nombre de villes Une tournée passant par cent une villes
est élevé, la résolution du problème du néces ite l'examen d'un nombre de
voyageur de commerce requiert un temps parcours de l'ordre de 10 157 (environ
VIE QUOTIDIENNE
100 !) ; de quo i fa ire to urne r un o rdi - Les spéc ia listes du problè me sont pes-
nateur pe rsonne l pe ndant plus ieurs mil - s imi stes ; toutes les solutions ex ac tes
li ards d 'années! e nvisageables, prédisent-ils, seront , pe u
Une autre méthode« intuiti ve», née de ou prou , des avatars de la re che rche
l'expérience du terra in , consiste à choi- exhausti ve. Le voyageur serait condamné
sir, à chaque étape, la ville la plu proche à e rre r é te rn e l le me nt , impui ss ant à
parmi celles qui n'ont pas été déjà visi- ré o udre un problè me échappant à l'en-
tées. Ce procédé, s' il élimine les parcours te nde me nt huma in .
les plus longs, n'assure en rien , au fi nal,
la découverte de la me ille ure o lutio n . Des solutions approchées
Ainsi sur l 'exemple sui va nt , le parcours
tracé en rouge à l'aide de l'algorithme de S ' il est illusoire de che rc he r des solu-
« la ville la plus proche», de longue ur tio ns exactes e t effi caces, la dé termi-
6 + 2.fi. + Jïo, n'est pas le plus court . na ti o n de solution s a pproc hées n 'e t
Le tracé ve rt , par exempl e, est J? ré fé- pas hors de portée. De nombre uses stra-
rable ; sa lo ng ue ur est de 10 + .../2 . tég ies pe rtine ntes ont é té proposée :
Il est surprenant qu ' un problème dont on recuit s imulé, 2-opt , al gorithme de Lin
conn aît un a lgo rithme de résoluti o n et Ke rni g han , a lgorithme de Karp , a lgo-
exacte pui sse ê tre dans la pratique irré- rithme de Keld He ldgaun , algorithme d' in-
mé di abl e me nt intra ita bl e. À l' he ure sertion , recherche avec tabous, algorithmes
actue lle, aucun a lgorithme efficace pe r- géné tiques, a lgorithme ACO (vo ir e n
mettant de venir à bout du problè me du e ncadré) . ..
voyageur de comme rce n'a été décou- Les application pratiques de ces méthodes
vert . Une méthode, écono me e n te mps d 'optimisation ont innombrables : rou-
d'exéc utio n , ex iste-t-elle? La ré ponse tage des jo urnaux et des imprimé , ges-
à cette questio n est toujour pe ndante. tio n d ' un parc de camions c ite rne pour
l'approvis io nne me nt e n essence, prév i-
v, v, sio n des dé le tages sur un réseau auto-
routie r e ngorgé, di stribution des tâc hes
e ntre diffé re ntes u s in e d ' un m ê me
groupe, développe me nt d ' Inte rne t , etc.
Les recherches sur le problè me du voya-
geur de comme rce sont toujours d 'ac-
tualité. La solution est pe ut-être au bout
du c he min !
v. v, v, F.C.
v, v, Références
• Swarm Intelligence: From Nat ural ta Artificial Systems. Éric Bonabeau,
Marco Dorigo et Gu y Théraulaz , Oxford Uni versity Press , 1999.
v, • l'intelligence en essaim. Éric Bonabeau et Guy Théraul az, Pour la
v, Science, mai 2000.
• l'efficacité des algorithmes. Harry Lew is et Christos Papadim itriou, /es
Ma thématiques GL1jo11rd'h ui. Pour La Science-Belin, 1986 .
" v. v, v,
• Inspiration for optimizationfrom social insect behaviour. Éric
Bonabeau, Marco Dorigo et Guy Théraulaz, Nature 406, 2000.
Un travail de fourmis
Lors de leurs déplacements, les fourmis sécrètent une molécule, la phéromone, qui attire et guide
leurs congénères. Si, entre le nid et une source de nourriture, on place un obstacle qui crée deux voies
d'accès de longueurs inégales, on constate un phénomène étonnant. En un laps de temps très bref,
les fourmis choisissent majoritairement le chemin le plus court. L'explication est simple. Au début
de l'expérience, le hasard seul guide les fourmis. Les deux pistes sont alors explorées équitablement
par l'avant-garde des fourmis. Lorsque les premières d'entre elles retournent au nid, elles ont mar-
qué deux fois par des phéromones le trajet le plus court, invitant ainsi le reste de la colonie à emprun-
ter de préférence ce chemin. Marco Dorigo, de l'université libre de Bruxelles, a transposé, dans une
simulation informatique, la stratégie des fourmis au problème du voyageur de commerce. Notons
diJ la distance entre les villes i etj, et -riJ la quantité de phéromone sécrétée sur l'arête connectant i
etj. Une même valeur -r0 , peu élevée, est attribuée initialement à tous les -riJ. L'algorithme ACO (pour
ant colony optimization) peut être résumé ainsi :
(1) Au début de la première itération, on choisit aléatoirement m villes. Une fourmi virtuelle est pla-
cée dans chacune de ces villes.
(2) Chaque fourmi , notée k (1 :S k :S m), entreprend un tour complet, visitant chaque ville une seule
fois et revenant à son point de départ. Lors de son périple, la fourmi actualise en permanence la liste
J k des villes non visitées. (L'algorithme initial de parcour peut être celui de« la ville la plus proche »
ou tout autre algorithme donnant, en un temps raisonnable, un circuit acceptable.)
(3) Lors de la deuxième itération, une fourmi située dans la ville i choisit de se diriger vers la ville j
non encore visitée, avec la probabilité suivante :
Pt =([TvJ[duY}i(~[TuJ[duY).
où a et p sont deux paramètres positifs qui gouvernent l'influence respective des phéromones dif-
fusées ou évaporées et des distances parcourues.
(4) Quand toutes les fourmis ont achevé leur circuit, le tableau des phéromones est mis à jour :
riJ - (1- g)-riJ + A-riJ où u est le taux d'évaporation et A-riJ est le montant des contributions de mar-
quage de l'arête (i,J). Ainsi, A-riJ est proportionnel à la qualité des solutions dans lesquelles (i,J) a
été utilisée par une ou plusieurs fourmis.
Plus précisément, si Lk dénote la longueur du circuit T k parcouru par la fourmi k,
alors: Mu= f...1u;,avec A~ = Q/Lk si (i,J) E Tk et tu; = 0 sinon (Q est un paramètre positif). Cette
procédure de renforcement traduit l'idée que la densité des phéromones doit être plus forte sur les
pistes courtes, un long trajet étant plus difficile à entretenir. Les étapes (1) à (4) sont répétées un
nombre prédéfini de fois , ou jusqu'à l'obtention d'une solution stable. L'algorithme de la colonie
de fourmis est très efficace. U n'identifie pas nécessairement le circuit le plus court, mais ses solu-
tions sont quasi-optimales et, comme l'affirment Éric Bonabeau et Guy Théraulaz, deux spécia-
listes de la question : « Ce système est flexible : les fourmis artificielles explorent continuellement
différentes voies; les multiples pistes de phéromone fournissent donc des plans de secours.Ainsi, lor-
qu'une voie est coupée, des solutions de rechange sont déjà prêtes. Cette propriété, qui explique sans
doute le succès écologique des vraies fourmis, est cruciale pour de nombreuses applications. »
es tâc hes nécessaires à la réa li- Il s'agit ensuite d 'ordonner ces tâches
-aucune
deux cent cinquante fourni eur et neuf mille sou -traitant .
L' utilisation de PERT a permis de ramener la durée globale de
réaJi ation du projet de ept à quatre ans. Un des autres titre de
Z.1 gloire de cette méthode e t attaché à la conquête de la lune : sept
ans seulement ont séparé la déclaration d ' intention du pré ident
1 1, 2, 5 John Kennedy et l' aluni age du module lunaire de Neil Arm-
41 trong et Buzz AJdrin.
s. 7
D.D.
l'algorithme de Dijkstra
Savoir quelles sont les routes embouteillées, c'est bien, mais
encore faut-il déterminer rapidement le chemin à suivre pour
aller le plus vite possible d'un point à un autre. L'algorithme de
Dijkstra est celui qui, à l'heure actuelle, est le plus performant
pour résoudre ce problème.
n problè me impo rtant es t de
U
chaque po int : en partant de A, les tra-
avo ir co mme nt rej o indre le jets composés d ' une arête seraient donc
plu s vite poss ible un po int B a u no mbre d e 3, de de ux a rê tes , au
partant d ' un point A lorsque le systè me nombre de 32 , et ainsi de suite. On trouve
de nav igatio n d ' un conducte ur auto- donc 3" trajets de n arêtes. En se limi-
mobile lui fournit les te mps moyens de tant à sept arêtes, on trouve déjà plus
parcours de chacun des axes poss ibles de deux mille trajets.
en fonction de la densité du trafic. En voici Pour des trajets sur de graphes com-
un exemple: portant des centaine d ' arêtes, avec un
Si on veut essayer tous les chemins pos- ordinateur examinant un milliard de tra-
sibles de A vers B (en excluant les cycles), jet à la econde, il fa udrait plus de 10 30
on arri ve vite à un nombre co lossa l. années pour ve nir à bout du pro blème.
En moye nne, troi s fl èc hes parte nt de Le mo nde est lo in d 'être aussi vieux !
7
L'algorithme de Dijkstra permet 5
d'éviter l 'explosion combinatoire.
V Une ité ration se fait en dernier trajet, Y devra it être dans Q (car
0 deux étapes. D'abord, on Y a dG , lors d ' une étape précédente , être
trajet sé lectionne toutes les inclus dans Q), ce qui contredit la défi-
optimal w(UV)
arê tes UV dont l'ori - nition de X .
g ine U es t dans Q e t Le sommet X ai nsi tro uvé est ensuite
do nt l'extrémité V e t rajouté à l'e nsemble Q , et on pose
extérieure à Q. p (X) =.n(X) et t (X) =r (X), ce qui ter-
Pour chacune d 'ell es, mine cette itération : on recommence
on connaît un trajet opti- alors avec le nouvel ensemble Q « grossi »
mal de A vers U (car U est dans Q). En qui , de proc he en proc he, fi ni ra ain si
prolongeant ce trajet jusqu 'à V, on a un par conte nir le point 8 qui nous inté-
te mp s tot a l d e pa rc our s éga l à resse (sauf si le schéma de circulation
t (U) + w (UV), où w (UV) est le « poids » rend inaccess ible Je point 8 partant de
de l'arête UV (proportionne l au temps A), marquant la fin de l'exécuti on de
de parcours de U à V) . l' algorithme.
Si cette omme est in fé rieure à r (V), ce L'a lgorithme de Dijkstra fo urnit l' iti -
trajet pourrait être un chemin optimal néraire optimal de A vers 8 ainsi que
vers V, et on le retient en posant les itiné raires optimaux pour tous les
r (V) = t (U) + w(UV) et .n(V) = U. point qui , partant de A, ont plus rapides
Ces valeurs re tent toujours relati ves au à atte indre que B. Le temps de calcul ,
me illeur itinéraire actue lle ment connu proportionnel au carré du nombre d'élé-
(notons que V peut être touché par plu- me nts de Q , reste raisonnable, même
sieurs arêtes). pour des ré eaux routi ers à l'éche lle
d' un pays.
Bourgeonnements successifs Po ur un réseau routier rée l, avec des
temps de trajets à peu près proportion-
Da ns une sec onde éta pe, on cho isit , nels aux di stances, la zone Q analysée
parmi les sommets X extérieurs à Q et ressemble très grossièrement à un disque
tels que r (X) <+ oo (et où .n(X) est donc centré en A et de rayon la di stance A B.
défini ), un X qui minimi se r(X). Le tra- Elle regroupe un nombre de sommets
jet optimal de A vers .n(X) (qui est dans proportionnel au carré de cette distance
Q) suivi de l' arête joignant .n(X) à X est et, donc, les temps de calcul s croissent
alors un trajet optimal vers X . En effet, do nc à pe u près comme la pui ssance
s' il ex ista it un traj e t plu s rapide, e n quatrième de AB .
notant Y le prédécesseur de X dans ce J.-L S.
c::J
I J
uand le chemin
se joue aux dés
L'alliance des graphes et de la théorie des probabilités produit
un outil extrêmement utile : les chaînes de Markov. Celles-ci
se retrouvent partout, de l'étude des flux migratoires à
l'analyse du langage.
a s itu ation du té lé phone arabe fo rmu le r de faço n plus « sérieuse » : on
sement). Ce qui nou s intéresse est de tracteur (c'est-à-dire d 'état qui , une foi s
savoir sur quel sommet nous nous trou- atteint , ne peut être quitté), chaque état
verons à l' issue des n lancers de dé. a une certaine probabilité de figurer à long
terme parmi les états visités .
Téléphone arabe
les cases du monopoly
Bien entendu , l'évolution de notre posi-
tion sur le graphe étant sou mi e à l'aléa D' un point de vue ludique, la modélisation
(le mot signifie« dé » e n latin), il n'est par un tel graphe permet d'étudier les jeux
pas po sible d'espérer une réponse déter- de hasard comme le Monopol y: c ' est à
minée. Tout ce que l'on peut fa ire, c'est partir d ' une chaîne de Marko v, un peu
d'estimer des probabilités. L'outil mathé- longue à détailler, qu ' on pe ut détermi-
matique le plus naturel pour étudier Je ner les cases du jeu sur lesquelle les
comportement à la limite (c ' est-à-di re joueurs ont Je plus de chances de tom-
lorsque n dev ient grand) de la probabi - ber (les cases ne sont pas toutes égales
lité de fi nir sur V ou sur F est celui de en termes de probabilités, mê me à long
suite récurrente . li permet de montrer terme) . Avec l' image du chauffe ur de
que, lor que Je nombre n de tran met- tax i, les sommets du graphe représentent
teurs dev ient important , la probabilité les di fférents endroits de la ville où le
que la nouvelle tran mise oit la bonne chauffe ur est su ceptible d ' aller, les pro-
tend vers la valeur 1/2. Ce résultat tra- babilités de arêtes les chances d ' aller
duit le fa it que l' in fo rmation qu i par- à tel ou tel endroit . Dans la fi gure pré-
vient à 1,, est vide, au sens où il y a« une cédente, le point « répul sif» D est alors
chance sur deux » pour que ce soit la un point centra l dans la v ill e, où un
bonne vers ion qui lui parv ienne, et éga- chauffe ur de tax i ne reste en général pas
lement une chance sur deux pour que longtemps avant qu ' un clie nt ne se pré-
ce soit la mauvaise. Le destinataire de sente. Le point A, en revanche, est un point
l' in fo rmation ne peut donc pas accor- à l'écart, où le chauffeur n 'a guère inté-
der le moindre crédit à ce qui lui est dit ! rêt à accepte r de se re ndre. D 'autres
Cette étude s'étend à des situations plus contextes rendent plus uti le l'étude des
générales. Le cas le plus global se décrit graphes précédents. En particulier, on
à partir d' un en emble de point carac- peut penser aux flu x migratoires entre
térisant le état possibles. Les-états sont différents pays (les probabilités se muant
reliés par de arêtes indiquant les tran- alors en proportions d ' une popul ation),
siti ons envi ageab le , chacune d 'elles à l'évolution de l 'état de santé d' un indi-
étant affectée d' une certaine probabilité. vidu (les sommets représentant les dif-
Dans un graphe comme celui de la pré- fé rents stades de di ffé rentes maladies
cédente fig ure, contrai rement à notre qui peuvent se contracter à la suite les
premier exemple, les di ffé rents états ne unes des autres) , ou encore à la circulation
sont pas égaux en termes de probabi li- automobile (les sommets représentant
tés. S'i l est relati vement fac ile de se per- des nœuds de circul ation, les arêtes les
suader que l' état D a peu de chances de axes entre ces nœuds, et les probabili -
survenir souvent à long terme, il est un tés des proportions de véhicules).
peu plus délicat de se con vaincre de ce Certaines étude de la langue utili sent
que, en réalité, on a toutes les chances également les chaînes de Markov. Dans
de fi nir co incé au point A . Dans les cas un texte , l'apparition de te lle ou telle
les plus généraux, où il n'y a pas d 'at- lettre n'est pas indi fférente à l'apparition
de la sui vante. Par exemple, en li sant la à la suite les lettres rencontrées en che-
suite de caractères min, on produit une succes ion de lettres
C O N S T A N T I N O P L, qui ne constituent pas un me sage fran-
chacun conviendra que la probabilité que çais, mais qui ressemble à quelque chose
le caractère sui vant soit un E est extrê- de français .
mement é levée. Une première approche
de l'étude probabiliste d'un texte est alors Du HHHHH à 11Il1
la suivante : on considère un graphe
constitué de vingt-sept sommets (chacun En réalité, pour rendre le modèle plus pré-
repré entant une lettre de l'alphabet, plus cis, il faut tenir compte non pas de la
l'espace , désignant la fin du mot) . Les dernière lettre vue, mai de plu sieurs :
arêtes reliant les sommets sont affectés ici, la probabilité d'apparition d ' un E
de coefficients représentant la probabi- e t beaucoup plu élevée après la lecture
lité qu ' une lettre soit suivie par une autre. des treize iettres précédente qu 'après la
Bien sûr, ces coefficients dépendent de lecture de la lettre L seule. Bien, sûr, la
la langue dans laque ll e les mots sont connaissance des douze dernières lettres
considérés . En français , par exemple, du (le C étant exclu) aurait suffit : en réa-
sommet Q ne partent que peu d'arêtes, celle lité , une approximation assez rai son-
Dans cette figure , le point menant à U étant affectée d ' une très forte nable consiste à s upposer qu'au-delà
A est un « trou » ou probabilité. d'un écart de quelques lettres, il n'y a
« puits » : dès qu'on arrive Dans ce contexte de « graphe de Mar- plus suffisamment de lien entre les lettres
dessus, on ne peut plus en kov de la langue française », une étude pour qu ' il so it nécessa ire d'en tenir
sortir. À l'inverse, le point comme celle du téléphone arabe ne peut compte. Si l'on décide de s'en tenir à,
D est répulsif : à peine avoir pour objectif de déterminer une di sons, cinq lettres, le graphe de Mar-
arrivé dessus, on est obligé « lettre ultime » d ' un texte écrit en fran- kov a pour sommet s l'en emble des
d'en repartir. Le point C çais. E ll e donne plutôt la fréq uence suites de cinq lettres (de AAAAA à zzz:z:z
est en quelque sorte moyenne d 'apparition de chaque lettre, en passant par YOUPI, MIAOU . .. sa ns
neutre : il permet d' aller et permet donc de savoir par quelle lettre oublier les séquences avec un ou plu-
n'importe où sans préfé- commencer (on tire au sort, en affec- ieurs espacements, tels que VAS Y). D' un
rence particulière. Enfin, tant à chaque lettre une probabilité pro- sommet tel que GRAPH partent alors vingt-
les points E, F et G consti- portionnelle à sa fréquence moyenne sept arêtes, affectées de probabilités
tuent quasiment une d 'apparition). On peut aussi s' intéres- diverses, aboutissant à toutes les suites
boucle : il y a une probabi- ser à la fabricatio n de « non-sens fran- de caractères dont les troi s premières
lité très forte pour que, çais» : en suivant le graphe de Markov lettres sont RAPH (RAPHA, RAPHB, RAPHC ... ).
arrivé sur E, on suive au selon les règles indiquées et en notant La séquence ci-dessous a été réali sée
moins une fois ces points informatiquement à partir de ces consi-
dans l'ordre. dérations pour le graphe de Markov du
latin :
IBUS CENT IPITIA VETIS IPS E CUM VIVIUS ...
Aucun mot n'a de sens dan la langue
concernée, et pourtant il est manifeste
que cela re semble fort à de « vrais
1/7
mots» de latin. Pour un peu, on se pren-
drait à croire que l' ordinateur cherche à
nous dire quelque chose ...
B.R.
1/7
Un problème de
téléphonie mobile
Comment faire en sorte que le passage de relai entre deux
bornes de téléphonie mobile se fasse dans les meilleures
conditions pour l'utilisateur ? La technique aujourd'hui
employée, qui utilise la notion d'arbre couvrant, répond au
problème de manière particulièrement efficace.
Pé riode T
i'TTTTTTT'TTI 1··· I
D D
~mission
du mobile
i'T'TTTTTTT'Tl
Le concept même du té léphone mobile
repose sur le fa it que les utilisate ur se
déplacent en l' utilisant , que ce soit e n
1··· I
BTS1
voiture (passagers, unique me nt !) ou à
pied . Ains i, il arri ve re lative me nt fré-
quemment qu ' un mobile passe d ' une 11111 l 1 1 1 1 1 1... 1
BTS2
borne à une autre . À ce mome nt-là,
pour éviter des interférences avec les
mobiles connectés à la no uvelle borne ,
jO (son temps d 'émission est r éduit)
er les borne . Une seconde raison est utili sé à autre chose. De plu s, les
que de ux mo biles phys ique me nt bo rnes BTS ne peuve nt mod ifi er le ur
proches mais communiquant avec des phase que très le nte ment.
borne différe ntes pe uvent se brouiller Une autre solution , purement algorith-
sur une partie du paquet seuleme nt et mique, a fort heureusement été trouvée .
rendre ainsi inopérantes les méthodes de Elle fonctionne de la manière uivante : les
traite ment des interfé re nces mention- bornes disposent d' un système pour écou-
nées plu haut. ter les signaux provenant de mobiles
communiquant avec une borne voisine ,
D'une borne à l'autre ce qui permet à chaque borne de calcu-
ler son dépha age avec chacune de ses
Pour sync hroni ser les bornes, la vois ines , mê me s i cette info rmat io n lui
mé thode la plus simple serait d ' utiliser parvient à des mome nts imprév is ibles.
un éléme nt exté rieur, un GPS par Ce systè me pe rmet de définir un graphe
exemple , qui enverrait un « top » à cha- dont les ommets sont les bornes et dont
cune d 'elles et les synchroniserait direc- les arêtes relient celles qui interfèrent suf-
te ment. Ce tte solutio n n 'a pas été re te- fi amment souvent pour que leur dépha-
nue pour des raisons politiques. sage soit connu régulièrement. (Ce graphe
dépend beaucoup du terrain environnant ,
Il serait égale ment possible de faire des immeubles, des fleuves qui créent des
e nvoyer un « top » par d 'autres bornes, interférences supplémentaires , etc.) Une
dites BSC (base station controllers), fo is en possession de ce graphe (manifes-
qui contrôle nt plus ieurs BTS : e n syn- tement non orienté car la mesure du
chronisant ces bornes elles-mê mes , on déphasage est réalisée par les deux bornes
obtie ndrai t le résultat voulu . Ce tte en même temps), il reste alors à trouver
solution n 'a pas non plus é té re te nue un algorithme permettant de synchroniser
car les communications e ntre les ses sommets. Cet algorithme doit être
bornes BTS et les bornes BSC sont purement « local », en ce sens que chaque
déjà nombreuses, et cette communica- borne ne peut agir directement que sur la
tion utili serait du te mps qui peut être phase des bornes qui lui sont voisines. De
plus, pour que l'algorithme soit véritable-
ment efficace, il doit résister à toutes
sortes de contrainte , qui vont des pannes
de bornes BTS aux ajouts de nouvelles
bornes (susceptibles de modifier sensible-
ment la structure du graphe).
La solution qui a été retenue utilise la Quand une borne tombe en panne, il faut
notion d'arbre, en complément d'autres que toutes ceUes qui en dépendent, directe-
méthodes plus classiques pour donner ment ou indirectement, puissent se syn-
une valeur constante aux sommet d'un chroniser à l'aide d'autres bornes, ce qui
graphe (par exemple la méthode du gra- est toujours possible à moins que la borne
dient, très efficace dès que le borne sont en panne ne provoque une coupure du
proches de l'état de synchronisation). graphe en deux parties non reliées l'une à
Le graphe étant connu, on en extrait un l'autre. Enfin, lorsqu ' une borne BTS est
sous-graphe avec exactement le mêmes ajoutée, on lui impose d'être une feuille
sommets , mai avec moins d'arêtes : de l'arbre (c'est-à-dire de n'être reliée qu'à
plus précisément , on fait en sorte que le une seule autre borne) et de se synchroni-
sous-graphe considéré soit un arbre, ser avec le sommet du graphe avec lequel
c'est-à-dire à la fois d' un seul tenant et eUe a le plus d'interférences.
sans chemin qui boucle (connexe et
sans cycle, en termes techniques : tous Des arbres de qualité
les sommet sont reliés les uns aux
autres par un chemin, et il n'ex iste De nombreux paramètres permettent
qu'un chemin d' un sommet à un autre). d'établir la qualité des arbres couvrants
Un tel arbre est appelé arbre couvrant choisis, notamment le nombre de dépha-
du graphe initial , comme dans sages calculés par chaque arête du
l'exemple ci-des ous. graphe, le nombre commun d'arêtes
entre l'arbre couvrant et son arbre bis ,
ou encore la taille du plus long chemin
existant dans l'arbre. En optimisant sui-
vant ces différents critères, on obtient un
système à la fois rapide (car le sommets
ne sont pas trop éloignés de la racine),
fiab le (car les synchronisations sont fré-
quentes) , résistant aux pannes grâce au
circuit bis , et enfin qui permet l'ajout de
nouvelles bornes .
En orientant les arêtes de l'arbre
couvrant, on obtient un arbre orien- Signalons enfin que cette technique a été
té passant par tou s les so mmets du validée à l'aide d'un simulateur développé
graphe. Il suffit alors d 'i mposer à pour l'occasion , qui a permis de voir que
chaque sommet de se connecter à l'algorithme est à la fois très efficace et
celui qui le précède dans l'arbre , seul évite les situations de blocage. Ce travail
un sommet (appelé racine) ne fai- de mise en place du simulateur a aussi été
sant rien . Pour éviter qu ' une panne l'occasion de poser des problèmes théo-
de l' une des bornes n'empêche le riques intéressants, notamment la ques-
bon fonctionnement de l'a lgorith- tion d'engendrer aléatoirement certains
me, le plu s s imple est de prévoir un types de graphes. Ainsi, le va-et-vient
arbre couvrant bi s (comme les itiné- entre la théorie et la pratique se poursuit.
raires du même nom) et de le mettre
en place s i l'une des bornes ne par- J.-C. N.
vient plu à se synchroni er à celle
qui lui es t dévolue .
Des arbres
pour faire passer des trains
Comment minimiser le coût d'un réseau ferroviaire ?
L'algorithme de Kruskal donne un moyen simple et efficace de
le faire. Et produit quelques surprises.
ébut des années 2030 . La SNCF tout en continuant à pouvo ir relier ces
D v ie nt de me ttre a u po int le
Sup e r-TG V, bea uco up plu s
rapide que le TGV
deux villes .. . mais en passant par Paris.
Pour la même raison, toutes les li aisons
dessinées en bleu peuvent ai nsi être sup-
d e ces d e rni è res primées ! On obtient alors une structure
décenni es. Mais il d ' arbre (un arbre possède toujours une
ne pe ut ro ule r sur arê te de moin s que de so mme ts) : il
le réseau ex istant : ex iste toujour une faço n et une seule de
toute les voies fe r- relier une ville à une autre en sui vant le
rées doivent donc réseau. Chacune des vi lles constitue un
être recon truites ! sommet, chacune des étapes une arête.
D a n s un so u c i
d 'éco n o mi e, o n
vo udra it po uvo ir
relier entre elles le
vingt et une capi -
tales régionales de
la fi n du siècle der-
nier en constru isant
le moin s de vo ies
poss ibles.
En France jacobine,
tout passe par Paris.
Un réseau dess iné
selon ces pri ncipes
pourrait être sem- Hrbre jacobin
bl abl e à ce lu i du
dess in ci -contre. L'arbre jacobin n'est pas le plus court que
Ce ré eau n 'est pas l' on pui s e imag iner. En admettant que
le plu s court : on peut par exemple sup- le coût de construction de la voie soit pro-
primer la liaison directe Rouen- Amiens, portionnel à sa longueur, on a intérêt à
1
VIE QUOTIDIENNE
Propriété de l'arbre minimal cripti ve pour établir des c lass ificat ions
par groupes, par exemple pour regrou-
Considérons un arbre qui ne comprend pas l'arête qui per les vingt et une capita les régionales
joint le sommet S à son plus proche voisin T. en plusieurs« superstructure » consti-
tuée de vi lles « proches entre elles ».
En supprimant la plus longue étape (Bor-
deaux- Toulouse}, on obtient deux groupes.
Pour e n avo ir troi s, o n s upprime la
seconde plus longue étape (Toulouse-
Montpellier). La ville de Toulouse consti-
tue alors un groupe à elle seule. En ôtant
les k plus grandes arêtes de l'arbre mini-
Montrons que cet arbre n'est pas minimal. Dans l'arbre mal , on obtient k + 1 groupes, qui consti-
initial, il existe un chemin qui permet d'aller de S à T. tuent des « super-régions » , dont on peut
Supprimons la première étape de ce chemin, et ajou- ain si choisir le nombre et la répartition
tons l'arête qui joint S à T. géographique.
G. G. &T.R.
Références
• Graphes et algorithmes. Michel Gondran
et Michel Minoux , Eyrolles, 1995 .
• Proof Jrom the book . Manin Aigner et Günter
Ziegler, Spri nger. 1998.
A
Ce groupe est constitué de six éléments: les trois symétries sA, sB et sc
par rapport aux axes (OA), (OB) et (OC) respectivement, les deux
rotations r 120 et r 240 de centre O et d'angles 120° et 240°, et l'iden-
,,, tité idT. L'ensemble des trois symétries est générateur, puisque
1 id = s/ , r 120 = sB . sA et r 240 = sc . sA. Le graphe de Cayley de G par
....... . . . . '
.. .. 1 ...
rapport à S est le suivant :
,' O,
id
c B
Chaque ar ête est orientée dans les
deux sens. Bien entendu, ce n'est
pas toujours le cas pour un groupe G et une sc- -----i11--_,........,.,___ r 240
Comment éuiter
Quand les distances se mesurent en minutes, la ligne droite
est rarement le plus court chemin d'un point à un autre. Les
randonneurs comme les automobilistes le savent bien, mais
comment trouver l'itinéraire le plus rapide ?
/ /_ 1i V''COl·50Um f
=/ cot• •- 1 1 · ~d uc .-c::,_,. .
'
----o l(IIQ ••
/f Il.'
flimm
"'
•
,·
COI. lGIIIAII SI• lf.S IOOIUIS , , ..
= o---CJL..... ,, .. ,... ..... ~
f r-o•
= COllUPlls- 50U. 1$
ua~J1. - ~ :
J
<•;
•t'llfOl(t
;i . gJlNWNI- :.J ~ o o fOlfKMUT
"-.,_~ ~ - ,.,0 , m g - .... <OIOU_
t _ <&11-t
t.. . . ., • • \
1
• • • •
.U00 / <all<Olll'l.W ,.__.,.. \\
~ '\.. - __.i:---\\~
r' -- . .
· If ~·: J., .~ ~· -:::::,: IOIU..UI=:
l l fl ~ ....." 1 COllll.Wlllll ll " /
u<•- ~ .. \:
lU"III »,' , li
l.UIO. A • O 'flUI r u hl o Ul.Alm
~ ll-USt.1111
•
,.,s woi..::o. f'IOMOITOIM O ~. «llrlilSIII" ~ ,
~
. ----
.+-- - ' ' - ' - ' - - - - O
llfm•u.1Ru o
0\ mtaSOlllUI
\ ,,
\1ii
0 111. . UQI
o ..... oo.ltru1111
\
7
JI'
..
lllllGll u!I(
o~
,',t
,·u
il)! -\\ -
~
/
/
I
~
s c0t•
l 'IWlAUI&
\, -7 1-....
I ,._ I'•
-·'"'
_ _. .,, •~ Ôl(r"[PUJIOIAII llfKl • CMœ A,USHMU.w,./
I I
!, Pl ~ --- u .... P - 1
•• , ~ ... <UCOIUI<
"!o.,... ~
lllllGlsllt O
~ 1·•
llt!IIT
o lU. . . . fOIT!IIIA! // !llll8mwl- / _ ~~ (OI...... /o•
O mua•l'OWI ~, ~ t
_ \ ..,....,.,,...,O ~ · ~41 1 ' '..,,lU
- ~,,
-.. . . . . 0 ---
• 4 ---'
//cot • "' u
Sf.llAI - · -- - - - - - - 0
1•• .....
a fllGIIU UIS
lNTlf
IJY.
_ 0 : ; ; : : - - uawuu '' • "'"" . • • ,• w -
ection interméd iai re et si le sens de tra- encore plu rapide, d 'où la solution Réseau de
jet de U ver V e t auto risé . À toute A- l.r-R- P- B, qui ne prend que dix-sept sentiers en
montagne avec
arête U- V on a ocie un coefficient de minutes. C'e t alors que, constatant que le
temps de
pondération, proportionne l au temps périphérique intérieur est très fluide , on parcours.
nécessaire pour parcourir U- V compte décide finalement de partir dans la direc- Le dénivelé fait
tenu de la distance et des condi tions de tion opposée à celle de l'objectif, et de que les
circul ation. rejoindre en C le périphérique intérieur, itinéraires
C 'est ainsi qu' une rue à sens unique est que l'on suit jusqu 'en H pour gagner fina-
doivent être
fléchés : le temps
représentée par une arête unique , une lement B . On choisit donc le trajet de parcours n'est
rue à double sens par deux arêtes (une A-C- D-E-F-G- H- B, qui prend quinze pas le même
dans chaque sens) et les temps de par- minutes. (Quitter le périphérique en F dans un sens et
cours sont parfois di ffé rents d ' un sens à aurait été une mauvaise solution car Q-B dans l'autre.
l' autre compte tenu de la densité du tra- et Q-P sont embouteillés .) Pour d 'autres
raisons
fic. La fig ure ci-de su mo ntre
(embouteillages),
l'exemple d ' une ville pourvue d ' un l'éloignement aide au rapprochement les graphes de
boulevard périphérique à double ens et navigation
très fl uide , ai n i que de rues à trafic Cet exemple , tout à fai t réaliste pour une routière sont
plus lent et parfois fo rt emboute illées ville comme Paris, montre qu ' un bon iti- aussi orientés.
(comme pour aller de N à P). néraire peut démarrer en tournant le do
Il serait logique , pour trouver l'itinéraire à l' objecti f. Pour trouver cette solu-
le plus court, d'avancer toujours dans la tion , il a fallu ana lyser plusieurs che-
direction de l'objectif. Dans l'exemple m in s. Tenons-nous la solut ion optima-
précédent, cela conduit à l' itinéraire le ? Pour le avo ir, il faudrait explorer
A- N- P- B, qui prend vingt-quatre to us les c he min s possibles ma is ,
minutes . Cependant, la rue N- P étant même en éliminant les bo uc les , c ' est
embouteillée dans le sens de N vers P, i I en pratique imposs ible : po ur une ville
vaut mieux faire le détour N- R- P, qui fai t réelle , le graphe contient considérable-
économiser six minutes . Passer par L est ment plus d ' arêtes que celui de notre
Exemple de
modélisation
de la situation
du trafic d'une
grande ville.
Les temps de
parcours entre
les points
d'intersection,
exprimés en
minutes,
indiquent
qu'on a affaire
à une ville dont
le centre est
surchargé et
dont le
boulevard
périphérique
est fluide.
exemple, sans parler des navigateurs de raisonnable pour que le conducteur puis-
voiture actuels, qui pe uvent contenir la se avoir l' info rmation dont il a besoin en
carte routière de l'ensemble de la France un temps acceptable.
(y compri s tous les pl ans de toutes le
villes), ce qui représente un graphe Encore plus fort : les heuristiques
gigantesque . L'énumération de tous les
chemins po sibles conduit à une explo- On peut considérablement accélérer
sion combinatoire et, mê me sur un l' algorithme en défini ssant une notion
ordinateur de pointe, les temps de cal- de « grands axes » et en prenant en
cul e compteraient plutôt en sièc les compte des règles intuiti ves (appelées
qu 'en mjnutes. heuristiques) du type « une fo is sur un
La olution aujourd ' hui employée est un grand axe , on y reste jusqu 'à ce que l' on
algorithme dû à Dijkstra (voir par ailleurs soit proche du point d 'arrivée » . Dans
dans ce numéro), dont le temp de calcul , certains cas , certes, cet algorithme accé-
proportionnel au carré du nombre de léré donne un résultat non optimal,
points, est raisonnable même pour des mais, en général, l'économie de temps
réseaux routiers à l'échelle d' un pays. Cet de calcul est phénoménale à l'échelle
algorithme consiste à « bourgeonner » d ' un pay . Tout repose sur l'astuce dont
autour de A, en déterminant de proche en on a fa it preuve dans la définition des
proche les plus courts chemins menant de heuristique et dans le choix des grands
A aux autres points (en commençant par axes. Comme souvent dans les applica-
les plus proches de A). Pour un réseau tions pratiques, on peut opter pour un
routier réel, avec des temps de trajets à algorithme exact mais parfois lent , ou
peu près proportionnels aux distances, les pour un algorithme accéléré, parfois
temps de calculs croissent à peu près non optimal mais souvent de vitesse
comme la puissance quatrième de la dis- d'exécution beaucoup plus rapide.
tance AB : c'est beaucoup , mais à l'échel-
le d' une ville, c'est encore suffisamment J.-L. S.
-
deux graphes donnés sont équivalents.
Ce problème non résolu dans toute sa
généralité se pose en particulier pour
classer les molécules chimiques.
Une condition nécessaire d'équi-
valence est bien sûr qu'ils aient le
même nombre de sommets. Mais
d'autres invariants existent,
comme le degré des sommets, la distance (topologique) à un sommet particulier, la taille de la
clique maximale ou le nombre chromatique. Si certaines de ces quantités ne sont pas égales,
les graphes ne peuvent être isomorphes.
La dualité point-droite de Poncelet et la correspondance Delaunay-Voronoï pour les mail-
lages amènent à définir le graphe adjoint G' d'un graphe G en associant un sommet à chaque
arête de G, deux sommets de G' étant adjacents si les arêtes correspondantes ont un sommet
de G en commun. Ainsi, le graphe adjoint du tétraèdre est le graphe octaédrique.
Un arbre
pour le théatre
Un texte littéraire est avant tout une suite de mots. Avant
d'enfiler les mots à la suite les uns des autres, on peut décider
au préalable de choisir une structure qui organise l'ensemble.
Dans cette phase, les mathématiques peuvent jouer un rôle.
ans les années 1960, un grou- Créations combinatoires
soit pas trop longue. En uite , uivant La, structure de graphe permet de multiplier
le choix finalement retenu , le acteur les possibilités avec un minimum d'efforts
jouent te lle ou telle cène. Par
pour les comédiens.
exemple, la scène 1 nou montre le roi
tri ste, que la reine ne parvient pas à
consoler. Pourquoi est-il malheureux ? C 'est cette question qui fait l'objet d' un
choix de la part des spectateurs,
- - - - - - 1rr choix confrontés à l'alternative suivante:
- la fille du roi , la princesse, a perdu le
•• - 2• choix ourire ;
- la princesse a été enlevée.
Si les pectateurs se prononcent pour la
première po sibilité , alor les comé-
dien jouent la cène numérotée 2 dans
4' choix le graphe de la figure de la page précé-
dente. Si , à l' inverse, ils optent majo-
ritairement pour la seconde, c'est alors
la scène n°3 qui e t jouée.
Structuralisme. langage
Ce sont les publications de Lévi-
Strauss qui ont donné naissance
au structuralisme. qui a envahi
peu à peu toutes les sciences
humaines. l'histoire et la gram-
maire notamment. (Le structura-
lisme a. dans ses excès. souvent
trop privilégié la structure formel-
les seize le des choses étudiées au détri-
chemins cun correspondant à une scène potentiel- ment du sens. et a progressive-
Pour lister toutes lement jouée. Parmi celles-ci , quatre ment perdu de son aura.)
les pièces pos- n'engagent pas le spectateur. Dit autre- Par exemple. connaître la struc-
sibles, une métho- ment , l' arbre comprend quinze cènes, ture d'une langue en apprend
de systématique dont quatre seulement ne débouchent pa
consiste à partir le
autant que connaître les mots
sur un choix des pectateurs. Une étude isolément car dès qu'on la
plus à gauche pos-
simple montre qu ' il est possible de connaît. on peut d'un seul coup
sible en descen-
jouer seize pièces différentes , autrement se lancer dans l'apprentissage
dant le graphe, et
en ne bifurquant à
dit que le nombre de chemins du graphe de toutes les langues ayant une
droite que si tous menant de la racine (la cène 1) aux structure similaire. Un exemple
les chemins plus à feuille (le cène 14 et 15) est de 16. parmi d ·autres : la structure de la
gauche ont déjà San l ' utili ation de cette tructure, le langue arabe, dite de dérivation.
été visités . En sui- eize pièce di ffé rentes obtenue auraient Les mots sont groupés par
vant cette règle , on néce ité l'écriture de pas moins de familles . chaque famille est
trouve les 16 che- quatre-vingt cène (cinq cène par engendrée à partir d"une racine.
mins suivants : pièce), d'où d' in urmontables difficultés Par adjonction de lettres à la raci-
2 4 6 10 14 d' apprenti age pour les comédien . La
2 4 6 11 15 ne. on forme d 'autres mots,
structure de l' arbre à théâtre possède chaque type d ·adjonction corres-
2 4 7 10 14
ainsi un intérêt « économique », repré- pondant à une même classe de
2 4 7 11 15
sentant à elle seule seize pièces poten- sens. Par exemple, la racine
2 5 8 12 14
1 2 5 8 13 15 tielles tout en ne nécessitant la mémori- « KTB » (signifiant « il a écrit »)
1 2 5 9 12 14 sation que de quinze scènes différentes. donne. en ajoutant une lettre. le
1 2 5 9 13 15 L'écriture à contraintes a connu son mot « celui qui écrit» (l'écrivain)
3 4 6 10 14 heure de gloire surtout à l'époque de et. en ajoutant deux lettres, le
3 4 6 11 15 l' ère structurali te (voir en encadré). mot « ce qui est écrit» (le destin,
3 4 7 10 14 Cependant , les oulipiens continuent maktoub). Cette racine engendre
3 4 7 11 15 encore à être actif aujourd ' hui et ren- ainsi une vingtaine de mots.
3 5 8 12 14 contrent un uccè qui ne ' est jamais
13 15 D'autres racines peuvent engen-
3 5 8 démenti .
3 5 9 12 14 drer plus d"une cinquantaine de
N. V. mots.
3 5 9 13 15
Entre sens
Parler, c'est transformer ce que l'on veut dire en ce que l'on
dit, autrement dit un sens en un texte. Cette correspondance
entre sens et textes peut se décrire par des graphes, pas
toujours simples à interpréter.
1 est délicat de définir et de repré- « départ » et « pleure ». Toutes ces rela-
phrases ont le même graphe et sont donc L'interaction des sens des mots
des paraphrase de la phrase initiale. Par
exemple:
peut se représenter par un graphe.
(2) « Pierre pleure , parce que cadeau à Marie », « donner » en a trois qui
Marie part », se réalisent comme sujet, objet direct et
objet indirect.
(3) « Les pleurs de Pierre sont dus L' autre partie fo rme la grammaire pro-
au départ de Marie », prement dite : règ les de conjugaison,
place du sujet par rapport au verbe , etc.
(4) « Le départ de Marie fait pleu- Pour décrire la correspondance entre
rer Pierre » • graphes sémantique et textes, il est pré-
férable de considérer des représentations
Comme on le voit, le sens « causer » intermédiaires, notamment une représen-
peut être exprimé en français de mul - tation dite syntaxique. La grammaire
tiples faço ns (« à cause de » , « parce devient alors modulaire : un premier
que », «être dO à » , « faire » sui vi de module assure la correspondance entre le
l'i nfi nitif. .. ) . graphe sémantique et la représentation
Le graphe sémantique d ' une phrase peut syntaxique et un second module assure
avoir des cycles, comme dans la phrase la correspondance entre la représentation
« Pierre croit entendre Marie ». syntax ique et le texte.
Un graphe sémantique ne représente
qu'une partie du sens, dite situationnelle, L'arbre de dépendance
qui renvoie à la situation que l'on veut
décrire. Les phrases précédentes, bien que La représentation syntaxique que nous
décrivant toute la même ituation, ne adoptons s'appelle un arore de dépendan-
peuvent être employées dans les mêmes ce syntaxique, notion développée par
contextes de communication et sont donc Lucien Tesnière , lingui ste majeur du
différentes de ce point de vue. xxe siècle. Les nœ uds de cet arbre sont
Le passage du sens au tex te pe ut être les mots de la phrase et ses arcs ont éti -
modélisé par un ensemble fi ni de quetés par des relation syntax iques indi-
règ les, qui permettent de construire un quant la fo nction du mot dépendant par
graphe sémantique. Une partie de cet rapport au mot dont il dépend .
Voici ces arbres pour les phrases (2) et (3) :
'causer' pleure
/0 " /o,
1 2
"
sujet circonstanciel
'partir' 'pleurer'
cl
1
~1 . O/
Pierre Q parce que
1
conjoncl ion
1 1
t
'Marie'
t
'Pierre'
1
Q part
1
(2) sujet
ensemble de règles forme le lexique et 1
concerne la description des mots. Par 0
exemple, « pleurer » po sède un unique
Marie
a-gument, alors que dan « Pierre donne un
les Q / "' Q de
1
"'Q a'
1
la configuration « sont du à » ; le sen
« pleurer » devient un dépendant de ce
prépositionnel pré1>ositionncl verbe et est exprimé par le nom
1 1 « pleurs » .
Pierre Q Q départ
"
/ cplt-dc-norn
déterminant
S ' il existe des cycles dans le graphe , il
faut les couper soit sur un arc (ce qui
le Q / "'Q de
1
donne « Pierre croit entendre Marie »
pour notre deuxième exemple de graphe),
prépo;itionncl soit sur un nœ ud . De cette opération
1 résulte l' introduction de pronoms,
0 comme le pronom « i1 » renvoyant à
(3) Marie
Pierre dans « Pierre croit qu ' il entend
Un mot ne correspond pas forcément à Marie ».
une chaîne de caractère entre deux Le pa age de l'ordre de dépendance
espaces . Ain i, «au» e t considéré syntax ique au texte consi te à ordonner
comme l' amalgame de deux mots, « à » les nœuds de l' arbre syntax ique selon
et « le », tandis que « parce que » e t des règle qui font intervenir le type de
considéré comme un seul mot. l'arc qui les relie .
Pour passer du graphe sémantique à un Il y a tout lieu de penser que le ens e t
arbre de dépendance, il faut choisir le un objet multidimensionne l. Là où la
nœud qui correspondra à la racine de hiérarchi sation assure le passage d ' un
l'arbre (ce choix est guidé par la structura- graphe sémantique à un arbre syn-
tion communicative), puis suspendre le tax ique (un arbre est un graphe hiérar-
graphe par cette racine. Ensuite, il faut chi sé), la linéarisation, quant à elle,
choisir pour chaque sens dans le graphe permet le passage d ' un arbre syntaxique
un ou plusieurs mots qui l'expriment à une suite linéaire de mots.
(« causer » s' exprime par « à cause de »
ou « être dO à » , par exemple). S. K.
En français comme dan la plupart des
langues, la racine
de l'arbre de dépen-
dance doit être un linguistique. sémantique et svntaxe
verbe . Décrire ce que produit quelqu'un qui parle ou qui
Par exemple, pour écrit et la façon dont il le produit est l'objet de la
l' arbre de (2) , le li11y11istiq11e. La S('/11Wlliq11e. quant ù elle, s'occupe
nœud sémantique du sens des mots et des textes, lù où la syntaxe
« pleurer » est choi- s'occupe de leurs constructions. Ainsi, la phrase
si pour exprimer la « d'incolores idées \'ertes dorment furieusement »
racine de l'arbre et est syntaxiqm,ment correcte, alors que « les
donne le verbe enfants joue dans la cour » ne l'est pas. Du point de
« pleure » ; le sen \'lie sémantique, c'est le contraire.
« causer » devient
' l' inverse de la topologie, de il n'y a pas de « boucles »), ce qui impo-
ISCI ne UI
/
(autrement dit...)
e eros
Il y a une trentaine d'années, c'est-à-dire bien avant Harry
Potter, un type particulier de livres pour la jeunesse a été
inventé. Structurés par des graphes , ils permettent une
narration originale.
n 1982 , les Britanniques Steve logiquement doté aussi du premier rôle
d' utilisation du style « lorsqu 'il sera remporté Roland-Garros une nouvel-
temps d 'utiliser la fo rmule magique, le fois. L'année suivante, vous êtes à
ajoutez 10 au paragraphe où vous vous nouveau confrontée à Serena
trouverez alors». Le lecteur qui n'a pas Williams en finale ; l'expérience
rencontré au préalable le sorcier ne peut acquise lors de votre défaite pourrait
alors pas poursui vre comme si c 'était le vous aider à prendre votre
cas . revanche ... Rendez-vous au 1.
B. R .
5. Votre adversaire manque sa volée.
Un début d'histoire dont vous êtes Vous êtes à 4 partout dans la derniè-
le héros. Si le cœur vous en dit, re manche. Lancez une pièce : si elle
poursuivez-la et complétez son tombe sur pile, rendez-vous au 9.
graphe. Sinon, rendez-vous au 4.
Allez savoir comment, vous êtes 6. Un point qui restera dans les
en finale dames des internatio- annales ! Vous empochez la premiè-
naux de France de Roland-Garros, re manche. Rendez-vous au 8.
opposée à Serena Williams, tenan-
te du titre. 7. Votre service va au filet : vous êtes
Il faut remporter deux manches désormais menée une manche à
pour gagner la partie. zéro. Rendez-vous au 8.
Rendez-vous au 1.
8. La seconde manche commence,
1. Vous donnez-vous à fond pour aussi âpre que la première. Lancez
gagner la première manche? Si oui , un dé : si vous obtenez 3 ou moins,
rendez-vous au 2. Si vous préférez vous perdez la manche (rendez-vous
vous économiser, rendez-vous au 3. au 4 si vous aviez perdu la première),
sinon, vous l'emportez (rendez-vous
2. Au prix d'un gros effort, vous rem- au 9 si vous aviez remporté la pre-
portez la première manche. Mais, mière ). Si vous en êtes à une
épuisée, vous perdez la suivante et manche partout, rendez-vous au 5.
vous êtes menée 4-2 dans la troisiè-
me. Lancez un dé : si vous obtenez 1 9. Victoire! Après un superbe échan-
ou 2, rendez-vous au 4. Sinon , ren- ge final , vous remportez la partie. Au
dez-vous au 5. moment de vous saisir du trophée
retentissent alors une série de
3. Vous êtes au jeu décisif dans la « Bip ! » caractéristiques de la sonne-
première manche. Tentez-vous un rie du réveil ... Vous ne pensiez tout
service-volée (rendez-vous au 6), ou de même pas que vous aviez gagné
servez-vous normalement (rendez- Roland-Garros !
vous au 7)?
B. R.
4. « Dès le début de la partie, je sen-
tais que ce serait difficile .. . » Le jour- Problème subsidiaire : réaliser le
naliste qui vous interroge le lende- graphe représentant l'évolution pos-
main de votre défaite prend un air sible d'un jeu au tennis selon les règles
compatissant. Serena Williams a habituelles (15--0, 15 partout, etc.).
Le word ladder.
un ieu sur les mots de Lewis Carroll
Prenez deux mots de quatre lettres au hasard, comme All\IE et l\IATH. Peut-on passer de
I\m à l'autre en plusieurs étapes consistant chacune à modifier une lettre? Ce jeu inventé
par Lewis Carroll concerne le graphe dont les sommets sont les mots de quatre lettres,
que l'on relie par une arête si l'on peut passer de l'un à l'autre selon la règle imposée. En
utilisant une méthode initiée par Donald Knuth , on s'aperçoit que ce graphe est constitué
de plusieurs composantes connexes ... dont l'une regroupe près de 95 % des mots. Fort de
cette quasi-certitude d'une solution à notre jeu, on trouve la suite All\IE- l\111\IE- l\IITE-
l\lITA-MATA-MATH.
Dans
l'intormatique
G R
Parler à son
Bientôt, vous parlerez à votre ordinateur et il vous compren-
dra. Derrière ce progrès, prédit par bien des auteurs de scien-
ce-fiction, se cachent les graphes de mots.
phonème ait été prononcé (ou ait voulu probabilités données par le modèle à
être prononcé) . Ainsi, nous pouvon chacun des phonèmes constituant le
associer au ignal un ensemble de suites mot.
pos ibles de phonème , chacune de ces
suites étant affectée d' une probabilité, les phrases : des hypothèses
donnée par le modèle acou tique.
En tant qu ' entités sonores, les mots Une suite de mots est une hypothèse de
sont formés de phonèmes. Certaines phrase. Le nombre d ' hypothèses de
suites de phonèmes candidates ne cor- phrases pouvant correspondre au signal
respondent à aucun mot : elles sont de parole peut être très grand (des cen-
alors éliminées. Seules les suites de taines de milliers, voire des centaines
phonèmes repré entant des mots sont de millions) . Pour que les calculs pui s-
conservées . Le système associe alors sent être effectués dans un délai raison-
des mots à chaque suite de phonèmes. nable , il est nécessaire d ' utiliser un
Comme il peut exister des mots diffé- outil efficace : c'est ici qu ' interviennent
rents pour une même suite de pho- les graphes de mots. Un graphe de
nèmes (par exemple pour le mots mot permet de représenter de manière
homophones comme « chaîne » et très compacte les hypothè es de phrase
« chêne »), il y a davantage de uites de a sociées au signal de parole enregistré.
mots que de suites de phonèmes con er- S' agis ant de traiter d 'aussi nombreuses
vées. Chaque mot po sède une probabi- hypothè e , les performances des algo-
lité acoustique, calculée à partir de rithmes de recherche du chemin optimal
En reconnais ance de
la parole, les arêtes j bonjour ;
forme
sont en général appe- euh~,02 0 .006
lées des transitions, et 10002 1
les so mmets des
nœuds . Un graphe de
mots est un graphe Exemple de graphe de mots
orienté par le temps :
La probabilité d' une phrase est égale au produit des jour a,I 0007 effort 0008 me 0.005
. 0003
~ ',,.
probabilités d'apparition de chacun des mots. IO
Retrouuer un mot
ans un
Zut! Je crois bien avoir écrit tout à l'heure« Hufftnan » avec
deux « n » au lieu d'un seul ! Mais où diable se trouve ce mot
dans mon fichier? Heureusement, mon éditeur de texte peut
le savoir. Il utilise des graphes spécifiques, les automates.
ans un ordi nateur, un texte T Dan le pire de cas, on effectue 311
mot vide). Dans un tel graphe, on parle un texte fai t passer de l'état initi al à
cf états plutôt que de sommets et de l' état fi nal si, et seulement si, il
transitions plutôt que d'arêtes . Deux contient le moti f « ses » .
états sont à distinguer des autres : E est
appelé l'état initial et « se » l'état Avec cette méthode, pour vérifier si le
fina l (flèche entrante et flèche sortante). motif « ses » figure dans un mot de lon-
Chaque tran iti on (all ant d ' un état p à gueur n, il faut effectuer seulement n
un état q) est étiquetée par une lettre comparaison . Plus généralement, à tout
I : la lecture de la lettre l fait passer motif on peut a socier un automate tel
l' automate de l'état p à l'état q. que, pour véri fier si ce motif fig ure dans
un mes age de longueur n, il suffi t d'ef-
Si l'on soumet un texte tel que « son fectuer n comparaisons. La fa brication
chat se chauffe à e pieds » à cet auto- préalable de cet automate demande p
mate, il part de l'état initial E. Le pre- opérations si le moti f est de longueur
mier caractère, « s », fai t passer de p : cela donne donc n + p opérations en
l'état initial à l'état « s » pui s « o » fa it tout. La méthode est illustrée ci-des-
revenir à ! 'état E. Les caractères sui- sous pour l' automate reconnaissant le
vants maintiennent l'automate à l'état motif « maman ». Le principe de fabri-
E, jusqu 'à l'arrivée de « s », puis de cation se généralise faci lement à n' im-
« e » et de « », qui fo nt alors passer porte quel motif.
successivement à « s » , « se » et à nou- H. L.
veau à E, et ain si de sui te. De la sorte ,
;t m
;ta, m
;t m, n
les réseauM
e neurones
Les réseaux de neurones informatiques s'inspirent de la forme
des vrais neurones. Capables de progresser au fil du temps dans
l'analyse de situations du même type, ils s'éloignent toutefois
sensiblement de leur modèle biologique.
e cerveau humain est composé de neurones d'informaticien
Bien entendu , ces « neurones » ne ont Ce premier exemple montre que les
qu'un modèle mathématique des neurones réseaux neuronaux , mê me s' il s sont
effectifs de notre cerveau : on parle à leur d ' inspiration biolog ique , ont des
sujet de neurones fo rmels. En les mettant objets purement mathématiques. Dans
en réseau, on obtient un « réseau de neu- cet exemple , le réseau ne po ède pas de
rones ». De tels réseaux peuvent donc boucle. Autrement dit , aucun retour en
aussi bien être considérés comme des arrière n'est possible. Chaque neurone
modèles de certai nes fonctions de notre fait son travail après ses prédécesseurs,
cerveau (vue, mémoire ... ) que comme des une couche après l'autre, le résultat ne
instruments mathématiques . dépend donc pas du temps . Pour cette
Pour illustrer ce second point de vue, raison, on dit qu ' il est statique. Ce type
Walter Pitts.
voici un exemple trè simple de réseau de réseau est utili sé pour évaluer des
de neurones réalisant la multiplication fonctions mathématiques comme dans
Les réseaux
de deux nombres donnés en entrée : l'exemple précédent mais aussi dans la
de neurones
reconnaissance de formes. Bien enten- en couches.
a du , pour de questions plus compli-
- _ ..,_,,,_..- - - ,-..._.......... ab Les propriétés
quées que celle de notre exemple, on de ces réseaux
L. -- -- utili se des réseaux avec un grand dépendent
Un réseau de neurones sans boucle à
nombre de couches comportant pour la du nombre
deux couches. Les deux premiers neu-
plupart un grand nombre de neurones. de couches
rones (première couche) ont comme
11e11ro11es couche 11e11ro11es
et du nombre
fonction de transfert la fonction loga-
d 'e11/ree cachée de sortie de neurones
rithme. Ensuite, ln (a) et ln(b) sont
,~ -~~
par couche.
additionnés en entrée du troisième
Ils décrivent assez
neurone (deuxième couche). La fonc-
bien les premières
tion de transfert est alors l'exponentiel-
le, la sortie donne donc le produit a.b.
~~~ 7"--è!. , - -==ao. étapes des
systèmes sensoriels.
Files d'attente :
Des arbres binaires
en faire tout un tas I presque complets
Dans les ordinateurs, plusieurs
tâches sont effectuée simulta- On peut toujours représenter les
nément. Cela permet de gérer au éléments d'un tableau, comme
mieux les di verses ressource à [o ; 1; 2 ; 3; 4; 5 ; 6 ; 7; 8 ;
la dispo ition du processeur (mé- 9], sous une forme arbores-
moi re, imprimante ... ). Pour chaque cente :
ressource, l' ordinateur utilise donc
une file d'attente. Le même pro- Un tel graphe est appe-
blème e retrouve sur les réseaux lé un arbre binaire
(Internet. .. ). Une gesti on de ces p resque complet.
tâches s'impose. Si , comme sur un Les emplace-
ordinateur personnel, le nombre ments cerclés sur
de travaux en cours est minime, le schéma sont
la représentation peut prendre la les nœ uds, le pre-
fo rme d' un simple tableau uni-
mier nœud en partant du haut est la racine. Chacun
dimensionnel (un vecteur) et du
des deux nœuds descendant d'un nœud donné sont
ses.fils (gauche et droit). Si les éléments du tableau
principe suivant lequel le premier
sont numérotés de o à n - 1, l'élément i a pour fils
arrivé est également le premier ser-
2i + 1 et 2i + 2 . Si chaque élément est supérieur à
vi : on retrouve la queue classique
ses deux fils, on parle de structure de tas.
des boulangeries le dimanche ma-
De façon générale, on définit les arbres binaires
tin. Si la queue est de longueur n et
sur les nombres entiers au moyen des
que chaque travail prend le même
deux règles de construction suivantes h. x
temps, l'attente est alors propor-
un nombre est un arbre binaire, si x
tionnelle à n. Dans les cas où n
est un nombre et g et d deux arbres
est petit, ce système est suffisant,
binaires, alors est un arbre binaire. g d
mais sur de grands réseaux, une
telle gestion aboutit au blocage de
tout le système. Il fa ut donner des
ordres de priorité afin que les tâches Hauteur d'un arbre
les plus e sentielles puissent être Dans le cas d ' un arbre binaire complet, la rela-
accomplies les premières. tion entre le nombre d'éléme nt net la hau-
L'idée de départ est donc d ' attri- te ur h est fac ile à déterminer. En effet,
buer à chaque travail un numéro à la hauteur 0, l' arbre a un seul élé-
de priorité et de créer une fil e d 'at- ment (la racine). Ensuite, à chaque
tente. Chaque fo is qu ' un nouveau niveau, le nombre d 'élément double
travail a besoin de la res ource, il puisque chaque élément a deux fil s.
est in éré dans la file avec on nu- Ainsi, si la hauteur est h, le nombre
méro. Chaque foi s que la ressource d 'élément de l' arbre complet est
est disponible, l'élément ayant la égal à 1 + 2 + ... + 2", soit 2 h+i - 1.
prio rité la plus élevée dans la file Pour un arbre presque complet, on a
en e t extrait. C'est )'exemple des donc 2h < n < 2"+ 1 - 1, ce qui donne
serv ice d' urgences des hôpitaux. h s log2(n) < h + 1.
dans la base) . La recherche s' est faite en quant à lui , peut davantage : on pe ut
au plus di x-sept comparaisons. Ce imag iner de fa ire évoluer la base , en
résultat est indépendant de l'étiquette lui ajo utant ou en lui supprimant des
cherchée, il provient du fait que l'on a é lé me nts. Avec notre structure « en
2' 7 > 100000 . Plus générale ment, pour dictionnaire », pour ajoute r (ou sup-
chercher un mot dans une base de n primer) un é lé ment , il fa ut trou ver
articles, le temps est au plus propor- l' e mplacement où l' on doit l' insérer
ti onnel à logi(n). (ou l'endroit où il se trou ve pour le
supprimer). Le te mps que cela prend
Des mots qui uont et qui ulennent est le même que celui d ' une recherche ,
c'est-à-dire proportionne l à logi(n).
Du point de vue de celui qui la consul - Mais ce n' est pas tout : il fa ut ensuite
te , la que tion des bases de données est insérer (ou supprime r) l' é léme nt
ainsi à peu près clo e. Pour le fo urnis- concerné et, pour cela, déplacer d ' un
seur de la base, en revanche , tout reste cran tou s ceux situés après lui , que ce
à faire. soit pour lui laisser une pl ace ou pour
boucher le trou qu ' il laisse . Cela fa it
Quand il s ' ag it de constituer une liste entre I et n étiquettes à déplacer, donc,
sur papier, comme dans le cas d ' un dans le pire des cas, le temps nécessai-
dictionnaire , la seule chose à fa ire est re à cette opération est proportionnel à
de ra semble r les éléments de la liste n. En conséquence , si la base de don-
et de les ranger dans l'ordre (alphabé- nées doit évoluer réguliè rement , les
tique, le plus souvent). L'ordinateur, coûts de maintenance sont élevés .
C
-- A
B C
A A BC D
A c
B C
B C A B
Résolution du cas : A de hauteur h - 2, B et C
Résolution du cas : A de hauteur h - 2, B de de hauteur h - 2 ou h - 3 (l'un au moins de hau-
hauteur h - 1 ou h - 2 et C de hauteur h - 1. teur h - 2) et D de hauteur h - 2.
Des arbres
David Huffman a donné son nom à une méthode de compres-
sion des données aujourd'hui à la base des diverses compres-
sions utilisées sur Internet : JPEG, MPEG 1 , 2 et 3. Elle peut
également servir en cryptographie.
e codage de Huffman est une a = 1101 , b = 0 , c = 101 , d = 111 et
l 'arbre de Huffman
Optimalité de Hullman
On peut montrer le résultat suivant : soit T un texte dans lequel chaque caractère a a une fréquence
f (a). Supposon que x et y soient les deux caractère le moin fréquents de T. Il exi te alors un
codage préfixe optimal tel que le caractères x et y aient des codes de même longueur et ne difre-
rent que par le dernier bit.
Le nombre de codages préfixe étant fini , l' un d 'entre eux est optimal (la longueur du texte codé
corre pondant e t minimale). Soit A l'arbre correspondant. On considère a et b deux feuilles sœurs
de profondeur maximale dans A et, quitte à changer les notations,
on suppo e que/ (a)~ f (b) et/ (x) ~ f (y).
Pui quex ety ont le lettre les moins fréquentes, on af (x) ~ f (a)
et/(y) ~ f (b). On permute alors les position de a et de x puis de
b et de y dan l'arbre A. On obtient un nouvel arbre B . La longueur
du codage du texte corre pondant à B e t inférieure à celle corres-
pondant à A puisque a et b ont plus fréquentes que x et y. La lon-
gueur du code correspondant à A étant minimale , les deux lon-
gueurs sont donc égales. L'arbre Best donc optimal. Dans ce coda-
ge, les codes de x et de y ont même longueur et ne different que par
le dernier bit.
L'étape suivante revient à remplacer x et y dans le texte T par
z = {x, y} de fréquence f (z) = f (x) + f (y) et à coder le texte T'
ainsi obtenu suivant le même principe. Les longueurs des deux
textes codés ont les mêmes puisque celles des codes de x et de y
le sont au si. L'algorithme de Huffman est donc optimal.
Hrbres,
jeuK et stratégies
Comment créer à la pelle des jeux de stratégie inédits ?
Comment devenir invincible au jeu d'échecs? La réponse à
ces questions se trouve dans les arbres, qui sont des graphes
particuliers.
oici une méthode pour créer des l'un des arc partant de la rac in e et
• ou bien le nombre écrit sur la rac ine est L'a lgorithme du mini max permet théo-
strictement positif ; cela signifi e que riquement de déterminer la meilleure
le joueur 1 possède une stratég ie qui stratég ie dans n' importe que l jeu fini à
lui permet de gagner contre tout autre info rmation complète où le hasard n' in-
joueur, auss i intelli gent soit-il ; tervient pas, ainsi que de dire lequel des
• ou bien le nombre est négati f ; dans deux joueurs est sûr de gagner (ou éven-
ce cas, c'est le joueur 2 qui peut s'as- tue ll eme nt que les de ux j oueurs sont
surer de la victoire ; assurés du match nul). Mais, bien qu 'ex-
• ou bien le nombre e t nul , et alors cha- trêmement simple, cet algorithme n' est
cun des deux joueurs peut assurer le pas utili sable en pratique pour les je ux
match nul dans tous les cas . cl assiques comme les échec , à eau e
du nombre fa ramine ux de nœ uds que
De plus, une fo is que )'arbre du jeu est compterait) 'arbre à étudier. Cette méthode
complètement rempli , la me illeure stra- néce siterait en effet l'analyse de toutes
tégie de chacun de joueurs est évidente : les positio ns du j eu avant de pou voir
le joueur 1 doit toujours choisir, parmi déterminer le meilleur premier coup des
les pos iti ons poss ibles , celle de valeur blancs ! Le vrais programmes qui jouent
max imum , et le joueur 2 celle de valeur aux échecs n ' effectue nt pas une te lle
mm1mum. analyse rétrograde en partant des pos i-
tions fin ales . Ils procèdent comme les
joueurs humains en partant d ' une situa-
tion donnée et en se projetant que lques
coups dans le futur.
La pui ssance des ordinateurs actuels ne
pe rmet ! 'étude co mpl ète que de je ux
très simples comme le mo rpion (dont
le graphe comporte déjà plusieurs mil -
liers de nœuds et dont l' issue est le match
nul ). Mais peut-être un jour nos machines
seront-elles capables de résoudre le pro-
blè me sui vant :
3 6 9 12 15
Graphes et
•
a r1n
En assimilant les couloirs d 'un labyrinthe aux arêtes d 'un
graphe et les carrefours à ses sommets, la théorie permet de
se sortir de n 'importe quel labyrinthe. Ah, si Thésée avait
connu la théorie des graphes ...
es labyrinthes constitue nt un XJJf siècle . Ma is les labyrinthes o nt
L'algorithme
de la main
gauche
appliqué à
deux
labyrinthes
Oesecond
labyrinthe
présente un
îlot, son
graphe
associé n'est
pas un arbre).
L' intérêt d ' un labyrinthe peut être mul- On peut vouloir visiter tous les recoins
tiple: selon les cas, le but peut être d 'ac-
d'un labyrinthe, ou seulement vouloir
céder à un point précis du labyrinthe, ou
bien de «visiter» l' intégral ité du laby- s'en échapper.
ri nthe dans le but d 'y découvrir une tenant. Le graphe associé à un tel laby-
structure particuljère, un trésor, ou une rinthe est alors un arbre (montrez- le !).
issue secrète, avant d 'en res ortir. Une Dès que le labyrinthe comporte des îlots
que lion théorique se po e alors : com- intérieurs entourés de murs, la « méthode
ment explorer un labyrinthe de façon de la main gauche» ne permet plus d'en
sy tématique, c'est-à-dire comment par- explorer I' intégraljté. Heureusement pour
couri r toute se galerie , ans en les Thésée modernes, des méthodes d'ex-
oublier le mo indre recoin ? ploration plus sopru tiquées ont été élabo-
rées, quj s'adaptent à tous les labyrinthes.
la méthode de la main gauche
la méthode de Gaston Tarry
Une première méthode d 'exploration ,
très simple d 'emploi , consiste à se Gas ton Tarry (1 843- 191 3) est un
déplacer en longeant continuellement le mathématicien françrus de la fin du XIXe
mur de gauche (ou bien celui de droite). siècle qui s'est intéressé à di vers
Hélas, cette méthode ne fonctionne à thèmes des mathématiques récréati ves,
coup sûr que dans les labyrinthes sans comme les carrés multirnagiques. En
Gaston Tarry.
«îlots», c'est-à-dire dont les murs 1895 , il énonce une méthode systéma-
constituent un ensemble d ' un seul tique d 'exploration des labyrinthes, qui
la méthode de TrémeauK
M. C.
5 6
5 2
6 A
les billes
Mais ce nouveau graphe n'est pas très
li sible avec cette di sposition des som- Vo ic i maintenant un tro isiè me problè-
mets . Nou s allon donc « déplier » ce me extrait du concours Logic'Flip .
graphe afin de lui donner une fo rme un
peu plus « présentable » . Des billes ont été placées dan s
Surpri se ! Le nou veau graphe « déplié » ces boîtes selon les règles sui-
est le même que le graphe de départ. Ce vantes. Chaque boîte contient un
graphe est dit autocomplémentaire . nombre différent de billes (entre
Niveau de difficulté
Trouuez v
)
vv
lrt•s facill'
facill'
pas facill'
.•
uniquement à A et F, et A à B et D, où Sur le plan ci-contre, Alfa e t reliée di -
se trouve C? recte ment à tro is ville . Balla et Calot
.•
sont reliées directement à quatre ville .
.......· ..··.
~. -·················
..•:'~ On ne pe ut aller directement d ' Alfa à
:• ' Balla, mais ces de ux villes peuve nt être
~ ..··· ..,.·· ·····~.
• ••• ll!tl ••••
V ·:...........................
• ••
atteintes directement de Calot.
Où se trouve Dahu si, d e cette ville,
on p eut a ller directem ent à Ba lla et à
HS5403 - En partant d'Hlfa v C alot , m a is pas à Alfa ?
nœuds (intersections), et des arête de moins que les boîtes situées juste
de longueur unité (segments joignant à côté. Le boîte A et H contiennent
deux nœuds). treize billes à elles deux.
Quelle est la longueur du circuit le Combien y a-t-il de billes
plus long (chemin partant d' un nœud dans la boîte D ?
et abouti ssant à ce nœud), sachant
qu'on ne peut emprunter qu ' une seule
fo is une arête et qu 'on ne peut passer
qu' une seule fo is sur un nœud (à l'ex-
ception du point de départ) ?
Ces textes sont issus d 'un remarquable document publié par HS5413 - Trauersée de frontières
le CNDP (aujourd 'hui Canapé). Chaque énoncé est suivi
d 'une indication des connaissances mises en j eu. Nous re- Cinq pays sont représentés ci-après
mercions Claudine Robert de nous avoir permis de les pu- avec leurs fronti ères. Est-il possible
blier. de partir d'un pays et d'y revenir en
franchissant chaque frontière une
HS5411 - Les enueloppes fois et une seule ?
0
Peut-on parcourir une fois et une
seule les arêtes des graphes ci-des- ,.
sous sans lever le crayon ?
!1
0 0
HS5412 - Dominos
0 2 0 2 4 3
• Conte nu : graphes complets ; chaînes
eulériennes ; degré d ' un sommet ;
théorème d 'Euler.
• Tous les titres avec les HS «kiosque ». •• Tous les titres avec les HS Bibliothèque. ••• Tous les titres avec les deux HS.
Total à payer
J e joins mon paiem ent par (établissements scolaires , joindre bon de commande administratif) :
HS5404- {A ; B ; C} ={l ; 7 ; 8} et {D ; E ;
F} = {2 ; 4 ; 6}. B est égaJ à l ou 4. Si B = 1, HS5408 -
alors C = 8 et A = 7. Si B = 4, alors C = l et
A= 7. Dans tou le cas, on a donc A= 7.
3 3 3 3
Tangente
Publié par les Éditions POLE
SftS au capital de 42 000 euros
s1e1e socl1l
80 bd Salnt-mlchel - 75006 Paris
Commission paritaire : 1016 K 80883
Dépôt légal ~ parution
Directeur de Publlc1tlen et de le Red1ctlon
Gilles COHEn
Secrn11re de red1ctlen
Édouard THOffiftS, assisté d'Estelle DUBOIS
Ont coll1bore a ce numero
nlcolas BlftflCHftRD, Francis CftSIRO,
Clément CHftRPEnTIER, michel CRITOn,
Jean-Paul DElftHftYE, Dauid DELHUnHY,
Thierry DE LH RUE, Jean-Jacques DUPHS,
Yannick ESTtUE, Gérard GRHnCHER,
Bertrand HftUCHECORnE, Élise JHnURESSE,
Syluain KftHftnE, François LHUHLLOU,
Herué LEHnmG, Jean-Christophe nouELll,
Beno1t RITTHUD, Jean-lue STEHLÉ,
Daniel nmnm, norbert UERDIER
ffl1quette
Guillaume GftlDOT, Romain GIRHUD,
natacha LHUGIER
~DITIONS.
Prix: 19,80 € POLE