Utilisateur:Xmlizer/Théorie des graphes

Théorie des graphes

Définition

Graphe

Soit ${\mathcal {G}}$ un graphe orienté.
${\mathcal {G}}$ est composé d'un ensemble fini $U_{\mathcal {G}}$ de nœuds $N$ et d'un ensemble fini $V_{\mathcal {G}}$ de liens $L$.
Un lien $L$ est défini comme un couple d'identifiants distincts $(J_{d},J_{f})$.
Un nœud $N$ est défini par un identifiant $J_{N}$ et une liste ordonnée $E_{N}$ de liens $L=(J_{d},J_{f})$ de $V_{\mathcal {G}}$, tel que $J_{d}=J_{N}$.

Lien résolu

On dit qu'un lien $L=(J_{N},J_{f})$ de $E_{N}$ est résolu si et seulement si il existe $N_{f}$ tel que l'identifiant de $N_{f}=J_{f}$.

Degré

On note degré d'un nœud $N$, $\delta (N)$, le nombre de liens distincts de $E(N)$.
On appelle degré résolu d'un nœud $N$, $\rho (N)$, le nombre de liens distincts résolus de $E(N)$.

Accessibilité

On appelle accessibilité d'un nœud $N=(J_{N},E_{N})$, $\alpha (N)$, le nombre de liens $L=(J_{d},J_{f})$ de $V_{\mathcal {G}}$ tel que $J_{f}=J_{N}$.

Nœud terminal

On dit que N est un nœud terminal si $\rho (N)=0$.

Nœud orphelin

On dit que N est un nœud orphelin si $\alpha (N)=0$.

Chaîne et sous-chaîne

On dit que $C=(N_{0},N_{1},\dots ,N_{p})$ est une chaîne si $N_{0}$ est un nœud et que pour tout $0\leq k<p$, il existe un lien résolu $L=(J_{N_{k}},J_{N_{k+1}})$ dans $E_{N_{k}}$.
Dans ce cas, la longueur $w$ de la chaîne $C$ est $w(C)=p$.
On défini simultanément deux opérateurs sur les chaînes :

• fst : l'opérateur $\operatorname {fst}$ (de first en anglais) récupère le premier élement de la chaîne ; i.e. $\operatorname {fst} (C)=N_{0}$.
• lst : l'opérateur $\operatorname {lst}$ (de last en anglais) récupère le dernier élement de la chaîne ; i.e. $\operatorname {lst} (C)=N_{p}$.

On dit que $C'$ est une sous-chaîne de $C=(N_{0},N_{1},\dots ,N_{p})$ si il existe $0\leq a\leq b\leq p$ tel que $C'=(N_{a},\dots ,N_{b})$.

Cycle et boucle

On dit qu'une chaîne $C$ est un cycle $\Omega$ si $\operatorname {fst} (C)=\operatorname {lst} (C)$.
Un cycle $\Omega =(N_{0},N_{1},\dots ,N_{p-1},N_{0})$ est simple si pour tout $0\leq k<l<p$, $N_{k}\neq N_{l}$.
On dit qu'une chaîne $C$ est sans boucle si aucune sous-chaîne $C'$ de $C$ n'est un cycle.

Distance

Distance orientée

On appelle distance orientée $d^{+}$ entre deux nœuds $N_{A}$ et $N_{B}$ la valeur telle que :

$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 :

1. $d^{+}(N,N)=0$, pour tout $N$
2. $d^{+}(N_{A},N_{B})=\infty$, s'il n'existe aucune chaîne reliant $N_{A}$ à $N_{B}$

Attention : $d^{+}$ n'est pas une distance au sens mathématique, car elle ne vérifie pas l'axiome de symétrie.

Distance inversée

On appelle distance inversée $d^{-}$ entre deux nœuds $N_{A}$ et $N_{B}$ la valeur telle que :

$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 :

1. $d^{-}(N,N)=0$, pour tout $N$
2. $d^{-}(N_{A},N_{B})=\infty$, s'il n'existe aucune chaîne reliant $N_{A}$ à $N_{B}$

