Résumé | J'examine dans quelle mesure il est possible de définir en logique du second ordre monadique, pour un graphe non orienté: une orientation, toutes les orientations, un ordre total.
Les réponses ne sont pas les mêmes avec ou sans quantifications sur les ensembles d'arêtes. Je mets en évidence des conditions combinatoires qui rendent ces définitions possibles. Certains résultats sont obtenus avec A. Blumensath. |