« Graphes et Applications » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 43 : | Ligne 43 : | ||
==== Graphes géométriques unidimmensionnels cycliques<br> ==== |
==== Graphes géométriques unidimmensionnels cycliques<br> ==== |
||
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 |
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.<br> |
||
==== Graphes géométriques plans bidimensionnels cycliques<br> ==== |
==== Graphes géométriques plans bidimensionnels cycliques<br> ==== |
||
Version du 30 décembre 2009 à 09:29
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 chaque dimension.
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 unidimmensionnels cycliques
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.
Cinq structures polyédriques...