Graphe universel
Cet article est une ébauche concernant les mathématiques et l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En mathématiques et en informatique théorique, un graphe universel est un graphe infini qui contient tous les graphes finis (ou dénombrables) comme sous-graphes.
Le premier graphe universel a été introduit par Richard Rado[1],[2] et s’appelle le graphe de Rado (encore appelé graphe aléatoire). C'est l'analogue des nombres univers qui contiennent dans leurs décimales toutes les suites finies de chiffres[3].
Notes et références modifier
- Rado, R., « Universal graphs and universal functions », Acta Arithmetica, vol. 9, , p. 331–340 (DOI 10.4064/aa-9-4-331-340, MR 0172268)
- Rado, R. « Universal graphs » () (MR 0214507)
— « (ibid.) », dans A Seminar in Graph Theory, Holt, Rinehart, and Winston, p. 83–85 - Jean-Paul Delahaye, Jean-Paul Delahaye, « Un graphe universel et singulier », sur Pourlascience.fr (consulté le )