Attention : $d^{-}$ n'est pas une distance au sens mathématique, car elle ne vérifie pas l'axiome de symétrie.

Distance complète

On appelle distance complète, ou simplement distance $d$ entre deux nœuds $N_{A}$ et $N_{B}$ la valeur telle que :

$d(N_{A},N_{B})=\min(d^{+}(N_{A},N_{B}),d^{-}(N_{A},N_{B}))$

On a alors :

1. $d(N,N)=0$, pour tout $N$
2. $d(N_{A},N_{B})=\infty$, s'il n'existe aucune chaîne reliant $N_{A}$ à $N_{B}$, ou $N_{B}$ à $N_{A}$
3. $d(N_{A},N_{B})=d(N_{B},N_{A})$, pour tout $N_{A},N_{B}$ (symétrie)

Voisinage

Voisinage orienté

On dit de $N_{d}=(J_{N_{d}},E_{N_{d}})$ qu'il est dans le voisinage orienté $V^{+}(N)$ de $N=(J_{N},E_{N})$, s'il existe une chaîne $C$ telle que $fst(C)=N$ et $lst(C)=N_{d}$.

Voisinage inversé

On dit de $N_{g}=(J_{N_{g}},E_{N_{g}})$ qu'il est dans le voisinage inversé $V^{-}(N)$ de $N=(J_{N},E_{N})$, s'il existe une chaîne $C$ telle que $fst(C)=N_{g}$ et $lst(C)=N$.

Voisinage complet

On dit de $N=(J_{N},E_{N})$ qu'il est dans le voisinage complet, ou simplement voisinage $V(N_{0})$ de $N_{0}=(J_{N_{0}},E_{N_{0}})$ si $N$ est soit dans $V^{+}(N)$ (voisinage orienté) ou dans $V^{-}(N)$ (voisinage inversé).

Îlot

Îlot orienté

Un îlot orienté $W^{+}$ est un sous-ensemble de nœud de $U_{\mathcal {G}}$ tel que :

1. pour tout $N_{a}$ et $N_{b}$ de $W^{+}$, $N_{a}$ appartient à $V^{+}(N_{b})$ ou $N_{b}$ appartient à $V^{+}(N_{a})$.
2. soit $N_{x}$ de ${\mathcal {G}}$ ; s'il existe $N$ dans $W^{+}$, tel que $N_{x}$ appartient à $V^{+}(N)$, alors $N_{x}$ appartient à $W^{+}$.
3. pour tout $N_{x}$ de ${\mathcal {G}}$, tel que $N_{x}$ n'appartient pas à $W^{+}$, quelque soit $N$ dans $W^{+}$, $N_{x}$ n'appartient pas à $V^{+}(N)$.

On en déduit que pour tout couple de nœuds $(N_{A},N_{B})$ pris dans $W^{+}$, il existe une chaîne $C$ telle que $\operatorname {fst} (C)=N_{A}$ et $\operatorname {lst} (C)=N_{B}$ ou alors $\operatorname {fst} (C)=N_{B}$ et $\operatorname {lst} (C)=N_{A}$.
La décomposition en îlot orienté d'un graphe ${\mathcal {G}}$ est unique et est un recouvrement complet de $U_{\mathcal {G}}$.
L'ensemble des îlots orientés $E(W^{+})=\{W_{i}^{+}\}$ forme donc une partition de $U_{\mathcal {G}}$.

Îlot inversé

Un îlot inversé $W^{-}$ est un sous-ensemble de nœud de $U_{\mathcal {G}}$ tel que :

1. pour tout $N_{a}$ et $N_{b}$ de $W^{-}$, $N_{a}$ appartient à $V^{-}(N_{b})$ ou $N_{b}$ appartient à $V^{-}(N_{a})$.
2. soit $N_{x}$ de ${\mathcal {G}}$ ; s'il existe $N$ dans $W^{-}$, tel que $N_{x}$ appartient à $V^{-}(N)$, alors $N_{x}$ appartient à $W^{-}$.
3. pour tout $N_{x}$ de ${\mathcal {G}}$, tel que $N_{x}$ n'appartient pas à $W^{-}$, quelque soit $N$ dans $W^{-}$, $N_{x}$ n'appartient pas à $V^{-}(N)$.

