Graphes et premier nombre de Ramsey
Un article de Wikipedia.
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'
Catégories: Logiciel | Pascal | Palm
