Soit
un graphe orienté.
est composé d'un ensemble fini
de nœuds
et d'un ensemble fini
de liens
.
Un lien
est défini comme un couple d'identifiants distincts
.
Un nœud
est défini par un identifiant
et une liste ordonnée
de liens
de
, tel que
.
On dit qu'un lien
de
est résolu si et seulement si il existe
tel que l'identifiant de
.
On note degré d'un nœud
,
, le nombre de liens distincts de
.
On appelle degré résolu d'un nœud
,
, le nombre de liens distincts résolus de
.
On appelle accessibilité d'un nœud
,
, le nombre de liens
de
tel que
.
On dit que N est un nœud terminal si
.
On dit que N est un nœud orphelin si
.
On dit que
est une chaîne si
est un nœud et que pour tout
, il existe un lien résolu
dans
.
Dans ce cas, la longueur
de la chaîne
est
.
On défini simultanément deux opérateurs sur les chaînes :
- fst : l'opérateur
(de first en anglais) récupère le premier élement de la chaîne ; i.e.
.
- lst : l'opérateur
(de last en anglais) récupère le dernier élement de la chaîne ; i.e.
.
On dit que
est une sous-chaîne de
si il existe
tel que
.
On dit qu'une chaîne
est un cycle
si
.
Un cycle
est simple si pour tout
,
.
On dit qu'une chaîne
est sans boucle si aucune sous-chaîne
de
n'est un cycle.
On appelle distance orientée
entre deux nœuds
et
la valeur telle que :
![{\displaystyle d^{+}(N_{A},N_{B})=\min _{C\in {\mathcal {G}}}\{w(C)/\operatorname {fst} (C)=N_{A}\land \operatorname {lst} (C)=N_{B}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfb5c32826da97eb86e04375e14d9b94820ee411)
Par conséquent :
, pour tout ![{\displaystyle N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
, s'il n'existe aucune chaîne reliant
à ![{\displaystyle N_{B}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc141c4bf37d6a37464b3eabe8a30b2e1c9dbe29)
Attention :
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
entre deux nœuds
et
la valeur telle que :
![{\displaystyle d^{-}(N_{A},N_{B})=\min _{C\in {\mathcal {G}}}\{w(C)/\operatorname {lst} (C)=N_{A}\land \operatorname {fst} (C)=N_{B}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5228699021ee2c3e7c5b4038937c451c5558d4a8)
Par conséquent :
, pour tout ![{\displaystyle N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
, s'il n'existe aucune chaîne reliant
à ![{\displaystyle N_{B}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc141c4bf37d6a37464b3eabe8a30b2e1c9dbe29)
Attention :
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
entre deux nœuds
et
la valeur telle que :
![{\displaystyle d(N_{A},N_{B})=\min(d^{+}(N_{A},N_{B}),d^{-}(N_{A},N_{B}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d125807b1e67eacda15e839b3b684f6a773677ce)
On a alors :
, pour tout ![{\displaystyle N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
, s'il n'existe aucune chaîne reliant
à
, ou
à ![{\displaystyle N_{A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fa9233ef6a6a2c0576dbf65490ddb8307fde494)
, pour tout
(symétrie)
On dit de
qu'il est dans le voisinage orienté
de
, s'il existe une chaîne
telle que
et
.
On dit de
qu'il est dans le voisinage inversé
de
, s'il existe une chaîne
telle que
et
.
On dit de
qu'il est dans le voisinage complet, ou simplement voisinage
de
si
est soit dans
(voisinage orienté) ou dans
(voisinage inversé).
Un îlot orienté
est un sous-ensemble de nœud de
tel que :
- pour tout
et
de
,
appartient à
ou
appartient à
.
- soit
de
; s'il existe
dans
, tel que
appartient à
, alors
appartient à
.
- pour tout
de
, tel que
n'appartient pas à
, quelque soit
dans
,
n'appartient pas à
.
On en déduit que pour tout couple de nœuds
pris dans
, il existe une chaîne
telle que
et
ou alors
et
.
La décomposition en îlot orienté d'un graphe
est unique et est un recouvrement complet de
.
L'ensemble des îlots orientés
forme donc une partition de
.
Un îlot inversé
est un sous-ensemble de nœud de
tel que :
- pour tout
et
de
,
appartient à
ou
appartient à
.
- soit
de
; s'il existe
dans
, tel que
appartient à
, alors
appartient à
.
- pour tout
de
, tel que
n'appartient pas à
, quelque soit
dans
,
n'appartient pas à
.
On en déduit que pour tout couple de nœuds
pris dans
, il existe une chaîne
telle que
et
ou alors
et
.
La décomposition en îlot inversé d'un graphe
est unique et est un recouvrement complet de
.
L'ensemble des îlots inversés
forme donc une partition de
.
Un îlot complet, ou plus simplement îlot
est un sous-ensemble de nœud de
tel que :
- pour tout
et
de
,
appartient à
.
- soit
de
; s'il existe
dans
, tel que
appartient à
, alors
appartient à
.
- pour tout
de
, tel que
n'appartient pas à
, quelque soit
dans
,
n'appartient pas à
.
On en déduit que pour tout couple de nœuds
pris dans
, il existe une chaîne
telle que
et
ou alors
et
.
La décomposition en îlot complet d'un graphe
est unique et est un recouvrement complet de
.
L'ensemble des îlots complets
forme donc une partition de
.
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
pris dans un îlot orienté (respectivement inversé), au moins une des valeurs
(respectivement
) et
(respectivement
) 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
pris dans un îlot orienté,
et est un entier fini.
Le diamètre d'un îlot
(ou
, ou
) est par définition :
![{\displaystyle \Delta (W)=\max _{N_{A},N_{B}\in W}\{d(N_{A},N_{B})\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10fa8d8905932e12ed2db69e08a9c1f17264b69e)
![{\displaystyle \Delta ^{+}(W^{+})=\max _{N_{A},N_{B}\in W^{+}}\{d^{+}(N_{A},N_{B})\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f37ecb3dde289f99939dcdacfd32a667f9eb81a)
![{\displaystyle \Delta ^{-}(W^{-})=\max _{N_{A},N_{B}\in W^{-}}\{d^{-}(N_{A},N_{B})\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48e2aa7a2aa1e07c98552060309945b6ce53dbf1)
Le diamètre étendu d'un îlot
(ou
)
![{\displaystyle \Delta '^{+}(W^{+})=\max _{N_{A},N_{B}\in W^{+}}\{\min(d^{+}(N_{A},N_{B}),d^{+}(N_{B},N_{A}))\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97f20093503a3e170e818034509e7b88a2f1c553)
![{\displaystyle \Delta '^{-}(W^{-})=\max _{N_{A},N_{B}\in W^{-}}\{\min(d^{-}(N_{A},N_{B}),d^{-}(N_{B},N_{A}))\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99bf1832a19a50441e4b19bf6ac15cb3655bbfd9)
Comme
,
et
sont des ensembles finis, on a par construction
est nécessairement un entier fini
est nécessairement un entier fini
est nécessairement un entier fini
peut être infini
peut être infini
Le rayon d'un îlot
(ou
, ou
) est par définition :
![{\displaystyle r(W)=\min _{N\in W}\{\max _{N'\in W}(d(N,N'))\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/612fa4dfa5eec1ffac4c7ea1a2521f8bede9cfc8)
![{\displaystyle r^{+}(W^{+})=\min _{N\in W^{+}}\{\max _{N'\in W^{+}}\{d^{+}(N,N')\}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6a48d4e18d4e64b337bc39a74f6bf28d2510267)
![{\displaystyle r^{-}(W^{-})=\min _{N\in W^{-}}\{\max _{N'\in W^{-}}\{d^{-}(N,N')\}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c82d9f0ea7b9b3b19eff2fae5515890f1fe7e8f5)
Le rayon étendu d'un îlot
(ou
![{\displaystyle r'^{+}(W^{+})=\min _{N\in W^{+}}\{\max _{N'\in W^{+}}\{\min(d^{+}(N,N'),d^{+}(N',N))\}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c253041f8aa84af5a035b1288ce30a8aff4373a)
![{\displaystyle r'^{-}(W^{-})=\min _{N\in W^{-}}\{\max _{N'\in W^{-}}\{\min(d^{-}(N,N'),d^{-}(N',N))\}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f713e202812053fefe36b49b57ca6305be736ca)
Comme
,
et
sont des ensembles finis, on a par construction
est nécessairement un entier fini
est nécessairement un entier fini
est nécessairement un entier fini
peut être infini
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
(ou
, ou
est par définition :
![{\displaystyle \Lambda (W)=\{N\in W/\max _{N'\in W}\{d(N,N')\}=r(W)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b17177f5225dc99ea033679eb21a24bfec5b80a)
si ![{\displaystyle r^{+}(W^{+})=\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d07d440fe13e1dccc366dfd1cf6640653ef5a9e7)
sinon
si ![{\displaystyle r^{-}(W^{-})=\infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab8d21cc30ffe6661a5c783c460a0882a9481b3e)
sinon
L'ensemble étendu des nœuds médians d'un îlot
(ou
![{\displaystyle \Lambda '^{+}(W^{+})=\{N\in W^{+}/\max _{N'\in W^{+}}\{\min(d^{+}(N,N'),d^{+}(N',N))\}=r'^{+}(W^{+})\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5046a14b524fe45ff96363c84152c9065ffa9ec)
![{\displaystyle \Lambda '^{-}(W^{-})=\{N\in W^{-}/\max _{N'\in W^{-}}\{\min(d^{-}(N,N'),d^{-}(N',N))\}=r'^{-}(W^{-})\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48f8c3fea4d786a86c591db6b2a9a9ca49ed02f3)
Comme
,
et
sont des ensembles finis, on a par construction
est un ensemble fini non vide
est un ensemble fini non vide
est un ensemble fini non vide
est un ensemble fini potentiellement vide
est un ensemble fini potentiellement vide
Il est interessant de définir le nombre d'îlots d'un graphe, pour déterminer les zones non connexes.
Ce sont des informations très interessantes pour déterminer la connexité d'un îlot, car on obtient de bonnes estimation du nombre de lien à traverser pour passer d'un nœud à l'autre dans un graphe.