Calcul d'invariants dans les graphes et ordres

الموضوعات

علوم اللغة

الملخص

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.

روابط وملفات

التعريف والنوع

رقم الوثيقة

f335df1c-714c-4d31-af86-02c629d4c4ce

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل دكتوراة

نوع الملف

pdf text

أسماء الملفات

782893_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":"Bachir sadi","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Djamel Talem","title_ar":"اعداد","title_en":"Preparation"}]

اللغة

French

المصدر والدورية

اسم المصدر

Calcul d'invariants dans les graphes et ordres

المحتوى والصفحات

عدد الصفحات

0

كلمات الباحثين

Chaine maximale

إشراف وإعداد

الإشراف

Bachir sadi

الإعداد

Djamel Talem

الاقتباسات الببليوغرافية