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

Graphe connexe

Période historique : 1736

Graphe d'un seul tenant où il existe toujours au moins une chaîne reliant deux sommets quelconques.

Contenu & Formulation mathématique

Définition rigoureuse
Graphe d'un seul tenant où il existe toujours au moins une chaîne reliant deux sommets quelconques.
∀u,v∈V, ∃ chemin (u=x0,x1,…,xk=v)∧∣E∣≥∣V∣−1\forall u, v \in V, \, \exists \text{ chemin } (u = x_0, x_1, \dots, x_k = v) \quad \land \quad |E| \ge |V| - 1

Genèse & Portée historique

Un graphe non orienté est connexe s'il ne peut être partitionné en deux sous-graphes sans arête entre eux. Le nombre de composantes connexes est un invariant topologique fondamental. Un graphe connexe à n sommets possède au minimum n - 1 arêtes.

C'est en résolvant le problème des sept ponts de Königsberg en 1736 qu'Euler a implicitement fondé la connexité des graphes.

« Aucun sommet n'est une île : le chemin existe toujours pour qui veut voyager. »

Filiations & Relations conceptuelles (2)

Généralise#495

Arbre en théorie des graphes

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

S'applique à#498

Parcours en largeur

Le parcours en largeur explore niveau par niveau les composantes connexes d'un graphe.

Objet de collection MathTCG

#494
★Commune
⊦

Graphe connexe

Maths Discrètes•CONCEPT

Graphe d'un seul tenant où il existe toujours au moins une chaîne reliant deux sommets quelconques.

∀u,v∈V, ∃ chemin (u=x0,x1,…,xk=v)∧∣E∣≥∣V∣−1\forall u, v \in V, \, \exists \text{ chemin } (u = x_0, x_1, \dots, x_k = v) \quad \land \quad |E| \ge |V| - 1
1736

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

Extension : Space, Chance & Computation (#094 / 100)
Numéro global MathTCG : MathTCG #494 / 500
Rareté officielle : Commune (★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : graphe-connexe
Consulter mon classeurExplorer tout le recueil