Graphes et premier nombre de Ramsey

Un article de Wikipedia.

(Différences entre les versions)
(→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 ''k = 2'',
+
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

Récupérée de « http://zigloo.ch/index.php/Graphes_et_premier_nombre_de_Ramsey »