Avis de soutenance de Doctorat en Mathématiques de Mr. TALEM Djamel

Dans cette thèse, nous nous intéressons au calcul des invariants suivants : décompo-sition minimum d’un graphe biparti en bicliques, chaine déviation d’un ensemble partiellement ordonné (poset) et P-couplage. Les invariants de graphes (resp.  des ordres) sont des paramètres qui caractérisent les graphes (resp.  les ordres) et dont la valeur est la même pour tous les graphes (resp.  les ordres) qui sont isomorphes. La formulation des problèmes de calcul des invariants est souvent facile, mais leurs résolution est, en générale, loin d’être pareille. En effet, les situations où nous disposons d’algorithmes « efficaces »  pour les résoudre sont limitées, dans les plus parts des cas un tel algorithme n’existe pas (ou du moins, la communauté scientifique s’accorde à penser qu’il n’existe pas), c’est le cas pour les problèmes du stable maximum, de la coloration minimum, de la dimension d’un poset, de la couverture minimum des sommets et d’un ensemble dominant minimum, etc. Nos contributions sont résumées comme suit:

Le problème de la décomposition d’un graphe biparti en bicliques est aussi connu pour être difficile en générale. En utilisant le parcours en largeur lexicographique, nous proposons d’abord un algorithme linéaire pour la reconnaissance de la classe des graphes biparti distance héréditaire, nous proposons aussi des algorithmes linéaires pour calculer une biclique maximum, une partition minimum des arêtes en biclique et une couverture minimum des sommets en bicliques pour la même classe de graphes.

Le problème de la chaine déviation d’un ensemble partiellement ordonné, introduit par Kong et Ribemboin en 1984, est définit comme suit : pour un ensemble partiellement ordonné « P », « (D^i(P))_i>0 » est une suite d’ensembles partiellement ordonnés  définie à partir de « P » d’une manière récursive, où « P=D⁰(P) » et pour  « 0<i, Dⁱ(P) » est l’ordre strict sur les antichaines maximales de l’ordre D^i-1 (P).  Les mêmes auteurs ont montré que cette séquence ainsi définie converge vers un ordre total après un nombre fini d’itérations. La notation « cdev(P) » désigne le plus petit entier naturel pour lequel D^cdev(P) (P) est une chaine. Pour un ordre P qui n’est, ni antichaine ni somme linéaire d’autres ordres, nous montrons que la valeur du paramètre « cdev(P) » est la distance dans le graphe « Inc(P) », graphe d’incomparabilité de « P », entre deux sommets additionnels « 0p » et « 1_P », où « 0_P » adjacent à tous les éléments minimaux de « P » et « 1_P » adjacent à tous les éléments maximaux de « P ». Nous donnons aussi sa valeur pour les deux cas particuliers cités ci-dessus. Enfin, nous montrons que « cdev » est un invariant de comparabilité, c’est-à-dire les posets ayant un même graphe de comparabilité ont le même « cdev ».

Quant au problème du « P –couplage », il consiste en la généralisation de la notion du couplage comme suit: étant donné un ordre « P=(E,_P) », un graphe biparti « G=(X,Y,E’) » tels que « |E|=|E’| » et une bijection « f:E⟶ E’ ». Un « P-couplage » dans « G » est un ensemble d’arêtes « M » vérifiant « f(A)∩ M » est un couplage pour toute antichaine de « P ». Le problème est de trouver un « P-couplage » avec un maximum d’arêtes. La complexité de ce problème est inconnue à l’heure actuelle. Nous donnons une condition nécessaire et suffisante pour qu’un ensemble d’arêtes soit un « P-couplage », et nous montrons comment calculer efficacement un « P-couplage » maximum pour quelques classes de ordres et de graphes très particulières.

Mots Clés : Ensemble partiellement ordonné, Décomposition d’un graphe biparti en bicliques, Biclique maximale, Chaine maximale, Antichaine maximale.