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 continues 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écbale (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é.
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.
Graphes Alex
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 in 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 des exemples concrets, 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.
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 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 faibel 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 Dr + Dn.