Bonsoir, je ne suis pas sure comment m'y prendre pour cet exercise:

Soit G = G (V, E) un graphe quelconque. Un couplage dans G est un sous-ensemble d'arêtes M qui n'ont pas de sommets en commun. Autrement dit, M ? E (G) et tout e, f ? M sont par paires non-incidentes.
Soit H un graphe biparti avec m arêtes, où m> 0 et supposons que d
est le degré maximal de n'importe quel sommet; C'est a dire d:= max {deg (v): v ? V (H)}.

Montrer que H admet un couplage de taille au moins m/d.

Alors je sais que le theoreme de Hall donne une condition nécessaire et suffisante pour l'existence d'un couplage parfait de taille |V(H)|/2, mais je ne vois pas comment utiliser le degre maximal ? Des idees ou indications ? Merci d'avance !

*** message déplacé ***quand un sujet est verrouillé, c'est pas pour en ouvrir un autre...

Pardon ! J'etais un peu confus et n'ai pas su comment vous contacter. Quel est le problème avec le sujet? Que puis-je faire pour qu'il soit conforme?

_{modération > ton message est conforme désormais...le tout est que quelqu'un maintenant s'empare de ton sujet}

Bonjour,

Tu n'as pas besoin de gros attirail pour résoudre cette question. Il suffit de raisonner par récurrence sur le nombre d'arêtes.
Suppose que le résultat est vrai pour tous les graphes bipartis de degré maximal d qui ont strictement moins de m arêtes. Que fais-tu pour le démontrer pour un graphe biparti de degré maximal d avec m arêtes ?

Bonjour GBZM,

Je n'ai pas vraiment eu d'idees pour m'y prendre par recurrence...

Mais en y reflechissant, je pourrais utiliser la notion d'indice chromatique. Une coloration des arêtes d'un graphe consiste à attribuer à chaque arête non incidantes une couleur, donc chaque ensemble d'aretes de meme couleur definie un couplage. L'indice chromatique de G est le nombre minimal de couleurs nécessaires pour réaliser la coloration des arêtes de G. On sait que pour un graphe biparti χ′(G) = d (degres maximal dans G) donc il existe au moins d couplages distincts dans G. Maintenant puis-je directement dire que par conséquent la taille que chaque couplage est au moins m/d ? Ou devrai-je le justifier d'avantage ?

Désolé, en y repensant l'idée de récurrence que j'avais ne marche pas.

Je ne vois alors pas d'autre voie que de montrer qu'il existe un coloriage des arêtes avec au plus d couleurs : on ne peut pas avoir toutes les couleurs à strictement moins de m/d arêtes, puisque le nombre total des arêtes est m.
Maintenant, ce résultat sur le coloriage se démontre bien par récurrence sur le nombre d'arêtes !

GBZM

Pourquoi est-ce au plus d couleurs ? D'apres mon raisonemment ci-dessus un coloriage d'arêtes d'un graphe consiste à attribuer à chaque arêtes non incidantes une couleur, donc un graphe colorié avec k couleurs contient k ensembles d'aretes non incidantes de meme couleur c'est a dire k couplages differents. Par definition, les graphes bipartis peuvent etres colorier avec au moins d couleurs differentes. Donc H admet au moins couplage differents et puisque H a m aretes, forcement l'un de ces d couplages sera de taille au moins m/d.

Suis-je correct ?

Non, ce que tu racontes ne va pas.
Si tu veux utiliser les coloriages, tu dois majorer le nombre de couleurs pour qu'il y ait au moins une couleur (et donc un couplage) avec beaucoup d'arêtes.

Bonsoir GBZM

Pourriez-vous expliquer d'avantage svp ? Je suis un peu perdu

Il n'y a aucune subtilité, ni rien de spécifique aux graphes. Si tu divises un ensemble à m éléments en p paquets et si tu veux être sûr qu'au moins un des paquets soit de taille au moins m/d, tu as intérêt à avoir p inférieur ou égal à d.

D'accord, dans notre cas, on veut diviser l'ensemble de m aretes dans H en p packet et le theoreme de Konig pour l'indice chromatique de graphe biparti nous dit que le minimum de couleur pour obtenir un coloriage de H (indice chromatique de H) est d le degres maximal χ′(H) = d, du coup on peut diviser l'ensemble de m aretes non-adjacantes en p =d paquets de taille au moins m/d. Ce qui implique le resultat?

Euh ... ce que tu écris n'est pas du tout satisfaisant.
En particulier, il n'y a aucune raison pour que tous les paquets soient de taille au moins m/d.
Le problème est un problème de raisonnement élémentaire, bien en deçà des résultats sophistiqués de théorie des graphes.

Puisque j'ai m elements au total (m aretes) et d paquets, si ces paquets sont de tailles egales, on aura exactement m/d elements dans chacun, sinon, si l'un a moins de m/d element, un autre en aura forcement plus de m/d ? Je ne vois pas ou est l'erreur de raisonement, ca me parait intuitive (mais j'admet que ces questions de 'taille' d'ensembles n'ont jamais ete mon point fort...)

Comprends-tu que
"on peut diviser l'ensemble de m aretes non-adjacantes en p =d paquets de taille au moins m/d."
n'est pas un raisonnement correct pour montrer qu'une des couleurs n'a pas qu moins m/d arêtes ?
Tu as fait quelque chose d'un peu plus correct depuis, mais ça reste bancal.
Si on a au plus d paquets qui ont chacun strictement moins de m/d arêtes, le nombre total d'arêtes de ces paquets est < ?

