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
-
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 !
-
mathelot
- Habitué(e)
- Messages: 13688
- Enregistré le: 08 Juin 2006, 09:55
-
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
-
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
-
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
-
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
-
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 .
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 52 invités