Utilisateur:Xmlizer/Théorie des graphes

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Théorie des graphes

[modifier] Définition

[modifier] 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 (Jd,Jf).
Un nœud N est défini par un identifiant JN et une liste ordonnée EN de liens L = (Jd,Jf) de V_{\mathcal G}, tel que Jd = JN.

[modifier] Lien résolu

On dit qu'un lien L = (JN,Jf) de EN est résolu si et seulement si il existe Nf tel que l'identifiant de Nf = Jf.

[modifier] Degré

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

[modifier] Accessibilité

On appelle accessibilité d'un nœud N = (JN,EN), α(N), le nombre de liens L = (JN,Jf) de V_{\mathcal G} tel que Jf = JN.

[modifier] Nœud terminal

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

[modifier] Nœud orphelin

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

[modifier] Chaîne et sous-chaîne

On dit que C = (N_0, N_1, \dots, N_p) est une chaîne si N0 est un nœud et que pour tout 0 \le 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 \le a \le b \le p tel que C' = (N_a, \dots, N_b).

[modifier] Cycle et boucle

On dit qu'une chaîne C est un cycle Ω 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 \le k < l < p, N_k \ne N_l.
On dit qu'une chaîne C est sans boucle si aucune sous-chaîne C' de C n'est un cycle.

[modifier] Distance

[modifier] Distance orientée

On appelle distance orientée d + entre deux nœuds NA et NB 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) = \infin, s'il n'existe aucune chaîne reliant NA à NB

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

[modifier] Distance inversée

On appelle distance inversée d entre deux nœuds NA et NB 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) = \infin, s'il n'existe aucune chaîne reliant NA à NB

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

[modifier] Distance complète

On appelle distance complète, ou simplement distance d entre deux nœuds NA et NB la valeur telle que :

d(NA,NB) = min(d + (NA,NB),d (NA,NB))

On a alors :

  1. d(N,N) = 0, pour tout N
  2. d(N_A, N_B) = \infin, s'il n'existe aucune chaîne reliant NA à NB, ou NB à NA
  3. d(NA,NB) = d(NB,NA), pour tout NA,NB (symétrie)

[modifier] Voisinage

[modifier] Voisinage orienté

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

[modifier] Voisinage inversé

On dit de N_g = (J_{N_g}, E_{N_g}) qu'il est dans le voisinage inversé V (N) de N = (JN,EN), s'il existe une chaîne C telle que fst(C) = Ng et lst(C) = N.

[modifier] Voisinage complet

On dit de N = (JN,EN) qu'il est dans le voisinage complet, ou simplement voisinage V(N0) de N_0 = (J_{N_0}, E_{N_0}) si N est soit dans V + (N) (voisinage orienté) ou dans V (N) (voisinage inversé).

[modifier] Îlot

[modifier] Îlot orienté

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

  1. pour tout Na et Nb de W + , Na appartient à V + (Nb) ou Nb appartient à V + (Na).
  2. soit Nx de \mathcal G ; s'il existe N dans W + , tel que Nx appartient à V + (N), alors Nx appartient à W + .
  3. pour tout Nx de \mathcal G, tel que Nx n'appartient pas à W + , quelque soit N dans W + , Nx n'appartient pas à V + (N).

On en déduit que pour tout couple de nœuds (NA,NB) 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}.

[modifier] Îlot inversé

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

  1. pour tout Na et Nb de W , Na appartient à V (Nb) ou Nb appartient à V (Na).
  2. soit Nx de \mathcal G ; s'il existe N dans W , tel que Nx appartient à V (N), alors Nx appartient à W .
  3. pour tout Nx de \mathcal G, tel que Nx n'appartient pas à W , quelque soit N dans W , Nx n'appartient pas à V (N).

On en déduit que pour tout couple de nœuds (NA,NB) 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}.

[modifier] Î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 Na et Nb de W, Na appartient à V(Nb).
  2. soit Nx de \mathcal G ; s'il existe N dans W, tel que Nx appartient à V(N), alors Nx appartient à W.
  3. pour tout Nx de \mathcal G, tel que Nx n'appartient pas à W, quelque soit N dans W, N n'appartient pas à V(Nx).

On en déduit que pour tout couple de nœuds (NA,NB) 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) = {Wi} forme donc une partition de U_{\mathcal G}.

[modifier] 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.

[modifier] 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 (NA,NB) pris dans un îlot orienté (respectivement inversé), au moins une des valeurs d + (NA,NB) (respectivement d (NA,NB)) et d + (NB,NA) (respectivement d (NB,NA)) 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 (NA,NB) pris dans un îlot orienté, d(NA,NB) = d(NB,NA) et est un entier fini.

[modifier] Diamètre d'un îlot

Le diamètre d'un îlot Δ(W) (ou Δ + (W + ), ou Δ (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 Δ' + (W + ) (ou Δ' (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

  • Δ(W) est nécessairement un entier fini
  • Δ' + (W + ) est nécessairement un entier fini
  • Δ' (W ) est nécessairement un entier fini
  • Δ + (W + ) peut être infini
  • Δ' (W ) peut être infini

[modifier] 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.

[modifier] Nœuds médians d'un îlot

L'ensemble des nœuds médians d'un îlot Λ(W) (ou Λ + (W + ), ou Λ (W ) est par définition :

\Lambda(W) = \{N \in W / \max_{N' \in W}\{d(N, N')\} = r(W)\}
\Lambda^+(W^+) = \empty si r^+(W^+) = \infin
\Lambda^+(W^+) = \{N \in W^+ / \max_{N' \in W^+}\{d^+(N, N')\} = r^+(W^+)\} sinon
\Lambda^-(W^-) = \empty si r^-(W^-) = \infin
\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 + ) (ou Λ;' (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

  • Λ(W) est un ensemble fini non vide
  • Λ' + (W + ) est un ensemble fini non vide
  • Λ' (W ) est un ensemble fini non vide
  • Λ + (W + ) est un ensemble fini potentiellement vide
  • Λ (W ) est un ensemble fini potentiellement vide

[modifier] Anomalies

[modifier] Calculs intéressants

[modifier] Îlots

[modifier] Nombres d'îlots

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

[modifier] 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.