Ivan Shishkin, Birch Grove

Graphe connexe

Concept history

A revision trail for this concept page.

4 revisions

Back

Revision 4028

9/6/2026, 6:34:24 PM · quark67

Typographique + remplacement du caractère unicode 𝑢 (U+1D462) par `$u$` etc. pour les autres caractéres unicode employés

Compare with revision 401914 changed lines
1- Deux sommets �� et �� d'un [[Graph|graphe]] non orienté G sont dits connectés s’il existe une chaîne entre �� et ��. On peut alors définir sur l'ensemble des sommets �� la relation d’équivalence suivante:
1- Deux sommets $u$ et $v$ d'un [[Graph|graphe]] non orienté $G$ sont dits connectés s’il existe une chaîne entre $u$ et $v$. On peut alors définir sur l'ensemble des sommets $X$ la relation d’équivalence suivante :
2
3������⇔��=�� ou �� et �� sont connectés
3$uRv\iff u=v$ où $u$ et $v$ sont connectés.
4
5Les classes d’équivalence de cette relation sont appelées "composantes connexes de G". Les sommet d’une même composante connexe sont tous connectés entre eux. Deux sommets appartenant à deux composantes connexes différentes ne sont pas connectés.
5Les classes d’équivalence de cette relation sont appelées « composantes connexes de $G$ ». Les sommet d’une même composante connexe sont tous connectés entre eux. Deux sommets appartenant à deux composantes connexes différentes ne sont pas connectés.
6
7Un graphe �� non orienté est donc dit connexe s’il admet une seule composante connexe ��. Sinon il est dit non connexe.
7Un graphe $G$ non orienté est donc dit connexe s’il admet une seule composante connexe $X$. Sinon il est dit non connexe.
8
9
10- Pour les digraphs ([[directed|graphes orientés]]), on définit la raltion d’équivalence comme suit:
10- Pour les digraphes ([[directed|graphes orientés]]), on définit la relation d’équivalence comme suit :
11
12������⇔��=�� ou �� est accessible à partir de �� et vice versa
12$uRv\iff u=v$ où $v$ est accessible à partir de $u$ et vice versa.
13
14Les classes d’équivalence de cette relation sont appelées "composantes fortement connexes de G". Les sommet d’une même composante fortement connexes sont tous accessibles entre eux. Il n’existe aucun chemin entre deux sommets appartenant à deux composantes fortement connexes différentes.
14Les classes d’équivalence de cette relation sont appelées « composantes fortement connexes de $G$ ». Les sommet d’une même composante fortement connexes sont tous accessibles entre eux. Il n’existe aucun chemin entre deux sommets appartenant à deux composantes fortement connexes différentes.

Revision 4019

9/6/2026, 4:16:43 PM · Ancient Tree

Updated title

titleGraphe ConnexeGraphe connexe

Revision 3978

9/6/2026, 11:01:48 AM · T.W

Added exercise "Un nombre minimal de sommets pour les graphes connexes."

linked exercisesNoneUn nombre minimal de sommets pour les graphes connexes.

Revision 2964

8/30/2026, 4:55:18 PM · Nix

Concept translation created

- Deux sommets 𝑢 et 𝑣 d'un [[Graph|graphe]] non orienté G sont dits connectés s’il existe une chaîne entre 𝑢 et 𝑣. On peut alors définir sur l'ensemble des sommets 𝑋 la relation d’équivalence suivante:

𝑢𝑅𝑣⇔𝑢=𝑣 ou 𝑢 et 𝑣 sont connectés

Les classes d’équivalence de cette relation sont appelées "composantes connexes de G". Les sommet d’une même composante connexe sont tous connectés entre eux. Deux sommets appartenant à deux composantes connexes différentes ne sont pas connectés.

Un graphe 𝐺 non orienté est donc dit connexe s’il admet une seule composante connexe 𝑋. Sinon il est dit non connexe.


- Pour les digraphs ([[directed|graphes orientés]]), on définit la raltion d’équivalence comme suit: 

𝑢𝑅𝑣⇔𝑢=𝑣 ou 𝑣 est accessible à partir de 𝑢 et vice versa

Les classes d’équivalence de cette relation sont appelées "composantes fortement connexes de G". Les sommet d’une même composante fortement connexes sont tous accessibles entre eux. Il n’existe aucun chemin entre deux sommets appartenant à deux composantes fortement connexes différentes.