Oui je comprends ce que vous dites, mais je n'ai besoin que d'un ensemble de meme couleur avec moins m/d arêtes . L'exercise demande uniquement de montrer que H admet un couplage de taille au moins m/d, non pas que tout les couplages satisfaient cette propriete.

Pour repondre a votre question: si on a au plus d paquets qui ont chacun strictement moins de m/d arêtes, le nombre total d'arêtes de ces paquets est < m?

Hum... J'ai l'impression que tu as quelques petits soucis de logique.

Pour répondre à la question, tu cherches à montrer qu'il existe une couleur qui a au moins m/d arêtes. Pour cela, on montre qu'il est impossible que chaque couleur ait strictement moins de m/d arêtes, vu qu'il y a au plus d couleurs et que le nombre total d'arêtes est m.

As-tu fini par comprendre que ce qui est important, c'est qu'il y ait un coloriage des arêtes avec AU PLUS d couleurs ?

Desole  de vous avoir fait vous repeter mais je crois que j'ai enfin saisi.

Maintenant comment montrer qu'il existe au plus d couleurs ? La piste que j'avais en utilisant le theoreme de Konig ne tient plus.

On raisonne par récurrence sur le nombre d'arêtes, en utilisant l'idée de démonstration du théorème de Vizing.
Ça te suffit comme indication, ou faut-il que je détaille ?

m = 1
Un graphe à 1 arête a d = 1 et peut se colorer avec au plus une couleur.

Supposons la propriété vraie pour un entier m quelconque, et montrons qu'elle reste vraie pour l'entier m+1. Soit H un graphe biparti à m+1 arêtes et d le degree maximal. Enlevons une arête e de ce graphe.
Soit A et B les sommets initialement reliés par l'arête e. d(A)<d et d(B)<d puisqu'ils ont perdu l'arete e. Si d est toujours le degre maximal, on obtient un graphe H' à m arêtes dont on peut colorer les arêtes avec au plus d couleurs, d'après l'hypothèse de récurrence. Sinon, le graphe peut etre colorer avec au plus d-1 couleurs. Essayons à présent de remettre  e dans H' pour obtenir à nouveau le graphe H.
Nécessairement, il existe une couleur parmi les d disponibles qui n'est pas utilisée pour colorer les arêtes incidentes au sommet A. De même, il existe une couleur parmi les d qui n'est pas utilisée pour la coloration des arêtes de B.

Si on peut trouver une couleur non utilisée à la fois pour la coloration des arêtes adjacentes à A et pour la coloration des arêtes adjacentes à B, alors il suffit de choisir cette couleur pour e et de replacer cette arête une fois colorée à son emplacement initial dans H.

Qu'en est-il pour les autre cas ? Y'a t il un algorithm pour faire "tourner" les couleurs et qui utilise la propriete biparti de H ?

On utilise la même idée que pour la démonstration du théorème de Vizing. On part d'un coloriage des arêtes du graphe privé de l'arête AB avec d couleurs (pas forcément toutes utilisées).
Soit a une couleur qui manque en A, b une qui manque en B (dans le lot de d couleurs). Partant de B, on construit le chemin maximal avec une arête de couleur a, puis une arête de couleur b, puis une arête de couleur a en alternant ainsi jusqu'à ce qu'on ne puisse plus (éventuellement, le chemin est de longueur 0 s'il n'y a pas non plus d'arête de couleur a partant de B). Le chemin n'arrive forcément pas au sommet A (on utilise ici le fait que le graphe est biparti).
On intervertit les couleurs a et b le long de ce chemin maximal. On a toujours un coloriage correct du graphe privé de l'arête entre A et B, et il suffit alors de colorier cette arête avec la couleur a.

D'accord, mais la couleur a est manquante pour A uniquement, pas necessairement manquante en B? Pourriez-vous aussi expliquer d'avantage comment le fait que le graphe est biparti nous guaranti que le chemain ne reviendra pas vers A ?  (Quand j'imagine un graphe complet, ca m'a l'air possible)

Ignorez ma premiere question sur a qui doit etre manquante en B, je n'avais pas bien interpreté l'algorithme et j'ai cru que l'on recoloriait tout le graphe, mais en fait on ne fait que suivre le chemain déja colorié?

Oui. Et as-tu compris pourquoi on ne peut pas revenir en A ?

Non, je ne vois pas pourquoi. A ne pourrait-il avoir une arete de couleur b et faire partie du chemain ?

Dans le graphe biparti, il y a deux côtés, celui de A et celui de B. Le chemin aux couleurs qui alternent entre a et b part de B, et il visite successivement un côté puis l'autre.
Vois-tu maintenant, ou dois-je encore détailler ?

Je suis d'accord mais en arrivant a un certain sommet du cote de B, si ce sommet est lié a A par la couleur b, on pourrait tres bien se retrouver en A. Pouvez-vous détaillé ?

Mais voyons, puisqu'on part de B avec la couleur a, quand on va du côté de B vers le côté de A, c'est avec la couleur a !

Aaaaah d'accord je vois maintenant. Je crois que j'ai enfin compris la preuve, merci infiniment pour toutes vos explications !

Avec plaisir.