Graphes et premier nombre de Ramsey
Un article de Wikipedia.
(Différences entre les versions)
(→Introduction) |
(→Ressources) |
||
Ligne 18 : | Ligne 18 : | ||
== Conclusions == | == Conclusions == | ||
== 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'] | ||
+ | |||
[[Category:Logiciel]] | [[Category:Logiciel]] | ||
[[Category:Pascal]] | [[Category:Pascal]] | ||
[[Category:Palm]] | [[Category:Palm]] |
Version du 22 mars 2008 à 11:33
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
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