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).
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 :
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).
Retour à la page des sujets.