Annuler
connectez vous
autre en post-bac
- Ensemble et application Partie II
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann AutreTopics traitant de autre [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Graphe connexe
Posté par RoronoaZoro
Bonjour tout le monde 
Alors voilà je voulais savoir si il y a une méthode générale (ou plusieurs mais pas trop non plus) pour montrer qu' un graphe est connexe .
Je dois montrer que le graphe de Johnson J (n,k), dont l'ensemble de sommets est k parmi n et où on a une arête si l intersection de deux sommets est égal à k-1, est connexe. Mais je ne vois par où commencer ! 
Merci 
Tu veux dire que l'ensemble des sommets est l'ensemble des parties à éléments d'un ensemble fixé
à
éléments ?
La connexité est assez évidente : si et
sont deux parties à
éléments de
, on passe de
à
en remplaçant l'un après l'autre les éléments de
par ceux de
. Le nombre d'étape est égal à
moins le cardinal de
.
oui les sommets c'est bien ça ! Par contre je ne comprends pas pourquoi on fait ça et en quoi ça montre la connexité ?
Bonsoir,
pour voir comment utiliser l'indication de Recomic35, que je salue, tu peux tracer effectivement le graphe pour de petites valeurs de n et k.
Je te conseille n=4 et k=2.
Le graphe n'est pas trop trivial et pas trop grand.
Bonsoir
J'ai réussi à tracer le graphe pour n=4 k=2 j'ai une figure à 6 sommets. Que dois je faire ensuite ?
si j'ai bien compris A et B sont deux sommets du graphes. Mais je ne vois pas ce que c'est A\B et B\A
Tu as raison, il a bien 12 arêtes.
Je ne sais plus faire une multiplication 
Après tu regardes l'indication de Recomic35.
Par exemple, en partant de l'ensemble {a,b,c,d} comment {a,b} est-il relié à {c,d} ?
Il suffit ensuite de généraliser.
Pas de soucis
{a,b} est relié à {b,c} qui est relié à {c,d}. J'arrive à comprendre à peu près l'idée mais je comprends pas ce que c'est A\B et B\A par exemple dans notre cas si on pose A={a,b} et B={c,d} qu'est ce que c'est A\B et B\A car ils ont aucun élément en commun
D'accord ! Je crois que j'ai compris
Merci !
Sinon il y a t il une méthode générale pour montrer la connexité d'un graphe ?
Ben en faite je comprends la définition mais je ne voyais pas ce que ça représentait par rapport aux sommets. Avec l'explication de verdurin j'ai compris ! Mais j'ai encore un doute quand vous dites qu'on remplace les éléments de A\B par B\A pourquoi on a le droit de faire ça?
C'est pourtant simple !
Supposons et
Donc et
On veut aller de à
par des arêtes du graphe. On prend un élément de
, disons
et on le remplace par un élément de
, disons
.
On passe ainsi de à
par une arête (puisque
et
ont deux éléments en commun). Ensuite on prend l'élément restant de
, qui est
, et on le remplace par l'élément restant de
, qui est
. On passe ainsi de
à
par une arête.
De manière générale, on voit qu'en remplaçant au fur et à mesure chaque élément de par un élément de
, on passe de
à
par un chemin constitué de (
moins le cardinal de
) arêtes.
Exercice : et
sont tous les deux de cardinal
, et
est de cardinal
. Combien y a-t-il dans le graphe de chemins de longueur
(c.-à-d. constitués de
arêtes) allant de
à
?
Bonsoir,
j'ai comprends mieux maintenant la preuve de la connexité mais comment avez vous fait pour trouver le nombre d'arêtes du chemin ?
et pour votre exo j'ai pas compris la question
et
sont tous les deux de cardinal
moins le cardinal de
.
Si tu ne comprends déjà pas la question de l'exercice, laisse tomber.