« Graphes et Applications » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 1 : | Ligne 1 : | ||
== Introduction == |
== Introduction == |
||
La définition de la théorie des graphes est largement [http://fr.wikipedia.org/wiki/Graphe_%28th%C3%A9orie_des_graphes%29 documentée]. |
La définition de la théorie des graphes est largement [http://fr.wikipedia.org/wiki/Graphe_%28th%C3%A9orie_des_graphes%29 documentée]. |
||
Ce qui suit touche aux [http://m3m.homedns.org/anim/Polyhedron.php polyèdres], aux [http://m3m.homedns.org/anim/ |
Ce qui suit touche aux [http://m3m.homedns.org/anim/Polyhedron.php polyèdres], aux [http://m3m.homedns.org/anim/GameOfLife.php structures GameOfLife], mais finalement et surtout à Alex. |
||
== Restrictions == |
== Restrictions == |
||
| Ligne 13 : | Ligne 13 : | ||
La relation du graphe peut être binaire (2 états: vrai ou faux) ou floue (états continues autorisés entre 0=faux et 1=vrai). |
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 ] |
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 |
Un graphe peut être ''orienté'' ou ''non-orienté''. Un graphe orienté peut avoir |
||
| Ligne 19 : | Ligne 19 : | ||
- une symmétrie ''forcée'' : (a,b) implique (b,a) |
- une symmétrie ''forcée'' : (a,b) implique (b,a) |
||
- une symmétrie ''interdite'' |
- une symmétrie ''interdite'' : (a.b) interdit (b,a) |
||
- une symmétrie ''libre'' |
- 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é. |
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. |
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.<br> |
|||
Dans la suite, seuls les graphes '''connexes''' sont considérés.<br> |
|||
== 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 [http://m3m.homedns.org/anim/Polyhedron.php polyèdres], et des [http://m3m.homedns.org/anim/GameOfLife.php structures GameOfLife], une représentation géométrique est autorisée et pratique.<br> |
|||
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<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 N / (2 x N!) .<br> |
|||
==== Graphes géométriques plans bidimensionnels cycliques<br> ==== |
|||
Tous les noeuds ont le même nombre de voisin. Les noeuds sont organisés cycliquement dans chaque dimension. <br> |
|||
Dans l'étude des [http://m3m.homedns.org/anim/GameOfLife.php structures GameOfLife], des réseaux carrés et hexagonaux sont proposé. La densité ...<br> |
|||
==== Graphes géométriques sphériques unidimmensionnels cycliques<br> ==== |
|||
Il y a au minimum 4 noeuds. Chaque graphe sphérique présenté dans l'étude des [http://m3m.homedns.org/anim/GameOfLife.php structures GameOfLife] provient d'un équivalent polyédrique.<br> |
|||
Cinq structures polyédriques... |
|||
Version du 30 décembre 2009 à 09:09
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 N / (2 x N!) .
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é ...
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...