We study the minimal spanning trees of a connected graph G = (X, U) where U is partially preordered (or quasi-ordered). We characterize several kinds of optimal spanning trees and give conditions for existence of strongl3,' optimal tress. Generalizations to ba~s of matro'ids (binary matro'ids in part 2) are immediate. Some of our results are given in terms of Krogdahi's dependance graphs. Thcy imply previous results of Rosenstiehl and Gale in the ca.~ of linear orders or pr,:orders. On 6tudie les arbres minimaux d'un grapb.e conne~e G = (X, U), oh U e.st partiellemenl pre3c, rdonn~.. On caract6rise diverses sortes d'arbres ol~timaux et on donne des conditions d't;xistence des arbres fortement optimaux. Des g6ngralisations aux bases de matro'ides (matroides bi',,~;;,:~ dans la pattie 2) sont immgdiates. Certains de nos r~sultats utilisent les graphes de dO'. ...zce de Krogdahl. lls impliquent des r~sultats de Ro~enstiehl et de Gale dans les cas โข : .cs el de prgordres totaux. 0. ln~'oductlon L'arbre minimum d'un graphe dont les arStes sont valu6es par des nombres r6eis positifs est l'un des objets combinatoires les mieux connus. Son 6tude, commenc6e sans doute par Boruvka [2], a 6tabli l'int6r6t de ses nombreuses propd6t6s et s'est pr6.*6e ?l d'importantes g6t16ralisations: l'algorithme A de Kruskal [11] a 6t6 le premier exemple d'algorithme glouton. En pratique, l'arbre minimum joue un r61e important en recherche op6rationnelle et en taxonomic math6matique.
C'est ~ propos de cette derni~re, utilis6e darts les sciences sociales o~ l'on est fr6quemment amen6 5 consid6rer des variables non num6riques, que nous nous sommes int6,ress6 au cas o/a il peut y avoir des paires d'ar6tes incomparables, c'est-h-dire o/a l'ensemble U des ar6tes du graphe G consid6r6 est muni d'un pr6ordre P quelconque, non forc6ment total. L'int6r6t du probli~me est aussi apparu dans des contextes plus th~oriques: Flament [5, 6] a caract6ris6 les families de sous-arbres d'un arbre par l'existence d'un arbre minimum dans un certain graphe (partiellement) pr6ordonn6.