Graphes et premier nombre de Ramsey
Un article de Wikipedia.
(Différences entre les versions)
(→But) |
(→Introduction) |
||
| Ligne 4 : | Ligne 4 : | ||
== Introduction == | == 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 == | == Résultats == | ||
== Conclusions == | == Conclusions == | ||
Version du 22 mars 2008 à 11:27
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
