Méta-théorèmes.

Il s'agit ici de discuter autour des 4 "méta-théorèmes" ci-dessous. Attention, ce sont plus des principes généraux que de vrais théorèmes. On y compare les différentes versions d'un même théorème ou d'un même problème algorithmique (on indique entre parenthèses s'il est question de graphes non orientés ou orientés ou les deux).

• Méta-théorème 1 : les versions "arêtes" (resp. "arcs") sont plus faciles que les versions "sommets"  (graphes non orienté, resp. orientés).
  
• Méta-théorème 2 : les versions "non orienté" sont plus faciles que les versions "orienté" (graphes non orientés versus orientés).
• Méta-théorème 3 : les versions "graphe biparti" sont aussi difficiles que les versions "graphe quelconque" (graphes non orientés).
• Méta-théorème 4 : les versions "graphe sans cycle" sont plus faciles que les versions "graphe quelconque" (graphes orientés).
  

Votre objectif est d'illustrer et/ou réfuter la validité de ces méta-théorèmes. Pour les illustrer, vous pouvez choisir des exemples particuliers en déclinant chacune des versions et en montrant qu'une version est effectivement plus facile qu'une autre. Vous pouvez aussi donner des arguments plus généraux : par exemple en exhibant des transformations de graphes vous permettant de ramener une version à l'autre version dans de nombreux cas, si bien que si on sait résoudre l'autre version on sait  aussi résoudre la version initiale.

Voilà quelques exemples d'illustrations ou de questions qui entrent dans le cadre du sujet :

• Pour les graphes non orientés, concernant la k-connexité entre deux sommets x et y, il existe un théorème de Menger avec une version où on veut déconnecter x et y en enlevant des sommets et une autre version en enlevant des arêtes. Est-il possible de déduire facilement la version "arêtes" de la version "sommets" ?  Et inversement ? Et dans le cas orienté ?
• Est-ce qu'il existe une transformation simple permettant de voir un graphe non orienté comme un graphe  orienté  particulier ? Est-ce qu'elle permet de résoudre certains problèmes du cas non orienté à partir de la solution pour le cas orienté ? Y a-t-il des contre-exemples au méta-théorème 2 ?
• Parmi les problèmes que vous connaissez sur les graphes non orientés, par exemple des problèmes d'optimisation, sont-ils en général strictement plus facile dans le cas biparti que dans le cas quelconque ? ou bien sont-ils aussi difficiles dans le cas biparti que dans le cas quelconque ?
  
• Dans un graphe orienté, est-il beaucoup plus facile de trouver un chemin de longueur maximum dans un graphe sans cycle que dans un graphe quelconque ?
  

A vous de trouver autant d'exemples, contre-exemples, transformations, que vous le souhaitez afin d'argumenter en faveur ou contre les affirmations de ces "méta-théorèmes". S'il vous vient d'autres idées de "méta-théorèmes", vous pouvez les proposer en essayant de les étayer le mieux possible.

Quelques références (pas exhaustif).

• Introduction to Graph Theory, livre de D. West, Prentice Hall (2001).
• Digraphs: theory, algorithms and applications, livre de J. Bang-Jensen et G. Gutin, Springer (2002).

Retour à la page des sujets.