Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Graphe Biparti

Posté par
random
11-11-20 à 19:11

Bonsoir,

Pour mon DM de Theorie des Graphes, je bloque sur la derniere partie de cette exo:

1. Montrez qu'un graphe connexe avec au moins autant d'arêtes que de sommets doit contenir un cycle.

2. Soit G un graphe connexe à n sommets et m arêtes pour n 2. Montrer que G contient un sous-graphe biparti H: = H (V; E) avec V (H) = V (G) et |E(H)| m/2

3. Soit K un graphe connexe avec n sommets et au moins 2n - 1 arêtes pour n 2. Montrer que K contient un cycle de longueur paire.

Alors j'ai montrer 1 et 2 mais pour 3, voila mon idee: K est connexe donc on pourrait appliquer 1 et déclarer qu'il contient un cycle. Ensuite,  appliquer 2 à K et déclarer qu'il contient aussi un sous-graphe biparti, mais je ne peux pas simplement affirmer que mon cycle est dans le sous-graphe biparti et devrai le prouver? C'est pourquoi j'ai aussi pensé à appliquer d'abord 2 pour dire que j'ai un sous-graphe biparti dans K puis utiliser 1 sur le sous-graphe biparti, cependant je ne peux utiliser 1 que lorsque le graphe est connexe, or est-ce que le sous-graphe biparti de mon graphe  K est également connexe? Du coup j'ai donc pensé à considérer les parties connexes du sous-graphe biparti de K mais je ne suis pas sûr que celles-ci respectent la condition sur le nombre minimum d'arêtes.

Des idees ? Merci d'avance !

Posté par
GBZM
re : Graphe Biparti 11-11-20 à 20:21

Bonsoir,

Dans un graphe biparti, tout cycle est pair.

Posté par
random
re : Graphe Biparti 11-11-20 à 20:32

BonsoirGBZM

Oui tout a fait ! C'est justement la propriete que je conte utiliser mais comment montrer que mon cycle est effectivement dans le sous-graphe biparti de K ?

Posté par
GBZM
re : Graphe Biparti 12-11-20 à 11:11

Dans la question 2, ne peut on pas demander en plus que le graphe biparti extrait soit connexe ?

Posté par
random
re : Graphe Biparti 12-11-20 à 11:29

Je crois que ca ne l'est pas forcement, c'est pourquoi j'ai pensé à considérer les parties connexes du sous-graphe biparti de K (mais je ne suis pas sure comment)

Posté par
GBZM
re : Graphe Biparti 12-11-20 à 13:47

Quelle est ta démonstration pour 2) ?

Posté par
random
re : Graphe Biparti 12-11-20 à 14:09

J'ai utilise la recurrence sur le nombre d'arretes de G

Posté par
GBZM
re : Graphe Biparti 12-11-20 à 14:23

Sois plus précis.

Posté par
random
re : Graphe Biparti 12-11-20 à 15:05

Pardon je voulais dire sommets. J'ai suppose que le resultat est vrai pour un graphe avec moins de n sommets. Maintenant choisissons un sommet v de G, et soit A le graphe obtenu à partir de G en supprimant v et toutes les arêtes de G incidentes en v. Si d = deg (v), | E (A) | = | E (G) | - d. Par l'hypothèse de récurrence, A a un sous-graphe biparti H avec au moins | E (A) | / 2 arêtes; soit V1 et V2 les ensembles de sommets de ce sous-graphe. On peut supposer que V1∪V2 = V (H), c'est-à-dire que H garde tous les sommets de A. Maintenant il suffit d'ajouter v à V1 ou à V2 tout en decidant laquelle des d arêtes de G incidentes à v garder pour obtenir un sous-graphe biparti de G avec au moins | E (G) | / 2  arêtes.

Posté par
GBZM
re : Graphe Biparti 12-11-20 à 15:11

Et le graphe biparti que tu construis ainsi ne serait-il pas automatiquement connexe, si le graphe G de départ l'est ?

Posté par
random
re : Graphe Biparti 12-11-20 à 19:55

Je vois, donc est-ce suffisant comme justification de dire que mon sous-graphe biparti est "automatiquement" connexe?

Posté par
GBZM
re : Graphe Biparti 12-11-20 à 20:43

Tu peux le montrer en utilisant la récurrence.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !