Discussion:Théorème de Kőnig (théorie des graphes)
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Français[modifier le code]
L'article me paraît transcrit de l'anglais et garde d'ailleurs plusieurs traces de franglais (en français, on dit cardinal et non cardinalité, les maths sont typographiés en romain, sauf les minuscules qui sont en italique etc.). Les notations sont parfois sous-entendues. Je modifierais bien trois paragraphes comme ceci :
Définitions[modifier le code]
Un couplage d'un graphe G est un sous-ensemble d'arêtes de G deux-à-deux non adjacentes ; un sommet est couplé s'il est extrémité d'une arête du couplage. Un transversal de G est un sous-ensemble T de sommets de G avec la propriété que toute arête de G est incidente à au moins un sommet de T (on dit aussi que T couvre les arêtes de G et l'on appelle aussi T une couverture nodale de G).
Ces deux invariants sont reliés par une relation de dualité faible :
Dans tout graphe, le cardinal de tout couplage est inférieur ou égal au cardinal de tout transversal.
La preuve réside dans le fait qu'un sommet ne peut couvrir plus d'une arête d'un couplage. L'inégalité est vraie en particulier du cardinal maximum d'un couplage et du cardinal minimum d'un transversal. Remarquons que cette inégalité peut être stricte, comme c'est le cas si G est le graphe triangle (le graphe complet à 3 sommets).
Théorème[modifier le code]
Le théorème de König établit une relation de dualité forte pour les graphes bipartis :
Théorème (Dénes König, 1931) – Dans tout graphe biparti, le cardinal maximum d'un couplage est égal au cardinal minimum d'un transversal.
Démonstration[modifier le code]
Ce théorème n'est pas difficile à démontrer ; il en existe plusieurs preuves courtes (voir la référence). En voici une démonstration constructive, qui donne un algorithme pour trouver un transversal minimal à partir d'un couplage maximal M pour le graphe G.
Comme G est biparti, ses sommets se répartissent en deux ensembles U et V et pour les arêtes (u,v) il sera entendu que u ∈ U et que v ∈ V.
Soit Z l'ensemble des sommets de U qui ne sont pas couplés par M. Puis ajoutons à Z tous les sommets atteignables à partir de Z par des chemins alternants, c'est-à-dire dont les arêtes sont alternativement non dans M puis dans M. La construction de Z implique que pour chaque arête (u,v) de M, si v ∈ Z alors u ∈ Z également. Et si u ∈ Z, comme u n'était pas initialement dans les sommets libres de U, u a été ajouté à Z grâce à l'arête (u,v), donc v ∈ Z. Ceci implique que pour chaque arête du couplage M, soit ses deux extrémités sont dans Z soit aucune.
Autrement dit, en notant S := (U − Z) ∪ (V ∩ Z), toute arête du couplage a exactement une extrémité dans S, donc |S| ≥ |M|.
On va montrer que S couvre toutes les arêtes du graphe. Soit (u,v) une arête du graphe. Si u ∉ Z, alors u ∈ S et l'arête est couverte, alors supposons u ∈ Z. Si (u,v) est dans M, alors par l'observation précédente v ∈ Z, et donc v ∈ S. Si (u,v) n'est pas dans M, alors par maximalité de Z, v doit aussi être dans Z, donc dans S. Ceci montre que S est un transversal.
Au vu de la relation de dualité faible ci-dessus |S| ≤ |M|, nous pouvons conclure |S| = |M|.
JC.Raoult (discuter) 25 novembre 2018 à 17:49 (CET)
- Aucune réaction, je publie donc mes modifications, qui d'ailleurs sont essentiellement cosmétiques.JC.Raoult (discuter) 8 février 2019 à 09:49 (CET)
Erreur dans la preuve[modifier le code]
Le dernier argument utilisé dans la preuve (appel à la dualité faible) fait usage de l'inégalité dans le mauvais sens. En tant que couplage, M est de plus petit cardinal que S d'après le lemme général et non l'inverse. La preuve est donc fausse ou incomplète?