Graphes et premier nombre de Ramsey
Un article de Wikipedia.
(Différences entre les versions)
(→Introduction) |
(→Introduction) |
||
| Ligne 9 : | Ligne 9 : | ||
* une permutation des sommets d'un graphe équivaut à l'autre | * 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 | * 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 === | === Nombre de Ramsey === | ||
Version du 22 mars 2008 à 11:28
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
Catégories: Logiciel | Pascal | Palm
