Graphe
Période historique : 1736 (Euler, Problème des sept ponts de Königsberg)
Le réseau universel de sommets et d'arêtes reliant les informations du monde.
Contenu & Formulation mathématique
Genèse & Portée historique
Structure combinatoire fondamentale définie par un ensemble de sommets reliés par des arêtes (orientées ou non). Né avec la résolution par Euler du problème des ponts de Königsberg, le graphe est l'abstraction suprême pour modéliser les réseaux informatiques, les circuits et les interactions sociales.
Euler prouva en 1736 qu'il était impossible de traverser les sept ponts de Königsberg une fois et une seule en observant uniquement le degré de chaque rive, inaugurant simultanément la topologie et la théorie des graphes.
Filiations & Relations conceptuelles (3)
Théorème des quatre couleurs
Formulé comme la 4-colorabilité des sommets de tout graphe planaire sans boucle.
Formule d'Euler des polyèdres
S'applique directement aux graphes planaires connexes sous la forme S - A + F = 2.
Théorème des mariages de Hall
Caractérise l'existence d'un couplage parfait dans les graphes bipartis.
Objet de collection MathTCG
Graphe
Couple composé d'un ensemble de nœuds (sommets) et d'une collection de liens binaires (arêtes ou arcs).
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.