Graphes et premier nombre de Ramsey
Un article de Wikipedia.
(→Résultats) |
(→Résultats) |
||
Ligne 20 : | Ligne 20 : | ||
L'algorithme utilisé est celui décrit dans les [[Graphes et premier nombre de Ramsey#Ressources|ressources]]. | L'algorithme utilisé est celui décrit dans les [[Graphes et premier nombre de Ramsey#Ressources|ressources]]. | ||
- | Il consiste à partir de toutes les permutations de '' | + | Il consiste à partir de toutes les permutations de ''n = 2'', |
{| align="center" | {| align="center" | ||
|- | |- | ||
Ligne 26 : | Ligne 26 : | ||
|- | |- | ||
| ''2'' || ''1'' | | ''2'' || ''1'' | ||
+ | |} | ||
+ | de déterminer toutes les permutations pour ''n = 3'' en triplant chaque ligne du cas ''n = 2 '' | ||
+ | {| align="center" | ||
+ | |- | ||
+ | | ''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 : | ||
+ | {| align="center" | ||
+ | |- | ||
+ | | ''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 : | ||
+ | |||
+ | {| align="center" | ||
+ | |- | ||
+ | | ''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'' | ||
|} | |} | ||
Version du 22 mars 2008 à 11:49
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.
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 |
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