Problèmes de chemins
109
Nous commencerons dans ce chapitre à analyser des problèmes de ''chemins''.
Auparavant, il est indispensable de donner quelques éléments succincts du vocabulaire
des graphes.
6.2. ELEMENTS DE VOCABULAIRE DE LA THEORIE DES GRAPHES
6.2.1. Application
On peut associer à un graphe
une correspondance de dans lui-même. Pour
cela, on fait correspondre à l'ensemble des tels qu'il existe un arc d'extémité initiale
et d'extrémité terminale . On appellera
cette correspondance, qui est une
application multivoque.
S'il s'agit d'un 1-graphe (entre un sommet quelconque et un sommet quelconque, il
ne peut y avoir que 0 ou 1 arc) le graphe est complètement donné par et et on pourra
noter :
Sur le graphe de la figure 1, où l'on a :
}
,
,
,
,
,
{
=
F
E
D
C
B
A
X
on peut écrire :
}
,
{
=
)
(
C
B
A
}
,
{
=
)
(
E
D
B
}
,
{
=
)
(
C
A
C
etc.
mais ici le graphe n'est pas entièrement donné par (il y a deux arcs
).
6.2.2. Image réciproque
Si , sommet d'un graphe
est l'extrémité terminale d'au moins un arc de ,
on appelle image réciproque de le sous-ensemble des extrémités initiales des arcs qui y
aboutissent, c'est-à-dire :
)}
(
|
{
=
)
(
1)
(
y
x
y
x
Ainsi sur le graphe de la page 1, les images réciproques de
sont elles :
}
{
=
)
(
1
C
A
}
,
{
=
)
(
1
D
A
B
}
,
,
{
=
)
(
1
D
C
A
C
etc.
6.2.3. Graphe partiel - sous-graphe
Soit un graphe
; si l'on supprime certains arcs dans le graphe , on obtient un
graphe
avec
. est appelé graphe partiel de .