Accueil🇫🇷Chercher

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, MR 0172268)
  2. Rado, R. « Universal graphs » () (MR 0214507)
    — « (ibid.) », dans A Seminar in Graph Theory, Holt, Rinehart, and Winston, p. 83–85
  3. Jean-Paul Delahaye, Jean-Paul Delahaye, « Un graphe universel et singulier », sur Pourlascience.fr (consulté le )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.