Graphes et Applications
Introduction
La définition de la théorie des graphes est largement documentée.
Ce qui suit touche aux polyèdres, aux structures GameOfLife, mais finalement et surtout à Alex.
Restrictions
Un graphe peut être fini ou infini (selon qu'il contient un nombre de points finis ou infinis).
Dans la suite seul les graphes finis sont considérés.
La relation du graphe peut être binaire (2 états: vrai ou faux) ou floue (états de relation continus autorisés entre 0=faux et 1=vrai).
Dans la suite, seuls les graphes binaires sont considérés. [ Mais cela mérite discussion ]
Un graphe peut être orienté ou non-orienté. Un graphe orienté peut avoir
- une symmétrie forcée : (a,b) implique (b,a)
- une symmétrie interdite : (a,b) interdit (b,a)
- une symmétrie libre : (a,b) n'implique pas et n'interdit pas (b,a)
Un graphe à symmétrie forcée est équivalent à un graphe non-orienté.
Dans la suite seuls les graphes non-orientés sont considérés.
Un graphe peut être sécable ou non-sécable (connexe), Dans un graphe connexe, deux points quelconques sont reliés par au moins un chemin.
Dans la suite, seuls les graphes connexes sont considérés.
Densité d'un graphe
La densité est la probabilité d'existence d'un lien direct entre deux noeuds choisis au hasard
Support géométrique
Dans les cas des polyèdres, et des structures GameOfLife, une représentation géométrique est autorisée et pratique.
Dans le cas plus général d'Alex, il faut aussi admettre des graphes dont il est vain d'espérer une représentation géométrique utile.
Graphes géométriques unidimmensionnels cycliques
Il y a au minimum 3 noeuds. Chaque noeud a exactement 2 voisins. Le nombre de liens est égal au nombre de noeuds. La densité est 2/(N-1) , N étant le nombre de noeuds.
Graphes géométriques plans bidimensionnels cycliques
Tous les noeuds ont le même nombre de voisin. Les noeuds sont organisés cycliquement dans chacune des deux dimensions.
Dans l'étude des structures GameOfLife, des réseaux carrés et hexagonaux sont proposés.
La densité est facile à calculer. Pour un réseau carré de 25 noeuds, où chaque noeud possède 4 voisins, la densité est 4/24.
Graphes géométriques sphériques bidimmensionnels
Il y a au minimum 4 noeuds. Chaque graphe sphérique présenté dans l'étude des structures GameOfLife provient d'un équivalent polyédrique.
La surface est celle d'une sphère, donc un espace bi-dimensionnel extrait d'un espace tridimmensionnel.
Tous les noeuds sont à égale distance du centre la sphère (la notion de distance est liée à la représentation géométrique, pas au graphe lui-même).
Cinq structures polyédriques parfaites peuvent être définies, et des polyédriques imparfaites peuvent être générées à l'infini à partir des structures parfaites.
Dans une structure parfaite, le nombre de voisins est une constante (et le nombre de faces).
La densité des structures de base est évidente : 1 pour le tétraèdre, 0.8 pour l'octaèdre, 0.43... pour le cube, 0.45... pour l'icosaèdre et 0.16... pour le dodecaèdre.
Graphes géométriques tridimmensionnels cycliques
Tous les noeuds ont le même nombre de voisin. Les noeuds sont organisés cycliquement dans chacune des trois dimensions.
Les graphes sont équivalents aux définitions de réseaux cristallins.
Dans l'étude des structures GameOfLife, seul le réseau cubique est proposé.
La densité est facile à calculer. Pour un réseau cubique de 27 noeuds, où chaque noeud possède 6 voisins, la densité est 6/26.
Graphes sans support géométrique
Pour la suite, et en particulier pour les graphes liés à Alex, il devient vain d'imaginer une représentaion géométrique.
On peut cependant imaginer que les noeuds occupent de manière homogène une espace cyclique de dimension quelconque.
'Homogène' signifie qu'aucune région de l'espace n'est privilégiée en terme de densité.
'Cyclique' signifie qu'aucune région de l'espace n'est à considérer comme périphérique ou centrale.
Graphes Alex
Les graphes Alex sont conçus pour être utilisé dans l'initialisation statique des graphes utilisés dans Alex.
Après cette initialisation statique, les graphes sont susceptibles d'évoluer par création et destruction dynamique de liens, mais ceci est une autre histoire...
Graphe Alex-R
Un graphe Alex-R est un graphe fini, binaire, non-orienté, contenant des liens aléatoires (R pour random).
Il se caractérise par un nombre de points N et par une densité D, et il est noté Alex-R(N,D) .
Le nombre de liens est D x N x (N-1) / 2 . Pratiquement c'est un entier, donc la valeur arrondie de l'expression donnée.
Il pourrait ne pas être connexe, mais ne sont retenus ici que les graphes connexes. Si N et D ne sont pas très petits, la probabilité de construire au hasard un graphe Alex-R non connexe est négligeable.
Pour prendre un exemple concret, considérons un graphe Alex-R(100,0.1), c'est à dire contenant N noeuds et ayant une densité de 0.1. Ce graphe possède 495 liens. En moyenne chaque noeud possède 4.95 voisins.
Graphe Alex-H
Un graphe Alex-H est un graphe fini, binaire, non-orienté, contenant de manière hybride (H pour hybride):
- des liens aléatoires
- des liens nuageux
Un lien nuageux est un lien construit aléatoirement, mais avec une probabilité aggrandie pour des noeuds déjà enchainés.
Algorithmiquement, un lien nuageux est construit par triangulation, comme ceci:
- on cherche un noeud au hasard: a
- on cherche un lien au hasard (a,b)
- on cherche un lien succédant au hasard (b,c)
- si le lien (a,c) n'existe pas encore, il est créé
Les liens nuageux sont construits après les liens aléatoires.
Il est donc supposé que les paramètres N et D permettent cette construction, en d'autres termes que la densité n'est ni trop faible ni trop forte pour cette triangulation nuageuse.
Le graphe Alex-H est noté Alex-H(N,Dr,Dn) . Dr est la densité des liens aléatoires. Dn est la densité des liens nuageux. La densité du graphe est D = Dr + Dn.
Pour prendre des exemples concrets, considérons un graphe Alex-H(100,0.05,0.05), c'est à dire contenant N noeuds et ayant une densité de 0.1. La densité aléatoire est 0.05 et la densité nuageuse est 0.05. Ce graphe possède 495 liens. En moyenne chaque noeud possède 4.95 voisins. Cependant, ce graphe possède des propriétés de nébulosité: certains groupes de noeuds sont formés, avec une densité locale de liens plus élevée que dans l'ensemble du graphe, et plus élevée qu'attendue dans un graphe Alex-R.