Modélisation d’un réseau par la prétopologie

Introduction Habituellement, on parle de modèle mathématique quand on met en oeuvre des outils et théories mathématiques permettant de simuler le comportement du modèle réel. Cependant, il ne faut pas contraindre le réel à subir une axiomatique qui ne lui convient pas, d’o`u l’idée de développer une topologie mieux adaptée aux problèmes rencontrés [7]. L’historique de cette idée débute dans les années 20 quand Fréchet visait à construire une topologie ayant moins d’axiomes [33].

Puis Appert reprit ces travaux dans les années 30, suivi par Monteiro dans les années 40 puis par Ky-Fan. Dans les années 60, Cech décrivait dans son ouvrage des structures topologiques privées de l’axiome idempotence [20]. C’est au début des années 70 que des chercheurs fran¸cais (Marcel Brissaud, Gérard Duru, Jean-Paul Auray, Michel Lamure […] pour ne citer qu’eux) débuteront leurs travaux sur la prétopologie et comment trouver une formalisation du concept de proximité, afin de résoudre des problématiques difficiles liées à la contrainte de l’outil mathématique utilisé, ici la topologie.

Dans le cadre de mes travaux, la prétopologie est à mon sens l’outil permettant d’aller plus loin que la théorie des graphes habituellement utilisée pour représenter les réseaux. Son cadre général, ainsi que sa capacité à représenter la dynamique d’un système en font l’outil adéquat pour la modélisation des réseaux complexes. Dans cette partie, des définitions sont données, ainsi qu’une définition générale d’un réseau. Nous proposerons ensuite des choix de structures de données adaptées dans le but de limiter la complexité des opérations afin de pouvoir construire des simulations exploitables, que nous appliquons sur plusieurs problématiques.

La théorie de la prétopologie

Cette section énonce les définitions de la prétopologie utilisées pour les travaux de recherche présentés dans ce mémoire, l’ouvrage de référence [7] contenant une présentation exhaustive de la prétopologie. 

Espace prétopologique

Soit E un ensemble non vide, et soit P(E) l’ensemble des parties de E. Définition 2.1 Soit une application a : P(E) → P(E) appelée adhérence et définie comme suit : ∀A, A ⊆ E l’adhérence de A, a(A) ⊆ E est telle que : – a(∅) = ∅ (P1) – A ⊆ a(A) (P2) L’adhérence est associée au processus de dilatation. De plus, a(.) peut ˆetre appliquée à A selon une séquence : A ⊆ a(A) ⊆ a 2 (A) ⊆ … . Cela signifie que l’on peut suivre le processus pas à pas, ce qui n’est pas possible avec la topologie, qui conserve la propriété d’idempotence (a(A) = a 2 (A)) [17].

Grâce à l’adhérence, on peut directement modéliser la notion de proximité. En terme de complexité, le coˆut d’une adhérence sera étudié lors de la partie concernant les structures de données utilisées en prétopologie. Définition 2.2 Soit une application i : P(E) → P(E) appelée intérieur et définie comme suit : ∀A, A ⊆ E l’intérieur de A, i(A) ⊆ E est telle que : – i(A) = [a(Ac )]c (P1) – i(A) ⊆ A (P2) avec Ac le complémentaire de A soit E − A.

L’intérieur est quant à lui associé au processus d’érosion. Notons que la propriété 1 de l’intérieur amenant la dualité n’est pas toujours vraie. Il est possible de définir une application intérieur indépendamment de l’adhérence. On appelle espace prétopologique le triplet (E, i, a) dont les applications i et a sont définies précédemment. 

Fermés et Ouverts, Fermeture et Ouverture

Le processus de dilatation généré par l’adhérence s’arrˆete à un instant donné et n’évolue plus. Dans ce cas, on a a k+1(A) = a k (A). On nomme A comme étant un sous ensemble fermé. De la mˆeme manière, l’évolution de l’intérieur va cesser, ce qui nous donne i k+1(A) = i k (A). Cette fois, on nomme A comme étant un sous ensemble ouvert. Respectivement, on utilise les notations F(A) pour la fermeture de A et O(A) pour l’ouverture de A. La complexité d’un fermé, si on prend l’adhérence comme opération de base, se fait au pire en O(n × coˆut d’une adhérence).