Soit
G
{\displaystyle {\mathcal {G}}}
un graphe orienté .
G
{\displaystyle {\mathcal {G}}}
est composé d'un ensemble fini
U
G
{\displaystyle U_{\mathcal {G}}}
de nœuds
N
{\displaystyle N}
et d'un ensemble fini
V
G
{\displaystyle V_{\mathcal {G}}}
de liens
L
{\displaystyle L}
.
Un lien
L
{\displaystyle L}
est défini comme un couple d'identifiants distincts
(
J
d
,
J
f
)
{\displaystyle (J_{d},J_{f})}
.
Un nœud
N
{\displaystyle N}
est défini par un identifiant
J
N
{\displaystyle J_{N}}
et une liste ordonnée
E
N
{\displaystyle E_{N}}
de liens
L
=
(
J
d
,
J
f
)
{\displaystyle L=(J_{d},J_{f})}
de
V
G
{\displaystyle V_{\mathcal {G}}}
, tel que
J
d
=
J
N
{\displaystyle J_{d}=J_{N}}
.
On dit qu'un lien
L
=
(
J
N
,
J
f
)
{\displaystyle L=(J_{N},J_{f})}
de
E
N
{\displaystyle E_{N}}
est résolu si et seulement si il existe
N
f
{\displaystyle N_{f}}
tel que l'identifiant de
N
f
=
J
f
{\displaystyle N_{f}=J_{f}}
.
On note degré d'un nœud
N
{\displaystyle N}
,
δ
(
N
)
{\displaystyle \delta (N)}
, le nombre de liens distincts de
E
(
N
)
{\displaystyle E(N)}
.
On appelle degré résolu d'un nœud
N
{\displaystyle N}
,
ρ
(
N
)
{\displaystyle \rho (N)}
, le nombre de liens distincts résolus de
E
(
N
)
{\displaystyle E(N)}
.
On appelle accessibilité d'un nœud
N
=
(
J
N
,
E
N
)
{\displaystyle N=(J_{N},E_{N})}
,
α
(
N
)
{\displaystyle \alpha (N)}
, le nombre de liens
L
=
(
J
d
,
J
f
)
{\displaystyle L=(J_{d},J_{f})}
de
V
G
{\displaystyle V_{\mathcal {G}}}
tel que
J
f
=
J
N
{\displaystyle J_{f}=J_{N}}
.
On dit que N est un nœud terminal si
ρ
(
N
)
=
0
{\displaystyle \rho (N)=0}
.
On dit que N est un nœud orphelin si
α
(
N
)
=
0
{\displaystyle \alpha (N)=0}
.
On dit que
C
=
(
N
0
,
N
1
,
…
,
N
p
)
{\displaystyle C=(N_{0},N_{1},\dots ,N_{p})}
est une chaîne si
N
0
{\displaystyle N_{0}}
est un nœud et que pour tout
0
≤
k
<
p
{\displaystyle 0\leq k<p}
, il existe un lien résolu
L
=
(
J
N
k
,
J
N
k
+
1
)
{\displaystyle L=(J_{N_{k}},J_{N_{k+1}})}
dans
E
N
k
{\displaystyle E_{N_{k}}}
.
Dans ce cas, la longueur
w
{\displaystyle w}
de la chaîne
C
{\displaystyle C}
est
w
(
C
)
=
p
{\displaystyle w(C)=p}
.
On défini simultanément deux opérateurs sur les chaînes :
fst : l'opérateur
fst
{\displaystyle \operatorname {fst} }
(de first en anglais) récupère le premier élement de la chaîne ; i.e.
fst
(
C
)
=
N
0
{\displaystyle \operatorname {fst} (C)=N_{0}}
.
lst : l'opérateur
lst
{\displaystyle \operatorname {lst} }
(de last en anglais) récupère le dernier élement de la chaîne ; i.e.
lst
(
C
)
=
N
p
{\displaystyle \operatorname {lst} (C)=N_{p}}
.
On dit que
C
′
{\displaystyle C'}
est une sous-chaîne de
C
=
(
N
0
,
N
1
,
…
,
N
p
)
{\displaystyle C=(N_{0},N_{1},\dots ,N_{p})}
si il existe
0
≤
a
≤
b
≤
p
{\displaystyle 0\leq a\leq b\leq p}
tel que
C
′
=
(
N
a
,
…
,
N
b
)
{\displaystyle C'=(N_{a},\dots ,N_{b})}
.
On dit qu'une chaîne
C
{\displaystyle C}
est un cycle
Ω
{\displaystyle \Omega }
si
fst
(
C
)
=
lst
(
C
)
{\displaystyle \operatorname {fst} (C)=\operatorname {lst} (C)}
.
Un cycle
Ω
=
(
N
0
,
N
1
,
…
,
N
p
−
1
,
N
0
)
{\displaystyle \Omega =(N_{0},N_{1},\dots ,N_{p-1},N_{0})}
est simple si pour tout
0
≤
k
<
l
<
p
{\displaystyle 0\leq k<l<p}
,
N
k
≠
N
l
{\displaystyle N_{k}\neq N_{l}}
.
On dit qu'une chaîne
C
{\displaystyle C}
est sans boucle si aucune sous-chaîne
C
′
{\displaystyle C'}
de
C
{\displaystyle C}
n'est un cycle .
On appelle distance orientée
d
+
{\displaystyle d^{+}}
entre deux nœuds
N
A
{\displaystyle N_{A}}
et
N
B
{\displaystyle N_{B}}
la valeur telle que :
d
+
(
N
A
,
N
B
)
=
min
C
∈
G
{
w
(
C
)
/
fst
(
C
)
=
N
A
∧
lst
(
C
)
=
N
B
}
{\displaystyle d^{+}(N_{A},N_{B})=\min _{C\in {\mathcal {G}}}\{w(C)/\operatorname {fst} (C)=N_{A}\land \operatorname {lst} (C)=N_{B}\}}
Par conséquent :
d
+
(
N
,
N
)
=
0
{\displaystyle d^{+}(N,N)=0}
, pour tout
N
{\displaystyle N}
d
+
(
N
A
,
N
B
)
=
∞
{\displaystyle d^{+}(N_{A},N_{B})=\infty }
, s'il n'existe aucune chaîne reliant
N
A
{\displaystyle N_{A}}
à
N
B
{\displaystyle N_{B}}
Attention :
d
+
{\displaystyle d^{+}}
n'est pas une distance au sens mathématique, car elle ne vérifie pas l'axiome de symétrie.
On appelle distance inversée
d
−
{\displaystyle d^{-}}
entre deux nœuds
N
A
{\displaystyle N_{A}}
et
N
B
{\displaystyle N_{B}}
la valeur telle que :
d
−
(
N
A
,
N
B
)
=
min
C
∈
G
{
w
(
C
)
/
lst
(
C
)
=
N
A
∧
fst
(
C
)
=
N
B
}
{\displaystyle d^{-}(N_{A},N_{B})=\min _{C\in {\mathcal {G}}}\{w(C)/\operatorname {lst} (C)=N_{A}\land \operatorname {fst} (C)=N_{B}\}}
Par conséquent :
d
−
(
N
,
N
)
=
0
{\displaystyle d^{-}(N,N)=0}
, pour tout
N
{\displaystyle N}
d
−
(
N
A
,
N
B
)
=
∞
{\displaystyle d^{-}(N_{A},N_{B})=\infty }
, s'il n'existe aucune chaîne reliant
N
A
{\displaystyle N_{A}}
à
N
B
{\displaystyle N_{B}}
Attention :
d
−
{\displaystyle d^{-}}
n'est pas une distance au sens mathématique, car elle ne vérifie pas l'axiome de symétrie.
On appelle distance complète , ou simplement distance
d
{\displaystyle d}
entre deux nœuds
N
A
{\displaystyle N_{A}}
et
N
B
{\displaystyle N_{B}}
la valeur telle que :
d
(
N
A
,
N
B
)
=
min
(
d
+
(
N
A
,
N
B
)
,
d
−
(
N
A
,
N
B
)
)
{\displaystyle d(N_{A},N_{B})=\min(d^{+}(N_{A},N_{B}),d^{-}(N_{A},N_{B}))}
On a alors :
d
(
N
,
N
)
=
0
{\displaystyle d(N,N)=0}
, pour tout
N
{\displaystyle N}
d
(
N
A
,
N
B
)
=
∞
{\displaystyle d(N_{A},N_{B})=\infty }
, s'il n'existe aucune chaîne reliant
N
A
{\displaystyle N_{A}}
à
N
B
{\displaystyle N_{B}}
, ou
N
B
{\displaystyle N_{B}}
à
N
A
{\displaystyle N_{A}}
d
(
N
A
,
N
B
)
=
d
(
N
B
,
N
A
)
{\displaystyle d(N_{A},N_{B})=d(N_{B},N_{A})}
, pour tout
N
A
,
N
B
{\displaystyle N_{A},N_{B}}
(symétrie)
On dit de
N
d
=
(
J
N
d
,
E
N
d
)
{\displaystyle N_{d}=(J_{N_{d}},E_{N_{d}})}
qu'il est dans le voisinage orienté
V
+
(
N
)
{\displaystyle V^{+}(N)}
de
N
=
(
J
N
,
E
N
)
{\displaystyle N=(J_{N},E_{N})}
, s'il existe une chaîne
C
{\displaystyle C}
telle que
f
s
t
(
C
)
=
N
{\displaystyle fst(C)=N}
et
l
s
t
(
C
)
=
N
d
{\displaystyle lst(C)=N_{d}}
.
On dit de
N
g
=
(
J
N
g
,
E
N
g
)
{\displaystyle N_{g}=(J_{N_{g}},E_{N_{g}})}
qu'il est dans le voisinage inversé
V
−
(
N
)
{\displaystyle V^{-}(N)}
de
N
=
(
J
N
,
E
N
)
{\displaystyle N=(J_{N},E_{N})}
, s'il existe une chaîne
C
{\displaystyle C}
telle que
f
s
t
(
C
)
=
N
g
{\displaystyle fst(C)=N_{g}}
et
l
s
t
(
C
)
=
N
{\displaystyle lst(C)=N}
.
On dit de
N
=
(
J
N
,
E
N
)
{\displaystyle N=(J_{N},E_{N})}
qu'il est dans le voisinage complet , ou simplement voisinage
V
(
N
0
)
{\displaystyle V(N_{0})}
de
N
0
=
(
J
N
0
,
E
N
0
)
{\displaystyle N_{0}=(J_{N_{0}},E_{N_{0}})}
si
N
{\displaystyle N}
est soit dans
V
+
(
N
)
{\displaystyle V^{+}(N)}
(voisinage orienté ) ou dans
V
−
(
N
)
{\displaystyle V^{-}(N)}
(voisinage inversé ).
Un îlot orienté
W
+
{\displaystyle W^{+}}
est un sous-ensemble de nœud de
U
G
{\displaystyle U_{\mathcal {G}}}
tel que :
pour tout
N
a
{\displaystyle N_{a}}
et
N
b
{\displaystyle N_{b}}
de
W
+
{\displaystyle W^{+}}
,
N
a
{\displaystyle N_{a}}
appartient à
V
+
(
N
b
)
{\displaystyle V^{+}(N_{b})}
ou
N
b
{\displaystyle N_{b}}
appartient à
V
+
(
N
a
)
{\displaystyle V^{+}(N_{a})}
.
soit
N
x
{\displaystyle N_{x}}
de
G
{\displaystyle {\mathcal {G}}}
; s'il existe
N
{\displaystyle N}
dans
W
+
{\displaystyle W^{+}}
, tel que
N
x
{\displaystyle N_{x}}
appartient à
V
+
(
N
)
{\displaystyle V^{+}(N)}
, alors
N
x
{\displaystyle N_{x}}
appartient à
W
+
{\displaystyle W^{+}}
.
pour tout
N
x
{\displaystyle N_{x}}
de
G
{\displaystyle {\mathcal {G}}}
, tel que
N
x
{\displaystyle N_{x}}
n'appartient pas à
W
+
{\displaystyle W^{+}}
, quelque soit
N
{\displaystyle N}
dans
W
+
{\displaystyle W^{+}}
,
N
x
{\displaystyle N_{x}}
n'appartient pas à
V
+
(
N
)
{\displaystyle V^{+}(N)}
.
On en déduit que pour tout couple de nœuds
(
N
A
,
N
B
)
{\displaystyle (N_{A},N_{B})}
pris dans
W
+
{\displaystyle W^{+}}
, il existe une chaîne
C
{\displaystyle C}
telle que
fst
(
C
)
=
N
A
{\displaystyle \operatorname {fst} (C)=N_{A}}
et
lst
(
C
)
=
N
B
{\displaystyle \operatorname {lst} (C)=N_{B}}
ou alors
fst
(
C
)
=
N
B
{\displaystyle \operatorname {fst} (C)=N_{B}}
et
lst
(
C
)
=
N
A
{\displaystyle \operatorname {lst} (C)=N_{A}}
.
La décomposition en îlot orienté d'un graphe
G
{\displaystyle {\mathcal {G}}}
est unique et est un recouvrement complet de
U
G
{\displaystyle U_{\mathcal {G}}}
.
L'ensemble des îlots orientés
E
(
W
+
)
=
{
W
i
+
}
{\displaystyle E(W^{+})=\{W_{i}^{+}\}}
forme donc une partition de
U
G
{\displaystyle U_{\mathcal {G}}}
.
Un îlot inversé
W
−
{\displaystyle W^{-}}
est un sous-ensemble de nœud de
U
G
{\displaystyle U_{\mathcal {G}}}
tel que :
pour tout
N
a
{\displaystyle N_{a}}
et
N
b
{\displaystyle N_{b}}
de
W
−
{\displaystyle W^{-}}
,
N
a
{\displaystyle N_{a}}
appartient à
V
−
(
N
b
)
{\displaystyle V^{-}(N_{b})}
ou
N
b
{\displaystyle N_{b}}
appartient à
V
−
(
N
a
)
{\displaystyle V^{-}(N_{a})}
.
soit
N
x
{\displaystyle N_{x}}
de
G
{\displaystyle {\mathcal {G}}}
; s'il existe
N
{\displaystyle N}
dans
W
−
{\displaystyle W^{-}}
, tel que
N
x
{\displaystyle N_{x}}
appartient à
V
−
(
N
)
{\displaystyle V^{-}(N)}
, alors
N
x
{\displaystyle N_{x}}
appartient à
W
−
{\displaystyle W^{-}}
.
pour tout
N
x
{\displaystyle N_{x}}
de
G
{\displaystyle {\mathcal {G}}}
, tel que
N
x
{\displaystyle N_{x}}
n'appartient pas à
W
−
{\displaystyle W^{-}}
, quelque soit
N
{\displaystyle N}
dans
W
−
{\displaystyle W^{-}}
,
N
x
{\displaystyle N_{x}}
n'appartient pas à
V
−
(
N
)
{\displaystyle V^{-}(N)}
.
On en déduit que pour tout couple de nœuds
(
N
A
,
N
B
)
{\displaystyle (N_{A},N_{B})}
pris dans
W
−
{\displaystyle W^{-}}
, il existe une chaîne
C
{\displaystyle C}
telle que
fst
(
C
)
=
N
B
{\displaystyle \operatorname {fst} (C)=N_{B}}
et
lst
(
C
)
=
N
A
{\displaystyle \operatorname {lst} (C)=N_{A}}
ou alors
fst
(
C
)
=
N
B
{\displaystyle \operatorname {fst} (C)=N_{B}}
et
lst
(
C
)
=
N
A
{\displaystyle \operatorname {lst} (C)=N_{A}}
.
La décomposition en îlot inversé d'un graphe
G
{\displaystyle {\mathcal {G}}}
est unique et est un recouvrement complet de
U
G
{\displaystyle U_{\mathcal {G}}}
.
L'ensemble des îlots inversés
E
(
W
−
)
=
{
W
i
−
}
{\displaystyle E(W^{-})=\{W_{i}^{-}\}}
forme donc une partition de
U
G
{\displaystyle U_{\mathcal {G}}}
.
Un îlot complet , ou plus simplement îlot
W
{\displaystyle W}
est un sous-ensemble de nœud de
U
G
{\displaystyle U_{\mathcal {G}}}
tel que :
pour tout
N
a
{\displaystyle N_{a}}
et
N
b
{\displaystyle N_{b}}
de
W
{\displaystyle W}
,
N
a
{\displaystyle N_{a}}
appartient à
V
(
N
b
)
{\displaystyle V(N_{b})}
.
soit
N
x
{\displaystyle N_{x}}
de
G
{\displaystyle {\mathcal {G}}}
; s'il existe
N
{\displaystyle N}
dans
W
{\displaystyle W}
, tel que
N
x
{\displaystyle N_{x}}
appartient à
V
(
N
)
{\displaystyle V(N)}
, alors
N
x
{\displaystyle N_{x}}
appartient à
W
{\displaystyle W}
.
pour tout
N
x
{\displaystyle N_{x}}
de
G
{\displaystyle {\mathcal {G}}}
, tel que
N
x
{\displaystyle N_{x}}
n'appartient pas à
W
{\displaystyle W}
, quelque soit
N
{\displaystyle N}
dans
W
{\displaystyle W}
,
N
{\displaystyle N}
n'appartient pas à
V
(
N
x
)
{\displaystyle V(N_{x})}
.
On en déduit que pour tout couple de nœuds
(
N
A
,
N
B
)
{\displaystyle (N_{A},N_{B})}
pris dans
W
{\displaystyle W}
, il existe une chaîne
C
{\displaystyle C}
telle que
fst
(
C
)
=
N
A
{\displaystyle \operatorname {fst} (C)=N_{A}}
et
lst
(
C
)
=
N
B
{\displaystyle \operatorname {lst} (C)=N_{B}}
ou alors
fst
(
C
)
=
N
B
{\displaystyle \operatorname {fst} (C)=N_{B}}
et
lst
(
C
)
=
N
A
{\displaystyle \operatorname {lst} (C)=N_{A}}
.
La décomposition en îlot complet d'un graphe
G
{\displaystyle {\mathcal {G}}}
est unique et est un recouvrement complet de
U
G
{\displaystyle U_{\mathcal {G}}}
.
L'ensemble des îlots complets
E
(
W
)
=
{
W
i
}
{\displaystyle E(W)=\{W_{i}\}}
forme donc une partition de
U
G
{\displaystyle U_{\mathcal {G}}}
.
Lemme des îlots :
Les décomposition en îlot orienté , décomposition en îlot inversé
et décomposition en îlot complet forment une unique décomposition que
l'on nommera simplement décomposition en îlot .
Comme entre chaque nœud d'un îlot orienté (respectivement inversé ), il existe par définition au moins une chaîne les reliants dans un sens, on en deduit que pour tout couple de nœud
(
N
A
,
N
B
)
{\displaystyle (N_{A},N_{B})}
pris dans un îlot orienté (respectivement inversé ), au moins une des valeurs
d
+
(
N
A
,
N
B
)
{\displaystyle d^{+}(N_{A},N_{B})}
(respectivement
d
−
(
N
A
,
N
B
)
{\displaystyle d^{-}(N_{A},N_{B})}
) et
d
+
(
N
B
,
N
A
)
{\displaystyle d^{+}(N_{B},N_{A})}
(respectivement
d
−
(
N
B
,
N
A
)
{\displaystyle d^{-}(N_{B},N_{A})}
) est un entier fini.
Comme entre chaque nœud d'un îlot orienté , il existe une chaîne les reliants, on en deduit que pour tout couple de nœud
(
N
A
,
N
B
)
{\displaystyle (N_{A},N_{B})}
pris dans un îlot orienté ,
d
(
N
A
,
N
B
)
=
d
(
N
B
,
N
A
)
{\displaystyle d(N_{A},N_{B})=d(N_{B},N_{A})}
et est un entier fini.
Le diamètre d'un îlot
Δ
(
W
)
{\displaystyle \Delta (W)}
(ou
Δ
+
(
W
+
)
{\displaystyle \Delta ^{+}(W^{+})}
, ou
Δ
−
(
W
−
)
{\displaystyle \Delta ^{-}(W^{-})}
) est par définition :
Δ
(
W
)
=
max
N
A
,
N
B
∈
W
{
d
(
N
A
,
N
B
)
}
{\displaystyle \Delta (W)=\max _{N_{A},N_{B}\in W}\{d(N_{A},N_{B})\}}
Δ
+
(
W
+
)
=
max
N
A
,
N
B
∈
W
+
{
d
+
(
N
A
,
N
B
)
}
{\displaystyle \Delta ^{+}(W^{+})=\max _{N_{A},N_{B}\in W^{+}}\{d^{+}(N_{A},N_{B})\}}
Δ
−
(
W
−
)
=
max
N
A
,
N
B
∈
W
−
{
d
−
(
N
A
,
N
B
)
}
{\displaystyle \Delta ^{-}(W^{-})=\max _{N_{A},N_{B}\in W^{-}}\{d^{-}(N_{A},N_{B})\}}
Le diamètre étendu d'un îlot
Δ
′
+
(
W
+
)
{\displaystyle \Delta '^{+}(W^{+})}
(ou
Δ
′
−
(
W
−
)
{\displaystyle \Delta '^{-}(W^{-})}
)
Δ
′
+
(
W
+
)
=
max
N
A
,
N
B
∈
W
+
{
min
(
d
+
(
N
A
,
N
B
)
,
d
+
(
N
B
,
N
A
)
)
}
{\displaystyle \Delta '^{+}(W^{+})=\max _{N_{A},N_{B}\in W^{+}}\{\min(d^{+}(N_{A},N_{B}),d^{+}(N_{B},N_{A}))\}}
Δ
′
−
(
W
−
)
=
max
N
A
,
N
B
∈
W
−
{
min
(
d
−
(
N
A
,
N
B
)
,
d
−
(
N
B
,
N
A
)
)
}
{\displaystyle \Delta '^{-}(W^{-})=\max _{N_{A},N_{B}\in W^{-}}\{\min(d^{-}(N_{A},N_{B}),d^{-}(N_{B},N_{A}))\}}
Comme
W
{\displaystyle W}
,
W
+
{\displaystyle W^{+}}
et
W
−
{\displaystyle W^{-}}
sont des ensembles finis, on a par construction
Δ
(
W
)
{\displaystyle \Delta (W)}
est nécessairement un entier fini
Δ
′
+
(
W
+
)
{\displaystyle \Delta '^{+}(W^{+})}
est nécessairement un entier fini
Δ
′
−
(
W
−
)
{\displaystyle \Delta '^{-}(W^{-})}
est nécessairement un entier fini
Δ
+
(
W
+
)
{\displaystyle \Delta ^{+}(W^{+})}
peut être infini
Δ
′
−
(
W
−
)
{\displaystyle \Delta '^{-}(W^{-})}
peut être infini
Le rayon d'un îlot
r
(
W
)
{\displaystyle r(W)}
(ou
r
+
(
W
+
)
{\displaystyle r^{+}(W^{+})}
, ou
r
−
(
W
−
)
{\displaystyle r^{-}(W^{-})}
) est par définition :
r
(
W
)
=
min
N
∈
W
{
max
N
′
∈
W
(
d
(
N
,
N
′
)
)
}
{\displaystyle r(W)=\min _{N\in W}\{\max _{N'\in W}(d(N,N'))\}}
r
+
(
W
+
)
=
min
N
∈
W
+
{
max
N
′
∈
W
+
{
d
+
(
N
,
N
′
)
}
}
{\displaystyle r^{+}(W^{+})=\min _{N\in W^{+}}\{\max _{N'\in W^{+}}\{d^{+}(N,N')\}\}}
r
−
(
W
−
)
=
min
N
∈
W
−
{
max
N
′
∈
W
−
{
d
−
(
N
,
N
′
)
}
}
{\displaystyle r^{-}(W^{-})=\min _{N\in W^{-}}\{\max _{N'\in W^{-}}\{d^{-}(N,N')\}\}}
Le rayon étendu d'un îlot
r
′
+
(
W
+
)
{\displaystyle r'^{+}(W^{+})}
(ou
r
′
−
(
W
−
)
{\displaystyle r'^{-}(W^{-})}
r
′
+
(
W
+
)
=
min
N
∈
W
+
{
max
N
′
∈
W
+
{
min
(
d
+
(
N
,
N
′
)
,
d
+
(
N
′
,
N
)
)
}
}
{\displaystyle r'^{+}(W^{+})=\min _{N\in W^{+}}\{\max _{N'\in W^{+}}\{\min(d^{+}(N,N'),d^{+}(N',N))\}\}}
r
′
−
(
W
−
)
=
min
N
∈
W
−
{
max
N
′
∈
W
−
{
min
(
d
−
(
N
,
N
′
)
,
d
−
(
N
′
,
N
)
)
}
}
{\displaystyle r'^{-}(W^{-})=\min _{N\in W^{-}}\{\max _{N'\in W^{-}}\{\min(d^{-}(N,N'),d^{-}(N',N))\}\}}
Comme
W
{\displaystyle W}
,
W
+
{\displaystyle W^{+}}
et
W
−
{\displaystyle W^{-}}
sont des ensembles finis, on a par construction
r
(
W
)
{\displaystyle r(W)}
est nécessairement un entier fini
r
′
+
(
W
+
)
{\displaystyle r'^{+}(W^{+})}
est nécessairement un entier fini
r
′
−
(
W
−
)
{\displaystyle r'^{-}(W^{-})}
est nécessairement un entier fini
r
+
(
W
+
)
{\displaystyle r^{+}(W^{+})}
peut être infini
r
−
(
W
−
)
{\displaystyle r^{-}(W^{-})}
peut être infini
Attention : Le rayon d'un îlot a très peu de rapport avec le diamètre d'un îlot .
L'ensemble des nœuds médians d'un îlot
Λ
(
W
)
{\displaystyle \Lambda (W)}
(ou
Λ
+
(
W
+
)
{\displaystyle \Lambda ^{+}(W^{+})}
, ou
Λ
−
(
W
−
)
{\displaystyle \Lambda ^{-}(W^{-})}
est par définition :
Λ
(
W
)
=
{
N
∈
W
/
max
N
′
∈
W
{
d
(
N
,
N
′
)
}
=
r
(
W
)
}
{\displaystyle \Lambda (W)=\{N\in W/\max _{N'\in W}\{d(N,N')\}=r(W)\}}
Λ
+
(
W
+
)
=
∅
{\displaystyle \Lambda ^{+}(W^{+})=\emptyset }
si
r
+
(
W
+
)
=
∞
{\displaystyle r^{+}(W^{+})=\infty }
Λ
+
(
W
+
)
=
{
N
∈
W
+
/
max
N
′
∈
W
+
{
d
+
(
N
,
N
′
)
}
=
r
+
(
W
+
)
}
{\displaystyle \Lambda ^{+}(W^{+})=\{N\in W^{+}/\max _{N'\in W^{+}}\{d^{+}(N,N')\}=r^{+}(W^{+})\}}
sinon
Λ
−
(
W
−
)
=
∅
{\displaystyle \Lambda ^{-}(W^{-})=\emptyset }
si
r
−
(
W
−
)
=
∞
{\displaystyle r^{-}(W^{-})=\infty }
Λ
−
(
W
−
)
=
{
N
∈
W
−
/
max
N
′
∈
W
−
{
d
−
(
N
,
N
′
)
}
=
r
−
(
W
−
)
}
{\displaystyle \Lambda ^{-}(W^{-})=\{N\in W^{-}/\max _{N'\in W^{-}}\{d^{-}(N,N')\}=r^{-}(W^{-})\}}
sinon
L'ensemble étendu des nœuds médians d'un îlot
Λ
′
+
(
W
+
)
{\displaystyle \Lambda '^{+}(W^{+})}
(ou
Λ
;
′
−
(
W
−
)
{\displaystyle \Lambda ;'^{-}(W^{-})}
Λ
′
+
(
W
+
)
=
{
N
∈
W
+
/
max
N
′
∈
W
+
{
min
(
d
+
(
N
,
N
′
)
,
d
+
(
N
′
,
N
)
)
}
=
r
′
+
(
W
+
)
}
{\displaystyle \Lambda '^{+}(W^{+})=\{N\in W^{+}/\max _{N'\in W^{+}}\{\min(d^{+}(N,N'),d^{+}(N',N))\}=r'^{+}(W^{+})\}}
Λ
′
−
(
W
−
)
=
{
N
∈
W
−
/
max
N
′
∈
W
−
{
min
(
d
−
(
N
,
N
′
)
,
d
−
(
N
′
,
N
)
)
}
=
r
′
−
(
W
−
)
}
{\displaystyle \Lambda '^{-}(W^{-})=\{N\in W^{-}/\max _{N'\in W^{-}}\{\min(d^{-}(N,N'),d^{-}(N',N))\}=r'^{-}(W^{-})\}}
Comme
W
{\displaystyle W}
,
W
+
{\displaystyle W^{+}}
et
W
−
{\displaystyle W^{-}}
sont des ensembles finis, on a par construction
Λ
(
W
)
{\displaystyle \Lambda (W)}
est un ensemble fini non vide
Λ
′
+
(
W
+
)
{\displaystyle \Lambda '^{+}(W^{+})}
est un ensemble fini non vide
Λ
′
−
(
W
−
)
{\displaystyle \Lambda '^{-}(W^{-})}
est un ensemble fini non vide
Λ
+
(
W
+
)
{\displaystyle \Lambda ^{+}(W^{+})}
est un ensemble fini potentiellement vide
Λ
−
(
W
−
)
{\displaystyle \Lambda ^{-}(W^{-})}
est un ensemble fini potentiellement vide