Nombre minimum d'arête pour rendre un graphe connexe

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
dzgpt86
Messages: 3
Enregistré le: 11 Oct 2021, 03:10

Nombre minimum d'arête pour rendre un graphe connexe

par dzgpt86 » 11 Oct 2021, 03:16

Bonjour, Bonsoir,

Soit un graphe G = (V,E) avec k composantes connexes.
Je souhaite rendre le graphe connexe, il faut donc ajouter exactement k - 1 arêtes.

Mais je n'arrive pas à prouver ça de manière formelle, si quelqu'un a une piste je suis preneur !

Merci d'avance !



Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

Re: Nombre minimum d'arête pour rendre un graphe connexe

par mathelot » 11 Oct 2021, 11:55

bonjour,
du graphe G , on peut en déduire un graphe G' à k sommets , chaque sommet de G' étant une composante connexe de G. G' est discret,il a k composantes connexes réduites à un point. Pour le rendre connexe, il faut donc ajouter k-1 arêtes. Ensuite G' est connexe si et seulement si G est connexe.
Modifié en dernier par mathelot le 11 Oct 2021, 13:53, modifié 1 fois.

tournesol
Membre Irrationnel
Messages: 1509
Enregistré le: 01 Mar 2019, 20:31

Re: Nombre minimum d'arête pour rendre un graphe connexe

par tournesol » 11 Oct 2021, 13:04

Bonjour
On peut faire une récurrence sur le nombre de composantes connexes mais il faut bien formuler l'hypothèse :
Supposons que pour tout graphe qui a k composantes connexes , on peut le rendre connexe en lui ajoutant k-1 arêtes convenablement choisies , mais on ne peut pas le rendre connexe en lui ajoutant k-2 arêtes .
D'autre part , Il faut initialiser à 0 et à 1 .

dzgpt86
Messages: 3
Enregistré le: 11 Oct 2021, 03:10

Re: Nombre minimum d'arête pour rendre un graphe connexe

par dzgpt86 » 11 Oct 2021, 14:34

mathelot a écrit:bonjour,
du graphe G , on peut en déduire un graphe G' à k sommets , chaque sommet de G' étant une composante connexe de G. G' est discret,il a k composantes connexes réduites à un point. Pour le rendre connexe, il faut donc ajouter k-1 arêtes. Ensuite G' est connexe si et seulement si G est connexe.


Bonjour mathelot,
Merci pour votre réponse elle est claire mais juste pour G' connexe <=> G connexe c'est admis ?
Je vois bien l'intuition derrière que si l'on rajoute les sommets que l'on avait omis ils sont tous forcément directement ou non reliés à un sommet de G'

dzgpt86
Messages: 3
Enregistré le: 11 Oct 2021, 03:10

Re: Nombre minimum d'arête pour rendre un graphe connexe

par dzgpt86 » 11 Oct 2021, 14:38

tournesol a écrit:Bonjour
On peut faire une récurrence sur le nombre de composantes connexes mais il faut bien formuler l'hypothèse :
Supposons que pour tout graphe qui a k composantes connexes , on peut le rendre connexe en lui ajoutant k-1 arêtes convenablement choisies , mais on ne peut pas le rendre connexe en lui ajoutant k-2 arêtes .
D'autre part , Il faut initialiser à 0 et à 1 .


Bonjour tournesol,
Merci pour votre réponse.
Initialiser k à 0 ? Un graphe sans composante connexe = graphe vide OK
Initialiser k à 1 ? Un graphe avec 1 seule composante connexe est connexe OK
Ou peut-être vouliez-vous dire initialiser k-2=0, k-1=1 et donc k = 2 ? Avec 0 arête c'est impossible mais en ajoutant 1 arête reliant 1 point de chaque composante connexe OK

Par contre pour l'hérédité je ne vois pas du tout :(

tournesol
Membre Irrationnel
Messages: 1509
Enregistré le: 01 Mar 2019, 20:31

Re: Nombre minimum d'arête pour rendre un graphe connexe

par tournesol » 11 Oct 2021, 14:58

Désolé , j'ai voulu dire non pas à 0 et à 1 mais à1 et à 2 .
si k+1 composante connexes , tu rends connexe un ensemble de k d'entre elles . Tu n'as alors plus que 2 composantes connexes , et tu appliques ton initialisation .

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 52 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite