Graphe universel

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
  1. Rado, R., « Universal graphs and universal functions », Acta Arithmetica, vol. 9,‎ , p. 331–340 (DOI 10.4064/aa-9-4-331-340, Math Reviews 0172268)
  2. Rado, R. (1967). « Universal graphs » A Seminar in Graph Theory: 83–85 p., Holt, Rinehart, and Winston.
  3. Jean-Paul Delahaye, Jean-Paul Delahaye, « Un graphe universel et singulier », sur Pourlascience.fr (consulté le )
  • Portail des mathématiques
  • Portail de l’informatique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.