Relations entre la théorie de la programmation linéaire et l'optimisation combinatoire / Zemirline, Abdallah (1987) 

Public ISBD Titre : Relations entre la théorie de la programmation linéaire et l'optimisation combinatoire Type de document : texte imprimé Auteurs : Zemirline, Abdallah, Auteur ; Fonlupt, Jean, Directeur de thèse Editeur : Bab Ezzouar : [s.n.] Année de publication : 1987 Importance : 119 f. Présentation : ill. Format : 27 cm. Note générale : Thèse d’État : Mathématiques Appliquées : Alger, Université des Sciences et de la Technologie Houari Boumedienne : 1987 Bibliogr. - Annexe [12] f Langues : Français (fre) Mots-clés : Recherche opérationnelle Programmation linéaire Optimisation combinatoire Graphes parfaits Algorithme polynomial Matroïdes Index. décimale : D000687 Résumé : Dans cette thèse deux problèmes d'Optimisation Combinatoire de natures différentes sont étudiés. Ils rendent bien compte, l'un et l'autre, des aspects principaux des relations liant la théorie de la Programmation Linéaire et l'Optimisation Combinatoire. Le premier problème a trait aux Graphes Parfaits. Il s'agit de prouver que le problème de reconnaissance de la classe des graphes parfaits sans K4/{e} est polynômial (K4/{e} étant la clique d'ordre 4 moins une arête). Le second problème concerne l'intersection de deux matroïdes. Etant données deux matroïdes simples M1=(E, F1) et M2=(E, F2) définis sur un même ensemble E, et ayant une base commune, il s'agit de trouver une borne inférieure du nombre de bases communes à M1 et M2. L'objet de cette première partie de thèse est d'élaborer un algorithme polynomial de reconnaissance des graphes parfaits sans K4/(e). Les graphes sans K4/(e) sont par définition les graphes qui ne contiennent pas comme sous graphe induit le graphe K4/(e) obtenu à partir de la clique K4 par suppression d'une arête. Nous résolvons ce problème de reconnaissance en procédant en deux étapes: Dans le chapitre 2, nous établissons d'abord le résultat pour graphes sans K4/(e) et sans K4. Dans le chapitre 3, nous l'étendons aux graphes sans K4/(e). L'autre aspect des relations entre la théorie de la programmation linéaire et l'optimisation combinatoire, abordé dans cette thèse, constitue l'objet du chapitre 5. Il consiste à déterminer la dimension du polyèdre dont les points extrêmes représentent les bases communes à deux matroïdes, pour en déduire des résultats purement combinatoires relatifs au nombre de bases communes à deux matroïdes. Les chapitres 1 et 4 sont une introduction respectivement aux Graphes Parfaits et aux Matroïdes. On y trouve également quelques notations et définitions usuelles. Relations entre la théorie de la programmation linéaire et l'optimisation combinatoire [texte imprimé] / Zemirline, Abdallah, Auteur ; Fonlupt, Jean, Directeur de thèse . - Bab Ezzouar : [s.n.], 1987 . - 119 f. : ill. ; 27 cm. Thèse d’État : Mathématiques Appliquées : Alger, Université des Sciences et de la Technologie Houari Boumedienne : 1987 Bibliogr. - Annexe [12] f Langues : Français (fre) Mots-clés : Recherche opérationnelle Programmation linéaire Optimisation combinatoire Graphes parfaits Algorithme polynomial Matroïdes Index. décimale : D000687 Résumé : Dans cette thèse deux problèmes d'Optimisation Combinatoire de natures différentes sont étudiés. Ils rendent bien compte, l'un et l'autre, des aspects principaux des relations liant la théorie de la Programmation Linéaire et l'Optimisation Combinatoire. Le premier problème a trait aux Graphes Parfaits. Il s'agit de prouver que le problème de reconnaissance de la classe des graphes parfaits sans K4/{e} est polynômial (K4/{e} étant la clique d'ordre 4 moins une arête). Le second problème concerne l'intersection de deux matroïdes. Etant données deux matroïdes simples M1=(E, F1) et M2=(E, F2) définis sur un même ensemble E, et ayant une base commune, il s'agit de trouver une borne inférieure du nombre de bases communes à M1 et M2. L'objet de cette première partie de thèse est d'élaborer un algorithme polynomial de reconnaissance des graphes parfaits sans K4/(e). Les graphes sans K4/(e) sont par définition les graphes qui ne contiennent pas comme sous graphe induit le graphe K4/(e) obtenu à partir de la clique K4 par suppression d'une arête. Nous résolvons ce problème de reconnaissance en procédant en deux étapes: Dans le chapitre 2, nous établissons d'abord le résultat pour graphes sans K4/(e) et sans K4. Dans le chapitre 3, nous l'étendons aux graphes sans K4/(e). L'autre aspect des relations entre la théorie de la programmation linéaire et l'optimisation combinatoire, abordé dans cette thèse, constitue l'objet du chapitre 5. Il consiste à déterminer la dimension du polyèdre dont les points extrêmes représentent les bases communes à deux matroïdes, pour en déduire des résultats purement combinatoires relatifs au nombre de bases communes à deux matroïdes. Les chapitres 1 et 4 sont une introduction respectivement aux Graphes Parfaits et aux Matroïdes. On y trouve également quelques notations et définitions usuelles.

Réservation

Réserver ce document

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité	Spécialité	Etat_Exemplaire
D000687	D000687	Papier + ressource électronique	Bibliothèque Annexe	Thèse de Doctorat	Disponible	Autre	Consultation sur place/Téléchargeable

Documents numériques

ZEMIRLINE.Abdallah.pdf URL