Calcul d'invariants dans les graphes et ordres
Loading...
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universite Mouloud MAMMERI Tizi-Ouzou
Abstract
L'intitulé de la thèse est " calcul d'invariant dans les graphes et ordres ". 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. tous les ordres) qui sont isomorphes. Deux graphes ou deux ordres sont isomorphes lorsqu'il existe une bijection entre leurs ensembles d'éléments conservant les relations d'adjacences et de comparabilités respectivement.Nous nous sommes intéresses à l'étude des problèmes suivant : 1.Problème de décomposition d'un graphe biparti en bicliques :en utilisant le parcours en largeur lexicographique (LexBFS), nous avons proposé d'abord un algorithme linéaire pour la reconnaissance de la classe des graphes bipartis distance héréditaire, ensuit nous avons proposé 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. 2.Problème de chaine déviation d'un ordre :ilest défini comme suit: pour un poset" P ", on définit récursivement une suite d'ordres " (Qn)n "en posant " Q0=P " et pour " n>0 "," Qn " est l'ordre strict bien précis sur les antichaines maximales de l'ordre " Qn-1 ". Il est bien connu que cette séquence ainsi définie converge vers un ordre total après un nombre fini d'itérations. Nous avons calculé le nombre exacte d'itérations au bout desquels cet ordre total est atteint sans passer par le calcul explicite des termes de la suite. 3.Problème de P-couplage : il consiste en la généralisation de la notion du couplage comme suit: soient un ordre " P=(E,<) ",un graphe biparti " G=(X,Y,E') " tels que " |E|=|E'| " et une bijection " f " allant de " E " dans " E' ". Un P-couplage est un ensemble d'arrêtes " M " dans " G " tel que pour toute antichaine maximale " A " de " P ", la restriction de " f(A) " sur " M " est un couplage. Il s'agit de trouver un P-couplage avec un maximum possible d'arrêtes. Nous avons donné une caractérisation de cette notion de P-couplage et nous avons donné quelques classes de graphes et ordres pour lesquels ce problème est polynomial.
Description
96f. : ill. ; 30 cm. + CD Rom
Keywords
Calcul d'invariants, Graphe biparti : décomposition, Chaine maximale
Citation
Recherche Opérationnelle