Résolution de problèmes à l'aide de graphe (I) Activité 2
5
pages
Français
Documents
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
5
pages
Français
Documents
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
T ES
−1 2 0 0 −1 −1A = 2 3 4
B = 2 1 3 C = 1 −1 0
3 −1 2 −1 0 1
2B−5C
A×B
B×C C×B
2 1 1 0 1
M = 3 4 N = 0 1 1
1 0 1
2 3 2M M N
3 7N N
10N
la
:
F
Calculer
an
1.
En
:
asso
matrices
ordre
les
Calculer
la
On
1.
1
t
graphes
D
l'aide
C
?
probl?mes
bre
de
?rier
R?solution
2
la
les
?
graphes
On
en
2
sommets
?tique.
B
A
B
1.
E
Calculer
degr?
?
des
la
le
main
et
.
v
.
?
,
2.
3
Calculer
D?terminer
et
matrice
et
.
.
des
2.
suiv
A
ts,
v
rangean
ec
les
la
par
alphab
d?terminer
A
tes
E
3.
C
,
A
an
F
Calculer
D
2.
On
le
le
de
suiv
t
sommets.
1
d?duire
suiv
nom
matrices
d'ar?tes.
deux
4
.
3.
graphe
Emettre
an
une
:
surB F
DABCFBEFAE
3
graphe
une
en
4
notan
d'am
t
;
les
4,
sommets
bien
par
ville.
ordre
alphab
tableau
?tique.
2
2.
situation
D?terminer
ar?te.
le
euv
nom
Le
bre
services
de
Malheureusemen
t
ha?nes
de
:
longueur
diciles
5
5
relian
1.
t
d'ordre
repr?sen
et
degr?
de
au
.
in
Lesquelles
5
te
R?p
d?signe
ondre
1,
par
,5,
V
r
amis
ai
relations
ou
son
F
dans
aux
an
?
2
6
v
des
5,
armations
2,
suiv
2,
an
ter
tes.
un
1.
dans
Le
dicile
graphe
par
Pr?ciser
tre
est
p
um
2.
t-elles
Le
sans
graphe
dicile
est
3.
plan
Le
sommet
nom
t
bre
hniques.
d'ar?tes
2,
de
,4
6.
graphe
t,
est
de
im-
six
pair.
on
4.
des
Le
diciles
graphe
admet
t
un
le
eul?rien.
suiv
5.
t
Le
1
graphe
3
admet
5
une
Relations
a
ha?ne
ec
eul?rienne.
1,
6.
6
La
5
3,
ha?ne
6
matrice
5
la
Repr?sen
Ecrire
1.
par
D
graphe
E
6,
F
lequel
C
relation
B
est
A
t?e
sommet
une
en
2.
le
le
bre
de
du
haque
3.
et
est
d?duire
une
nom
d'ar?tes
ha?ne
graphe.
eul?rienne.
Com
B
de
F
ersonnes
C
maxim
E
p
A
en
D
?tre
vit?es
6
risque
Une
p
?
ersonne
?
souhaiterait
7
in
graphe
viter
repr?sen
six
le
amis
d'une
que
Le
nous
A
d?signons
l'emplacemen
par
des
les
2
hiresen
Les
otre
sommets
de
B,
C,
ues.
D,
en
E,
0,
F
du
et
graphe
G
Donner
d?signen
pi?ton
t
m?me
les
jeu
emplacemen
ts
3.
de
t
jardins
et
publics.
Une
D
ar?te
graphe,
repr?sen
ses
te
toutes
l'a
ter
v
ue
en
9
ue
t
relian
4,
t
t
deux
le
emplacemenb
ts
repr?sen
et
a
est
p
sommets
ond?r?e
par
v
le
B
nom
F
bre
de
de
le
feux
tricolores
2.
situ?s
eut-il
sur
a
le
sans
tra
fois
jet.
v
B
Justier
D
onse.
A
C
dominos
G
E
2,
F
que,
1.
domino,
R?p
ondre
par
aux
et
quatreb
questions
ar?tes
suiv
graphe
an
ten
tes
ses
:
v
(a)
ues
Ce
tes
graphe
les
est-il
du
les
?
de
(b)
a
Ce
en
graphe
A
est-il
C
E
?
1.
(c)
l'ordre
Ce
graphe
puis
admet-il
degr?
une
de
ha?ne
sommets.
eul?rienne
Un
?
p
(d)
parcourir
Ce
graphe
v
admet-il
ues
un
emprun
plusieurs
eul?rien
la
?
a
2.
en
D?terminer,
?
en
v
justian
r?p
t,
le
On
nom
un
bre
de
utilisan
hromatique
les
de
hires
1,
graphe.
3,
tels
8
sur
Le
haque
graphe
guren
suiv
deux
an
hires
t
;
repr?sen
exemple
te
1
le
le
planb
d'uneb
ville.
3
Les1, 2 3
0 7 6 1 0 4 2
7 2 1 10 9 1 5
6 1 0 9 8 0 3
3 = 1 10 9 2 1 7 5
0 9 8 1 0 6 3
4 1 0 7 6 0 2
2 5 3 5 3 2 2
p
tes.
A
deux
B
soient
C
sommets
D
t
E
F
"se
G
les
L
ec
es
4
questions
et
deux
sommets
t
10
relian
es
et
que,
ar?te
ossible
sont
d'une
ind?p
sommets
endantes.
hemin
1.
C
Est-il
sept
p
ossible
E,
de
B,
trouv
les
er
le
un
?
tra
jet,
les
utilisan
deux
t
de
les
tous
liaisons
villes
existan
en
tes,
l'exis-
qui
de
part
a
d'une
d'un
des
tre
Une
B
ondan
D
le
villes.
bre
?
onden
de
G
3
F
relien
D,
le
C,
A
A,
sommet
sept
Les
tre,
tous.
graphe
11
Sur
group
d'amis
identiques
une
dans
"en
Alp
On
touchent",
repr?sen
pions
par
lorsque
graphe
sorte
les
oins
B,
les
D,
d'aligner
p
p
Est-il
deux
r?soudre
tre
probl?me
liaison
tence
hoisir
indique
passer.
ar?te
tre
T,
:
par
?
ils
le
euv
V
t
sept
Donner
villes
nom
et
de
y
hemins
revien
longueur
t
qui
en
t
passan
sommet
t
au
une
F.
fois
et
une
Un
seule
e
fois
organise
par
randonn?e
toutes
les
les
es.
autres
a
villes
t?
?
le
2.
On
sommets
note
C,
M
F,
la
N
matrice
lesquels
asso
p
en
au
graphe
de
Une
Les
en
sommets
deux
son
t
v
rang?s
l'existence
suiv
an
en
t
les
l'ordre
sommets.
alphab
F
?tique.
T
On
N
donne
Mn
46n6 6
M
4 10 8 16 6 5
10 6 11 6 11 10
8 11 8 11 11 63 M = 10 6 11 6 11 10
6 11 11 11 8 8
5 10 6 10 8 4
de
t
sorte
T
que
Justier
les
son
sommets
e
reli?s
e
par
du
un
nom
que
hemin
7.
n'on
passan
t
que
pas
t
la
de
m?me
D?terminer
hromatique
On
5.
note
en
exemple
6.
le
nom
l'ordre
bre
D?mon
et
hromatique
les
du
graphe.
du
(a)
C
Mon
haque
trer
ossible.
que
t
un
?
Donner
r?alisable.
bre
est
graphe
souhait
r?p
.
alors
(b)
Prop
t
oser
d?marc
un
la
du
(les
graphe
pris
p
b
ermettan
donne
t
de
seule
d?terminer
une
son
sommets
nom
passer
bre
