Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème des amis et des étrangers
Résumé
droite|cadre|
Les 78 graphes possibles amis-étrangers avec 6 nœuds. Pour chaque graphe, les nœuds rouge/bleu montrent un exemple de triplet d'amis ou d'inconnus mutuels.
Le théorème des amis et des étrangers ou théorème des amis et des inconnus est un théorème dans le domaine des mathématiques appelé théorie de Ramsey et est un cas particulier du théorème de Ramsey.
Supposons qu'une fête comporte six invités. Considérons deux d'entre eux. Ils pourraient se rencontrer pour la première fois—dans ce cas, nous allons les appeler des étrangers ou inconnus ; ou ils pourraient s'être rencontrés auparavant—dans ce cas, nous allons les appeler des connaissances mutuelles ou amis. Le théorème dit :
Dans toute fête de six personnes, soit au moins trois d'entre eux sont (par paires) mutuellement des étrangers, soit au moins trois d'entre eux sont (par paires) mutuellement des amis.
Une démonstration du théorème exige seulement un raisonnement logique en trois étapes. Il est commode de formuler le problème dans le langage de la théorie des graphes.
Supposons qu'un graphe simple a 6 sommets et que chaque paire de sommets (distincts) est jointe par une arête. Un tel graphe est appelé graphe complet (car il ne peut y avoir plus d'arêtes). Un graphe complet sur sommets est notée par le symbole .
Maintenant, prenez le graphe . Il a 15 arêtes en tout. Les 6 sommets correspondent aux 6 personnes de la fête. On choisit que les arêtes seront de couleur rouge ou bleu selon que les deux personnes représentées par les sommets reliés par l'arête commune, sont des étrangers ou des connaissances, respectivement. Le théorème affirme :
Peu importe comment vous coloriez les 15 arêtes d'un en rouge et bleu, vous ne pouvez pas éviter d'avoir soit un triangle rouge, un triangle dont les trois côtés sont de couleur rouge, ce qui représente trois paires d'étrangers mutuels—ou un triangle bleu, représentant les trois paires de connaissances mutuelles. En d'autres termes, quelles que soient les couleurs que vous utilisez, il y aura toujours au moins un triangle monochromatique (c'est un triangle dont tous les côtés ont la même couleur).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.