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