Résolution de problèmes à l'aide de graphe (II) Cours 3

Description

Etudiez les devoirs et les activités 2009/2010 pour la classe de terminale ES.

Sujets

• Mathematics
• Chiffre
• Arithmétique
• Addition
• Soustraction
• Multiplication
• Opération
• Formules mathématiques simples
• Géométrie
• Algèbre
• Nombres

Informations

• Publié par: classe-de-terminale-es
• Publié le: 01 janvier 2009
• Nombre de lectures: 68
• Langue: Français

Extrait

T ES
...........................
...............
...............
.......................................
trouv
er.
Comme
a
de
ts
nous
parmi
en
don
a
livreur
v
ar?tes
ons
plus
l'habitude,
passan
il

est
oser
ais?
un
de
est
remarquer

que
une
de
p
telles
?
situations
ts
p
son
euv
ositifs.
en
el?s
t
parcours
se
.
ramener
esoin
?
nom
l'?tude
p
d'un
osen
graphe.
tre
Les
qui
math?maticiens
Dans
et

informaticiens
I)
on
de
t
4
prop

os?
un
div
les
erses
aect?es
m?tho
ts
des

(ou
t
algorithmes)
ses
p
doit
our
pizzas,
r?soudre
hemin.
le

probl?me
trouv
du
ons
plus
situations



somme
hemin.
ts
Une
la
des
Une
solutions
haine
les
sommets
plus


relien
est
ha?ne
un

algorithme
he
qui
?s
p
aphes
orte
(partie
le
?
nom
graphes
de
de
son
Sp
in
en
v
la
en
est
teur,
graphe
l'informaticien
t
n?erlandais
ar?tes
Edsger
t
Dijkstra
de
et

a
p
?t?
Ces
publi?

en
son
1959.
app
Mais

a
?
v
prop
an
que
?
aux
solution
de
Exemple
Du
V

un
Le
p
plus
A
er
E
de
B
b
3
v
1
nous
5
breuses
1
d'une
3
haine
de
la
nouv
des
elles
oin
notions.
des
1.1
qui
D?nitions

D?nition
t.
1
plus
Gr

aphe
en
p
deux
ond?r
est,
?
les
Un
ha?nes
dit
les
probl?me
t,
dit

qui
de
Et
hemin
ts.

fr?quen
d'un
plus
herc
des
1
est
ond?r
probl?me
orient?s,

Gr
ternet,
I
in
graphes
sur
l'aide
donn?es
probl?mes
des
R?solution
mission
l'aide
trans-
probl?mes
la
R?solution
par
?cialit?
t
t
Cours
d'?tudier

1
algorithme

nous
graphe
a
ond?r?.
v
C
ons
S
b
D
esoin,
3

1
toujours,
3
de
1
d?nir
1E S
1 ◦
◦
∞
2 ◦ X
◦ X
3 ◦ Y X p
X X Y
◦ p Y
p Y ◦
Y
4 ◦
◦
5
E A B C D S
∞ ∞ ∞ ∞ ∞ E
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
sous
vide
P
Sommet
allons
l'on
our
d'un

l'algorithme
haque
es
sommet
Sommet

?

de
t
plus
?
jusqu'au
la
:
,
le

?crire
la
sommets
somme
de
er
derni?re
en
0
tre
graphe
le


et

V
t
our
de
?rer
y
sous
et
de
du
t
p
2?me
oids
dans
de
Sommet
l'ar?te
Etap
relian
fur
t
les
ra
des
?
ligne
et
tableau,
.

ligne
les
Si
le
elle
Dijkstra
est
vien

de
t
de
inf?rieur
les
au
es

le

la
t
sommets.
de
0
nouv

dans
et
la
le
ligne
0
pr?c?den

te,
du
inscrire
Sur
une
1?re
dans
graphe
la
tous

0


o
de
dan
?
te
hoisir
de
que
la
form?e

et
Commenecr
l'ensem
.

minimal.
Sommet
Sinon,
t
inscrire
utiliserons
le
utilisation

t.

et
t
en
de
hemin
t
trouv
de
allons
la
Algorithme
ligne
pro
pr?c?den
t,
te,
ainsi

suite

sommet
.
d?part.
ligne

par
?tap
des


p

remplir
ts
tableau
de
1.
la
dans
ligne
Rep
pr?c?den
autres
te.

de
les
sommet
t
S'il

reste
2.
des
d?part
sommets
sommet
non
sous


retourner
0
?

l'?tap
le
e
tableau,
2.
ligne
le
la
Sinon,
tableau.
passer
ligne
?
la
l'?tap
3.
e
du
5.
les
ligne
Placer
La

longueur
eectuer
minimale
he
est
e
le
l'algorithme.
nom
l'?x?cution
bre
mesure
lu
et
sur
au
la

derni?re
nous
ligne
sommets
du
par
tableau.

La
la

sommets
haine
ble
de
4.
longueur
os?e
minimale
est
se
premi?re
trouv

e
la
en
don
lisan
une
t
nous
le
de
tableau
haque
en
A
repartan
pr?c?den
t
du
du
sommets
dernier
tre
de

sommet
le
et

en
er
regardan
t
t

de
Nous
quel
de
sommet
et
1.2

la
2E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
5(C) 7(C) D
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
5(C) 7(C) C
6(D) S
E−B−C−D−S
S
D D
C
v2
v v1 4
v3
..................
la
mani?re
suiv
orien
ar?tes
que
an
Sommet
te
que
:
an
dans
est
la
graphe

t?es,
gauc
eut
de
sens.
3
,
on

rep
l'origine
?re
plus
le
Sommet
p
t
oin
t
t
?
inscrit
ne
le
les
plus
un
en
2
bas,
en

:
?
Une
.
une
Puis
don
dans
l'extr?mit?
la


0
droite
0
on
un
note
don
le
les
sommet
son
inscrit
orien
le

plus
dire
en
l'on
bas,
p
de
parcourir

ar?tes
Le
dans
p
seul
oids
Exemple
de
t

l'?criv

3
he,
ha?ne
est
D?nition
6.
Boucle
2
b
Graphes
est
orien
ar?te
t?s
t?e
D?nition
t
2
et
Gr
donc
aphe
haine
orient?

Un
Une
graphe

orien
6.
t?

est
.
5.
On
l'obtien
Exemple
t
3A
B C
n
n n×n i
j i j 0
 
1 0 1A
 A= 0 1 1
0 0 0
C
B
t
n
um?rot?s
une
Un
L
1
?tiquet?
?
p
?

est
?tiquet?s
une
les
matrice
bres


de
v
dimension
ts

tation
asso
aphe
matrice
orien
,
aect?es
o?
son
le
5
terme
:
guran
A
t
pas
en
des
ligne
mais
La
reli?s
et
t

3
orient?
5
est
Un
?gale
un
?
don
1
son
s'il
Remarque
existe
les
une
des
ar?te
ositifs.
d'orgine
graphes
aphe
t
et
ALEZY,
d'extr?mit?b
gr
E
,
non
et
a
un
ec
sinon.
sommets
Exemple
ts,
4

?
et
son
par
p
ar?te
sommets
oss?dan
les
l'orien
t

e
Graphes

D?nition
asso
Gr
e
?tiquet?
Matric
graphe
don
est
un
graphe
d'ordre
t?
t?
t
orien
ar?tes
p
t
est
d'?tiquettes.
graphe
2
dans
graphe
graphe
ond?r?
4
un
D?nition
?tiquet?
g?n?rer
lequel
de
?tiquettes
des
t
des.
nom
graphe
p
an
Exemple
p
Les
par
?tiquet?s
de
ermetten
les
de