Server : Apache System : Linux webd348.cluster026.gra.hosting.ovh.net 5.15.148-ovh-vps-grsec-zfs-classid #1 SMP Thu Feb 8 09:41:04 UTC 2024 x86_64 User : hednacluml ( 122243) PHP Version : 8.3.9 Disable Function : _dyuweyrj4,_dyuweyrj4r,dl Directory : /home/hednacluml/encyclo/articles/t/h/é/ |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr" lang="fr" dir="ltr"> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <!-- headlinks removed --> <link rel="shortcut icon" href="../../../../misc/favicon.ico"/> <title>Théorème de Hall - Wikipédia</title> <style type="text/css">/*<![CDATA[*/ @import "../../../../skins/offline/main.css"; /*]]>*/</style> <link rel="stylesheet" type="text/css" media="print" href="../../../../skins/common/commonPrint.css" /> <!--[if lt IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE50Fixes.css";</style><![endif]--> <!--[if IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE55Fixes.css";</style><![endif]--> <!--[if IE 6]><style type="text/css">@import "../../../../skins/monobook/IE60Fixes.css";</style><![endif]--> <!--[if IE]><script type="text/javascript" src="../../../../skins/common/IEFixes.js"></script> <meta http-equiv="imagetoolbar" content="no" /><![endif]--> <script type="text/javascript" src="../../../../skins/common/wikibits.js"></script> <script type="text/javascript" src="../../../../skins/offline/md5.js"></script> <script type="text/javascript" src="../../../../skins/offline/utf8.js"></script> <script type="text/javascript" src="../../../../skins/offline/lookup.js"></script> <script type="text/javascript" src="../../../../raw/gen.js"></script> <style type="text/css">/*<![CDATA[*/ @import "../../../../raw/MediaWiki%7ECommon.css"; @import "../../../../raw/MediaWiki%7EMonobook.css"; @import "../../../../raw/gen.css"; /*]]>*/</style> </head> <body class="ns-0"> <div id="globalWrapper"> <div id="column-content"> <div id="content"> <a name="top" id="contentTop"></a> <h1 class="firstHeading">Théorème de Hall</h1> <div id="bodyContent"> <h3 id="siteSub">Un article de Wikipédia, l'encyclopédie libre.</h3> <div id="contentSub"></div> <!-- start content --> <p>Le théorème de Hall donne une condition nécessaire et suffisante à l'existence d'un <i>couplage parfait</i> dans un <a href="../../../../articles/g/r/a/Graphe_biparti.html" title="Graphe biparti">graphe biparti</a> (un couplage parfait dans un <a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_graphes.html" title="Théorie des graphes">graphe</a> ayant un nombre pair <i>2n</i> de sommets est un sous-ensemble de <i>n</i> arêtes deux-à-deux disjointes du graphe, ainsi chaque sommet du graphe est incident à exactement une arête du couplage).</p> <dl> <dd>Théorème de Hall (1935) - <b>Un graphe biparti G=(U,V;E) admet un couplage parfait si et seulement si pour tout sous-ensemble X de U (de V, respectivement), le nombre de sommets de V (de U, respectivement) adjacents à un sommet de X est supérieur ou égal à la cardinalité de X</b>.</dd> </dl> <p>Ce résultat généralise le fait, déjà remarqué en 1914 par König, que les graphes bipartis <i>réguliers</i> (c'est-à-dire <i>k</i>-régulier pour un entier <i>k</i>, ceci voulant dire que chaque sommet du graphe est incident à exactement <i>k</i> arêtes) admettent un couplage parfait. Par-ailleurs, le théorème de Tutte généralise celui de Hall par une condition nécessaire et suffisante pour tous les graphes. Le Théorème de Hall est en fait un cas particulier du <a href="../../../../articles/t/h/%C3%A9/Th%C3%A9or%C3%A8me_flot-max_coupe-min_21c5.html" title="Théorème flot-max/coupe-min">Théorème flot-max/coupe-min</a>, dans les graphes consitués d'un graphe biparti G=(U,V;E) plus un sommet source et un sommet puits, la source étant relié à tous les sommmets de U tandis que tous les sommets de V sont reliés au sommet puits.</p> <p>Le Théorème de Hall n'est pas difficile à montrer (il en existe au-moins trois courtes preuves voir les références).</p> <p>L'intérêt (a posteriori) du théorème est de fournir un problème de décision dans <a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_de_la_complexit%C3%A9.html" title="Théorie de la complexité">NP</a>, en l'occurrence déterminer si un graphe admet ou non un couplage parfait, qui est à la fois dans <a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_de_la_complexit%C3%A9.html" title="Théorie de la complexité">co-NP</a>, puisqu'à l'aide d'un ensemble X violant la condition, on peut vérifier en temps polynomial que son voisinage N(X) est tel que |N(X)|<|X|, et donc convaincre que la réponse au problème de décision est négative.</p> <p><a name="R.C3.A9f.C3.A9rences" id="R.C3.A9f.C3.A9rences"></a></p> <h2><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9or%C3%A8me_de_Hall_9116.html" title="Modifier la section : Références">modifier</a>]</span> <span class="mw-headline">Références</span></h2> <p><i>Graph Theory with Applications</i>, J.A. Bondy and U.S.R. Murty, pour l'usage personnel libre sur <a href="http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html" class="external free" title="http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html" rel="nofollow">http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html</a></p> <p><i>Graph Theory</i>, de Reinhard Diestel, libre en version électronique à <a href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.counted.pdf" class="external free" title="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.counted.pdf" rel="nofollow">http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.counted.pdf</a>).</p> <!-- NewPP limit report Preprocessor node count: 2/1000000 Post-expand include size: 0/2048000 bytes Template argument size: 0/2048000 bytes Expensive parser function count: 0/500 --> <div class="printfooter"> </div> <div id="catlinks"><div id='catlinks' class='catlinks'><div id="mw-normal-catlinks"><a href="../../../../articles/a/c/c/Cat%C3%A9gorie%7EAccueil_1aae.html" title="Catégorie:Accueil">Catégorie</a> : <span dir='ltr'><a href="../../../../articles/t/h/%C3%A9/Cat%C3%A9gorie%7ETh%C3%A9orie_des_graphes_90c2.html" title="Catégorie:Théorie des graphes">Théorie des graphes</a></span></div></div></div> <!-- end content --> <div class="visualClear"></div> </div> </div> </div> <div id="column-one"> <div id="p-cactions" class="portlet"> <h5>Views</h5> <ul> <li id="ca-nstab-main" class="selected" ><a href="../../../../articles/t/h/%C3%A9/Th%C3%A9or%C3%A8me_de_Hall_9116.html">Article</a></li><li id="ca-talk" class="new" ><a href="../../../../articles/t/h/%C3%A9/Discuter%7ETh%C3%A9or%C3%A8me_de_Hall_990b.html">Discussion</a></li><li id="ca-current" ><a href="http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Hall">Version actuelle</a></li> </ul> </div> <div class="portlet" id="p-logo"> <a style="background-image: url(../../../../misc/Wiki.png);" href="../../../../index.html" title="Accueil"></a> </div> <script type="text/javascript"> if (window.isMSIE55) fixalpha(); </script> <div class='portlet' id='p-navigation'> <h5>Navigation</h5> <div class='pBody'> <ul> <li id="n-mainpage"><a href="../../../../index.html">Accueil</a></li> <li id="n-thema"><a href="../../../../articles/a/c/c/Portail%7EAccueil_bcc9.html">Portails thématiques</a></li> <li id="n-alphindex"><a href="../../../../articles/t/o/u/Special%7EToutes_les_pages_fabc.html">Index alphabétique</a></li> <li id="n-randompage"><a href="../../../../articles/p/a/g/Special%7EPage_au_hasard_9c81.html">Un article au hasard</a></li> <li id="n-contact"><a href="../../../../articles/c/o/n/Wikip%C3%A9dia%7EContact_929e.html">Contacter Wikipédia</a></li> </ul> </div> </div> <div class='portlet' id='p-Contribuer'> <h5>Contribuer</h5> <div class='pBody'> <ul> <li id="n-help"><a href="../../../../articles/s/o/m/Aide%7ESommaire_c9f0.html">Aide</a></li> <li id="n-portal"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_5272.html">Communauté</a></li> <li id="n-recentchanges"><a href="../../../../articles/m/o/d/Special%7EModifications_r%C3%A9centes_b222.html">Modifications récentes</a></li> <li id="n-aboutwp"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_des_nouveaux_arrivants_0784.html">Accueil des nouveaux arrivants</a></li> <li id="n-sitesupport"><a href="http://meta.wikimedia.org/wiki/Faire_un_don:_explication">Faire un don</a></li> </ul> </div> </div> <div id="p-search" class="portlet"> <h5><label for="searchInput">Rechercher</label></h5> <div id="searchBody" class="pBody"> <form action="javascript:goToStatic(3)" id="searchform"><div> <input id="searchInput" name="search" type="text" accesskey="C" value="" /> <input type='submit' name="go" class="searchButton" id="searchGoButton" value="Aller" /> </div></form> </div> </div> </div><!-- end of the left (by default at least) column --> <div class="visualClear"></div> <div id="footer"> <div id="f-poweredbyico"><a href="http://www.mediawiki.org/"><img src="../../../../skins/common/images/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" /></a></div> <div id="f-copyrightico"><a href="http://wikimediafoundation.org/"><img src="../../../../misc/wikimedia-button.png" border="0" alt="Wikimedia Foundation"/></a></div> <ul id="f-list"> <li id="f-credits">Cette page a été modifiée pour la dernière fois le 3 mars 2008 à 14:51 par Utilisateur(s) non enregistré(s) de Wikipédia. Basé sur le travail de Utilisateur(s) <a href="../../../../articles/t/o/u/Utilisateur%7ETou_chti_0b19.html" title="Utilisateur:Tou chti">Tou chti</a>.</li> <li id="f-copyright"><span style="white-space:normal"><a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Droit_d'auteur" title="Droit d'auteur">Droit d'auteur</a> : Tous les textes sont disponibles sous les termes de la <a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Licence_de_documentation_libre_GNU" title="GFDL">licence de documentation libre GNU</a> (GFDL).<br/> Wikipedia® est une marque déposée de la <a href="http://wikimediafoundation.org/wiki/Accueil" title="Wikimedia Foundation">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a class="internal" href="http://en.wikipedia.org/wiki/501(c)" title="501(c)">501(c)(3)</a> du code fiscal des États-Unis.</span><br/></li> <li id="f-about"><a href="../../../../articles/%C3%A0/_/p/Wikip%C3%A9dia%7E%C3%80_propos_5de1.html" title="Wikipédia:À propos">À propos de Wikipédia</a></li> <li id="f-disclaimer"><a href="../../../../articles/a/v/e/Wikip%C3%A9dia%7EAvertissements_g%C3%A9n%C3%A9raux_fef1.html" title="Wikipédia:Avertissements généraux">Avertissements</a></li> </ul> </div> </div> </body> </html>