2.6. Graphes
Un graphe est un ensemble de couples. Notons gr la classe des graphes:
gr R ⇔ (Set R ∧ ∀x∈R, Fnc x ∧
Dom x = V2).
Pour tout symbole liant Q et tout graphe G, la
formule Qx∈G, A(x0, x1)
qui lie la variable z = (z0, z1)
sur une structure binaire A admissible sur G, peut se
voir comme liant 2 variables z0, z1
sur A(z0, z1), et donc
se noter par un couple de variables: Q(x,y)∈G, A(x,y).
Le transposé d'un couple est t(x,y) = (y,x)
Celui d'un graphe R est l'image de la transposition dessus:
tR = {(y,x)|(x,y)
∈ R}.
On définit le domaine et l'image d'un graphe
comme les images respectives de π0 et π1 dessus:
Dom R = {x|(x,y) ∈ R}
Im R = {y|(x,y) ∈ R} = Dom tR
Notations de curryfication
Les graphes s'expriment sous formes curryfiées comme foncteurs R⃗
et R⃖:
∀x, R⃗(x) = {y
| (z,y)∈R ∧ z=x}.
∀y, R⃖(y) = {x | (x,z)∈R ∧
z=y} = tR⃗ (y).
∀x,y,
y ∈ R⃗ (x) ⇔ (x,y)
∈ R ⇔ x ∈ R⃖
(y)
∀x, x ∈ Dom R ⇔ R⃗
(x) ≠ ∅
Dom R ⊂ E ⇒ Im R = ⋃x∈E R⃗(x) ∧
∀y, R⃖(y) = {x∈E | (x,y) ∈ R}
Ils peuvent aussi apparaitre comme fonctions
R⃗E =
(E∋x ↦ R⃗(x))
R⃖F = (F∋y ↦
R⃖(y))
(R⃗) = R⃗Dom R
(R⃖) = R⃖Im R.
Graphes fonctionnels
Le graphe d'une fonction f se définit par
Gr f = {(x,f(x)) | x ∈ Dom f}
∀x,y, (x,y) ∈ Gr f ⇔ (x ∈ Dom f ∧ y =
f(x))
Dom f = Dom Gr f
Im f = Im Gr f
Pour toute fonction f et tout graphe R,
| Gr f
⊂ R |
⇔ ∀x∈Dom f, f(x) ∈ R⃗(x) |
R ⊂ Gr f
|
⇔ (Dom R ⊂ Dom f ∧ ∀(x,y)∈R,
y = f(x)) |
R = Gr f
|
⇔ (Dom R ⊂ Dom f ∧ ∀x∈Dom f,
R⃗(x) = {f(x)} ) |
Un graphe R est dit fonctionnel si c'est le graphe d'une fonction. Cette condition
peut s'écrire de 2 manières équivalentes
∀x∈ Dom R, !:
R⃗(x)
∀x,y∈R, x0 = y0 ⇒
x1 = y1.
C'est alors le graphe d'une unique fonction ℩R⃗ = ((Dom R)
∋ x ↦ ℩(R⃗(x))).
Pour tout ensemble E on notera 𝛿E = Gr IdE.
Partitions indexées
Deux ensembles E et F sont dits disjoints
quand E∩F = ∅, ce qui équivaut à ∀x∈E, x∉F.
Les ensembles d'une famille (Ai)i
∈ I sont dits deux à deux disjoints si ∀i≠j∈I,
Ai∩Aj = ∅
Pour tout graphe R avec Im R ⊂ F,
(R⃖(y))y∈F
est une famille d'ensembles deux à deux disjoints si et seulement si R est fonctionnel :
(∀y≠z∈F, ¬∃x∈R⃖(y),
x ∈ R⃖(z)) ⇔
(∀(x,y)∈R, ∀z∈F, xRz ⇒ y = z)
Pour toute fonction f et tout y on définit la fibre de y par f
commef•(y) = {x∈Dom f | f(x)
= y} = (Gr⃖ f)(y)
Quand f : E → F cela définit
une famille f•F = (f•(y))y∈F de parties de E deux à deux disjointes :
∀y,z∈F, f•(y) ∩ f•(z)
≠ ∅ ⇒ ∃x∈ f•(y) ∩ f•(z),
y = f(x) = z
⋃y∈F f•(y) = E
Im f = {y∈F | f•(y) ≠ ∅}.
Une partition indexée d'un ensemble E est une
famille de parties de E non vides, deux à deux disjointes et
dont l'union est E.
Autrement dit c'est une famille de la forme f• =
f•Im f pour toute function f de domaine E.
Somme ou union disjointe
Le symbole liant ∐ de somme d'une famille d'ensembles
(Ei)I∈I
done un graphe ∐i∈I Ei défini par
∐
i∈I
Ei = ⋃
i∈I {(i,x) | x∈Ei}
∀i,x, (i,x) ∈ ∐
i∈I
Ei ⇔ (i∈I ∧ x∈Ei)
(∀(i,x)∈∐
i∈I Ei,
A(i,x)) ⇔ (∀i∈I,
∀x∈Ei, A(i,x))
(∀i∈I, Ei ⊂ E′i)
⇔ ∐i∈I Ei ⊂
∐i∈I E′i
E0⊔…⊔En−1 =
∐i∈Vn Ei
Ce symbole sert d'inverse à la curryfication : R =
∐i∈I Ei
⇔ (Dom R ⊂ I ∧ ∀i∈I,
R⃗(i) = Ei).
On l'appelle aussi union disjointe comme la famille de copies {(i,x) |
x∈Ei} de chaque Ei est 2 à 2
disjointe, la function de R vers I étant donnée par π0.
Images directe et inverse par un graphe
La restriction d'un graphe R à un ensemble A se définit par
R|A =
{(x,y)∈R | x∈A} = ∐x∈A
R⃗(x)
L'image directe d'un ensemble A par un graphe R
est
R⋆(
A) = Im
R|A =
⋃
x∈A R⃗(
x) = {
y |(
x,
y)∈
R∧
x∈
A} ⊂ Im
R.
Dom
R ⊂
A ⇔
R|A =
R
⇒
R⋆(
A) = Im
R
R⋆(⋃
i ∈ I
Ai) = ⋃
i ∈ I
R⋆(Ai)
R⋆(⋂
i ∈ I
Ai) ⊂ ⋂
i ∈ I
R⋆(Ai)
A ⊂
B ⇒
R⋆(
A) ⊂
R⋆(
B)
De même, l'image inverse ou préimage d'un ensemble B par un graphe R
est
R⋆(B) = tR⋆(B) =
⋃y∈B R⃖(y)
= {x | (x,y)∈R∧ y ∈ B} ⊂ Dom R.
Image directe et préimage par une fonction
L'image directe d'une partie A ⊂ Dom f par une fonction f,
notée f[A] ou f⋆(A), est
f[A] = (Gr f)⋆(A)
= {f(x) | x∈A} ⊂ Im f
Pour tous f : E → F et B ⊂ F,
la préimage ou image inverse de B par f, notée
f⋆(B), se définit par
f⋆(B) =
(Gr f)⋆(B) = {x∈E | f(x) ∈ B} = ⋃
y∈B
f•(y)
f•(y) = f⋆({y})
f⋆(∁
F B) = ∁
Ef⋆(
B)
Pour toute famille (Bi)i ∈ I
de parties de F, f⋆(⋂i∈I
Bi) = ⋂i∈I
f⋆(Bi), où les
intersections sont respectivement interprétées comme parties
de F et E.
Other languages:
EN : 2.6.
Graphs