Graphes et premier nombre de Ramsey
Un article de Wikipedia.
(→Nombre de Ramsey) |
(→Ressources) |
||
| Ligne 175 : | Ligne 175 : | ||
== Ressources == | == Ressources == | ||
* Description de l'algorithme permettant de générer l'ensemble des permutations pour ''n'' donné : [http://web.ew.usna.edu/~wdj/book/node156.html 'An algorithm to list all the permutations'] | * Description de l'algorithme permettant de générer l'ensemble des permutations pour ''n'' donné : [http://web.ew.usna.edu/~wdj/book/node156.html 'An algorithm to list all the permutations'] | ||
| - | + | * Nombres de Ramsey : [[http://mathworld.wolfram.com/RamseyNumber.html 'Ramsey Number']] | |
[[Category:Logiciel]] | [[Category:Logiciel]] | ||
[[Category:Pascal]] | [[Category:Pascal]] | ||
[[Category:Palm]] | [[Category:Palm]] | ||
Version du 22 mars 2008 à 12:04
Sommaire |
Graphes et premier nombre de Ramsey
But
Déterminer les graphes équivalents ayant au plus 6 sommets et utiliser ces graphes pour vérifier le premier nombre de Ramsey R(3,3).
Introduction
Un graphe est constitué d'un nombre n de sommets parfois reliés entre eux par des arrêtes.
Deux graphes sont considérés ici comme équivalents si :
- une permutation des sommets d'un graphe équivaut à l'autre
- pour un graphe chaque arrête est éliminée et chaque absence d'arrête est remplacée par une arrête et qu'il existe une permutation des sommets du graphe qui équivaut à l'autre
Nombre de Ramsey
Le nombre de Ramsey R(n,k) est le nombre minimum de sommets nécessaires pour qu'un graphe contenant un nombre arbitraire d'arrêtes comporte soit n sommets tous reliés entre eux soit k sommets tous non reliés entre eux.
Une autre formulation est le nombre R(n,k) de personnes qu'il faut inviter pour que n personnes se connaissent toutes entre elles ou que k personnes ne se connaissent pas entre elles.
Certains nombres de Ramsey sont connus, entre autres :
| n | k | R(n,k) |
|---|---|---|
| 3 | 3 | 6 |
| 4 | 4 | 18 |
Résultats
Pour déterminer l'équivalence d'un graphe de n sommets, il faut disposer de la liste complète des permutations pour n éléments donnés.
L'algorithme utilisé est celui décrit dans les ressources.
Il consiste à partir de toutes les permutations de n = 2,
| 1 | 2 |
| 2 | 1 |
de déterminer toutes les permutations pour n = 3 en triplant chaque ligne du cas n = 2
| 1 | 2 |
| 1 | 2 |
| 1 | 2 |
| 2 | 1 |
| 2 | 1 |
| 2 | 1 |
et en insérant le chiffre 3 dans chaque ligne en commençant par la dernière position jusqu'à la première et une fois la première position atteinte, recommencer depuis la première jusqu'à la dernière :
| 1 | 2 | 3 |
| 1 | 3 | 2 |
| 3 | 1 | 2 |
| 3 | 2 | 1 |
| 2 | 3 | 1 |
| 2 | 1 | 3 |
Pour n = 4 il faut quadrupler chaque ligne du cas n = 3 et insérer le chiffre 4 de la même manière que précédemment :
| 1 | 2 | 3 |
| 1 | 2 | 3 |
| 1 | 2 | 3 |
| 1 | 2 | 3 |
| 1 | 3 | 2 |
| 1 | 3 | 2 |
| 1 | 3 | 2 |
| 1 | 3 | 2 |
| 3 | 1 | 2 |
| 3 | 1 | 2 |
| 3 | 1 | 2 |
| 3 | 1 | 2 |
| 3 | 2 | 1 |
| 3 | 2 | 1 |
| 3 | 2 | 1 |
| 3 | 2 | 1 |
| 2 | 3 | 1 |
| 2 | 3 | 1 |
| 2 | 3 | 1 |
| 2 | 3 | 1 |
| 2 | 1 | 3 |
| 2 | 1 | 3 |
| 2 | 1 | 3 |
| 2 | 1 | 3 |
en insérant le chiffre 4 :
| 1 | 2 | 3 | 4 |
| 1 | 2 | 4 | 3 |
| 1 | 4 | 2 | 3 |
| 4 | 1 | 2 | 3 |
| 4 | 1 | 3 | 2 |
| 1 | 4 | 3 | 2 |
| 1 | 3 | 4 | 2 |
| 1 | 3 | 2 | 4 |
| 3 | 1 | 2 | 4 |
| 3 | 1 | 4 | 2 |
| 3 | 4 | 1 | 2 |
| 4 | 3 | 1 | 2 |
| 4 | 3 | 2 | 1 |
| 3 | 4 | 2 | 1 |
| 3 | 2 | 4 | 1 |
| 3 | 2 | 1 | 4 |
| 2 | 3 | 1 | 4 |
| 2 | 3 | 4 | 1 |
| 2 | 4 | 3 | 1 |
| 4 | 2 | 3 | 1 |
| 4 | 2 | 1 | 3 |
| 2 | 4 | 1 | 3 |
| 2 | 1 | 4 | 3 |
| 2 | 1 | 3 | 4 |
Conclusions
Ressources
- Description de l'algorithme permettant de générer l'ensemble des permutations pour n donné : 'An algorithm to list all the permutations'
- Nombres de Ramsey : ['Ramsey Number']
Catégories: Logiciel | Pascal | Palm