On en déduit que pour tout couple de nœuds $(N_{A},N_{B})$ pris dans $W^{-}$, il existe une chaîne $C$ telle que $\operatorname {fst} (C)=N_{B}$ et $\operatorname {lst} (C)=N_{A}$ ou alors $\operatorname {fst} (C)=N_{B}$ et $\operatorname {lst} (C)=N_{A}$.
La décomposition en îlot inversé d'un graphe ${\mathcal {G}}$ est unique et est un recouvrement complet de $U_{\mathcal {G}}$.
L'ensemble des îlots inversés $E(W^{-})=\{W_{i}^{-}\}$ forme donc une partition de $U_{\mathcal {G}}$.

Îlot complet

Un îlot complet, ou plus simplement îlot $W$ est un sous-ensemble de nœud de $U_{\mathcal {G}}$ tel que :

1. pour tout $N_{a}$ et $N_{b}$ de $W$, $N_{a}$ appartient à $V(N_{b})$.
2. soit $N_{x}$ de ${\mathcal {G}}$ ; s'il existe $N$ dans $W$, tel que $N_{x}$ appartient à $V(N)$, alors $N_{x}$ appartient à $W$.
3. pour tout $N_{x}$ de ${\mathcal {G}}$, tel que $N_{x}$ n'appartient pas à $W$, quelque soit $N$ dans $W$, $N$ n'appartient pas à $V(N_{x})$.

On en déduit que pour tout couple de nœuds $(N_{A},N_{B})$ pris dans $W$, il existe une chaîne $C$ telle que $\operatorname {fst} (C)=N_{A}$ et $\operatorname {lst} (C)=N_{B}$ ou alors $\operatorname {fst} (C)=N_{B}$ et $\operatorname {lst} (C)=N_{A}$.
La décomposition en îlot complet d'un graphe ${\mathcal {G}}$ est unique et est un recouvrement complet de $U_{\mathcal {G}}$.
L'ensemble des îlots complets $E(W)=\{W_{i}\}$ forme donc une partition de $U_{\mathcal {G}}$.

Lemme des îlots

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.

Distance sur un î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})$ pris dans un îlot orienté (respectivement inversé), au moins une des valeurs $d^{+}(N_{A},N_{B})$ (respectivement $d^{-}(N_{A},N_{B})$) et $d^{+}(N_{B},N_{A})$ (respectivement $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})$ pris dans un îlot orienté, $d(N_{A},N_{B})=d(N_{B},N_{A})$ et est un entier fini.

Diamètre d'un îlot

Le diamètre d'un îlot $\Delta (W)$ (ou $\Delta ^{+}(W^{+})$, ou $\Delta ^{-}(W^{-})$) est par définition :

$\Delta (W)=\max _{N_{A},N_{B}\in W}\{d(N_{A},N_{B})\}$

$\Delta ^{+}(W^{+})=\max _{N_{A},N_{B}\in W^{+}}\{d^{+}(N_{A},N_{B})\}$

$\Delta ^{-}(W^{-})=\max _{N_{A},N_{B}\in W^{-}}\{d^{-}(N_{A},N_{B})\}$

