∑
MathTCG
#095 / 100•Space, Chance & Computation•MathTCG #495 / 500•★Commune•⊦Maths Discrètes•Concept

Arbre en théorie des graphes

Période historique : 1857

Graphe connexe et acyclique : l'ossature minimale reliant n sommets par exactement n - 1 arêtes.

Contenu & Formulation mathématique

Définition rigoureuse
Graphe connexe et acyclique : l'ossature minimale reliant n sommets par exactement n - 1 arêtes.
G arbre  ⟺  (G connexe ∧∣E∣=∣V∣−1)  ⟹  Cayley : nn−2 arbresG \text{ arbre} \iff (G \text{ connexe } \land |E| = |V| - 1) \implies \text{Cayley : } n^{n-2} \text{ arbres}

Genèse & Portée historique

Graphe sans aucun cycle, un arbre vérifie de multiples propriétés équivalentes : il est connexe à n - 1 arêtes ; il est acyclique à n - 1 arêtes ; ou encore, entre toute paire de sommets, il existe une chaîne élémentaire unique. Tout arbre non trivial possède au moins deux feuilles (sommets de degré 1).

Arthur Cayley a forgé le terme d'arbre en 1857 en dénombrant les isomères des hydrocarbures saturés C_n H_{2n+2} (alcanes), reliant la chimie à la combinatoire.

« L'épure absolue : relier tous les points du monde sans jamais refermer de boucle. »

Filiations & Relations conceptuelles (1)

Cas particulier de#494

Graphe connexe

Un arbre est un graphe connexe dépourvu de cycles.

Objet de collection MathTCG

#495
★Commune
⊦

Arbre en théorie des graphes

Maths Discrètes•CONCEPT

Graphe connexe et acyclique : l'ossature minimale reliant n sommets par exactement n - 1 arêtes.

G arbre  ⟺  (G connexe ∧∣E∣=∣V∣−1)  ⟹  Cayley : nn−2 arbresG \text{ arbre} \iff (G \text{ connexe } \land |E| = |V| - 1) \implies \text{Cayley : } n^{n-2} \text{ arbres}
1857

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.

Extension : Space, Chance & Computation (#095 / 100)
Numéro global MathTCG : MathTCG #495 / 500
Rareté officielle : Commune (★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : arbre-en-theorie-des-graphes
Consulter mon classeurExplorer tout le recueil