Le diamètre étendu d'un îlot $\Delta '^{+}(W^{+})$ (ou $\Delta '^{-}(W^{-})$)

$\Delta '^{+}(W^{+})=\max _{N_{A},N_{B}\in W^{+}}\{\min(d^{+}(N_{A},N_{B}),d^{+}(N_{B},N_{A}))\}$

$\Delta '^{-}(W^{-})=\max _{N_{A},N_{B}\in W^{-}}\{\min(d^{-}(N_{A},N_{B}),d^{-}(N_{B},N_{A}))\}$

Comme $W$, $W^{+}$ et $W^{-}$ sont des ensembles finis, on a par construction

• $\Delta (W)$ est nécessairement un entier fini
• $\Delta '^{+}(W^{+})$ est nécessairement un entier fini
• $\Delta '^{-}(W^{-})$ est nécessairement un entier fini
• $\Delta ^{+}(W^{+})$ peut être infini
• $\Delta '^{-}(W^{-})$ peut être infini

Rayon d'un îlot

Le rayon d'un îlot $r(W)$ (ou $r^{+}(W^{+})$, ou $r^{-}(W^{-})$) est par définition :

$r(W)=\min _{N\in W}\{\max _{N'\in W}(d(N,N'))\}$

$r^{+}(W^{+})=\min _{N\in W^{+}}\{\max _{N'\in W^{+}}\{d^{+}(N,N')\}\}$

$r^{-}(W^{-})=\min _{N\in W^{-}}\{\max _{N'\in W^{-}}\{d^{-}(N,N')\}\}$

Le rayon étendu d'un îlot $r'^{+}(W^{+})$ (ou $r'^{-}(W^{-})$

$r'^{+}(W^{+})=\min _{N\in W^{+}}\{\max _{N'\in W^{+}}\{\min(d^{+}(N,N'),d^{+}(N',N))\}\}$

$r'^{-}(W^{-})=\min _{N\in W^{-}}\{\max _{N'\in W^{-}}\{\min(d^{-}(N,N'),d^{-}(N',N))\}\}$

Comme $W$, $W^{+}$ et $W^{-}$ sont des ensembles finis, on a par construction

• $r(W)$ est nécessairement un entier fini
• $r'^{+}(W^{+})$ est nécessairement un entier fini
• $r'^{-}(W^{-})$ est nécessairement un entier fini
• $r^{+}(W^{+})$ peut être infini
• $r^{-}(W^{-})$ peut être infini

Attention : Le rayon d'un îlot a très peu de rapport avec le diamètre d'un îlot.

Nœuds médians d'un îlot

L'ensemble des nœuds médians d'un îlot $\Lambda (W)$ (ou $\Lambda ^{+}(W^{+})$, ou $\Lambda ^{-}(W^{-})$ est par définition :

$\Lambda (W)=\{N\in W/\max _{N'\in W}\{d(N,N')\}=r(W)\}$

$\Lambda ^{+}(W^{+})=\emptyset$ si $r^{+}(W^{+})=\infty$

$\Lambda ^{+}(W^{+})=\{N\in W^{+}/\max _{N'\in W^{+}}\{d^{+}(N,N')\}=r^{+}(W^{+})\}$ sinon

$\Lambda ^{-}(W^{-})=\emptyset$ si $r^{-}(W^{-})=\infty$

$\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 $\Lambda '^{+}(W^{+})$ (ou $\Lambda ;'^{-}(W^{-})$

$\Lambda '^{+}(W^{+})=\{N\in W^{+}/\max _{N'\in W^{+}}\{\min(d^{+}(N,N'),d^{+}(N',N))\}=r'^{+}(W^{+})\}$

$\Lambda '^{-}(W^{-})=\{N\in W^{-}/\max _{N'\in W^{-}}\{\min(d^{-}(N,N'),d^{-}(N',N))\}=r'^{-}(W^{-})\}$

Comme $W$, $W^{+}$ et $W^{-}$ sont des ensembles finis, on a par construction

• $\Lambda (W)$ est un ensemble fini non vide
• $\Lambda '^{+}(W^{+})$ est un ensemble fini non vide
• $\Lambda '^{-}(W^{-})$ est un ensemble fini non vide
• $\Lambda ^{+}(W^{+})$ est un ensemble fini potentiellement vide
• $\Lambda ^{-}(W^{-})$ est un ensemble fini potentiellement vide

Calculs intéressants

Îlots

Nombres d'îlots

Il est interessant de définir le nombre d'îlots d'un graphe, pour déterminer les zones non connexes.

Diamètre, rayon et nœuds médians des îlots

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.