Spelling suggestions: "subject:"digraphes"" "subject:"bigraphes""
411 |
Modélisation des réseaux de transport collectifs métropolitains vers la structuration territoriale des réseaux. Applications au Nord-Pas-de-Calais et à Provence-Alpes-Côte d'AzurConesa, Alexis 11 March 2010 (has links) (PDF)
On considère la métropolisation comme un ensemble de processus, qui, depuis les années 1980, bouleversent les rapports des sociétés à leurs territoires. En particulier, ces changements ont réinterrogé le rôle du transport comme outil d‟aménagement du territoire. Les réseaux de transport présentent ainsi des aptitudes à structurer les territoires métropolitains, en permettant un fonctionnement des lieux en interaction et une appropriation de la part des individus et des sociétés qui les gèrent et les utilisent. L‟objectif de cette recherche est de construire un outil d‟aide à la décision en aménagement du territoire et politique des transports qui puisse rendre compte du potentiel que les réseaux de transports offrent à la structuration du territoire métropolitain. Dans l‟esprit de proposer une alternative au tout-automobile, le travail se concentre sur les réseaux de transport collectif. Concrètement, une démarche modélisatrice est menée et mobilise les notions d‟accessibilité et de capillarité, qui font l‟objet de mesures chiffrées. Ces indicateurs peuvent informer les décideurs sur les qualités des réseaux de transport étudiés. L‟application est menée sur les réseaux de transport collectifs des régions Nord-Pas-de-Calais et Provence-Alpes-Côte d‟Azur. Les analyses mettent en relief certains dysfonctionnements, c‟est pour y remédier que des projets d‟aménagement en matière de transport ont été simulés dans chacune des régions. Les résultats montrent comment les réseaux de transport collectif peuvent favoriser une construction métropolitaine, mais aussi leurs limites. En effet, la thèse plaide pour une conception coordonnée des politiques de transport et d‟aménagement.
|
412 |
Réseaux géométriques aléatoires : Connexité et comparaisonYogeshwaran, D. 24 November 2010 (has links) (PDF)
Cette thèse porte sur deux thèmes : 1)Percolation et connexité sur les graphes géométriques aléatoires dits "type AB". 2)Comparaison stochastique directionnellement convexe de processus ponctuels et leurs propriétés de percolation et connexité. Dans le premier sujet, nous définissons un graphe biparti, dit "de type AB", sur deux processus ponctuels de Poisson indépendants. Cet graphe est une extension continue de graphe dit "type AB" sur une grille régulière. Nous montrons l'existence de percolation pour toute dimension supérieure à deux et nous établissons des bornes pour l'intensité critique. Dans le cas de dimensions deux, nous caractérisons exactement l'intensité critique. Pour le problème de connexité, nous étudions le modelé sur les processus ponctuels de Poisson indépendant dans le cube de volume un avec des intensités n et c_n pour une constante c > 0. Nous établissons des bornes asymptotiques presque sûres pour le seuil de connexité. 2) Le but du deuxième sujet de travail est de définir l'ordre directionnellement convexe de processus ponctuels est de lier cet ordre aux propriétés de regroupement des points de processus ponctuels et, dans un contexte applicatif, aux caractéristiques de la performance des réseaux de communication sans fil. La dernière partie de cette thèse porte sur la comparaison des intensités critiques de percolation pour les processus ponctuels ordonnés selon cet ordre et les applications de ces résultats de comparaison pour les réseaux sans fils. Nous concluons en montrant que les processus ponctuels inférieurs, selon cet ordre, à un processus ponctuel de Poisson ont une transition de phase non-triviale dans plusieurs modelés des percolation.
|
413 |
Imagerie par résonance magnétique du tenseur de diffusion (IRM-TD) en imagerie cardiaque humaine : traitements et premi`eres interprétationsFrindel, Carole 04 December 2009 (has links) (PDF)
Cette thèse a pour cadre l'étude de l'organisation spatiale des fibres du muscle cardiaque à partir de séries d'images tridimensionnelles acquises par IRM du Tenseur de Diffusion (IRMTD). Cette organisation constitue une propriété fondamentale du coeur sous-tendant la fonction contractile. Néanmoins elle est très complexe à obtenir au vu des difficultés inhérentes au mouvements cardiaque et respiratoire. Notre objectif consiste à développer de nouvelles approches, basées sur la prise en compte du mouvement du coeur et de la sensibilité au bruit de l'acquisition, pour l'estimation, l'analyse et la visualisation des fibres du myocarde. Dans ce cadre, mes travaux se déclinent selon trois axes principaux. Le premier compare, dans le contexte d'études cliniques ex vivo, les principales approches de régularisation opérant soit sur les images pondérées en diffusion soit sur les champs de tenseurs de diffusion. Les différences sont suffisamment faibles pour conclure que la qualité de nos données IRMTD est suffisante pour considérer toutes les méthodes de régularisation comme équivalentes. Partant de ce constat, une méthode de régularisation simple et rapide apparaî satisfaisante. Le second concerne la mise en place d'une méthode de tractographie spécialement conçue pour la spécificité cardiaque. Celle-ci est guidée par une fonctionnelle de coût globale qui permet l'estimation automatique des fibres cardiaques en une seule fois pour l'ensemble des données, et ce sans l'utilisation de points d'initialisation. Le dernier axe consiste en la distinction d'une population de fibres cardiaques en sous-groupes. Celle-ci s'appuie sur la comparaison de méthodes de classification de type géométrique et de type topologique exploitant toutes trois modes différents de représentation des fibres. Les résultats établissent que la classification pourrait permettre l'identification automatique de régions spécialisées dans le myocarde, ce qui pourrait grandement faciliter l'analyse et la comparaison des données IRMTD cardiaques pour la conception de thérapies patient-spécifiques.
|
414 |
Aspects algorithmiques d'heuristiques de coloration de graphesSampaio, Leonardo 19 November 2012 (has links) (PDF)
Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.
|
415 |
Synthèse de réseaux à composantes connexes unicycliquesHadji, Makhlouf 24 September 2009 (has links) (PDF)
Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. Mots clés : Optimisation Combinatoire, Polyèdres, Algorithme à Plans Coupants, Graphes
|
416 |
Graphes et couleurs : graphes arêtes-coloriés, coloration d'arêtes et connexité propreMontero, Leandro Pedro 13 December 2012 (has links) (PDF)
Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.
|
417 |
Outils d'aide à la décision pour la conception en avant-projet des systèmes d'usinage à boîtiers multibrochesGuschinskaya, Olga 27 November 2007 (has links) (PDF)
Les travaux de recherche effectués dans le cadre de cette thèse concernent essentiellement la conception en avant-projet de systèmes d'usinage dédiés à la production en grande série. Lors de cette phase de conception, l'objectif principal est de trouver, pour une pièce donnée, une configuration du système d'usinage qui satisfaisait, à coût minimal, les contraintes technologiques, techniques et économiques existantes. Plusieurs problèmes combinatoires posés par cet objectif sont étudiés dans la thèse. Plus concrètement, nous nous sommes intéressés aux problèmes d'optimisation de la configuration des trois types de systèmes d'usinage suivants : machines de transfert, machines à table mobile et machines à table circulaire pivotante. Pour chacun de ces systèmes, nous avons proposé, dans un premier temps, différents modèles mathématiques. Dans un deuxième temps, nous avons développé de nombreux outils d'optimisation dédiés à leur résolution, tels que des algorithmes de calcul des bornes inférieures, des procédures de pré-traitement, des algorithmes de résolution exacte et approchée, et des approches mixtes utilisant plusieurs de ces algorithmes. Ces travaux ont permis de concevoir un prototype de logiciel destiné à supporter les différentes étapes de conception en avant projet d'un système d'usinage. Ce logiciel a été testé avec succès sur plusieurs cas industriels.
|
418 |
Applications et services DTN pour flotte collaborative de dronesLaplace, Rémi 20 December 2012 (has links) (PDF)
Les travaux présentés dans cette thèse effectuée au LaBRI portent sur la mise en place d'une flotte de drones et le portage sur celle-ci d'applications collaboratives distribuées utilisant des communications asynchrones non sûres. Ces applications sont formalisées grâce au modèle de réétiquetage de graphes Asynchronous Dynamicity Aware Graph Relabeling System (ADAGRS) que nous proposons. Au delà des contributions théoriques, ces travaux ont débouché sur la mise en place du démonstrateur CARUS dans lequel cinq drones se partagent la surveillance d'une grille de 15 points d'incidents potentiels (au sol). Lorsqu'un drone détecte un incident, il s'en rapproche pour le traiter. Le reste de la flotte doit alors prendre en charge les points que ce drone ne traite plus.Les réorganisations nécessaires de la flotte se font en totale autonomie vis-à-vis du sol et sous hypothèse de perte éventuelle de drones et de messages.
|
419 |
Les réseaux techniques comme vecteur de propagation des risques en milieu urbain - Une contribution théorique et pratique à l'analyse de la résilience urbaineLhomme, Serge 03 December 2012 (has links) (PDF)
Les réseaux techniques sont des infrastructures critiques qui peuvent être vulnérables aux inondations. Leur bon fonctionnement représente donc un enjeu majeur pour la gestion des risques et des territoires. Cette recherche postule que l'analyse de la résilience des réseaux techniques constitue un préalable nécessaire, mais non suffisant, à la mise en place de politiques d'amélioration de la résilience urbaine face aux inondations. Une méthodologie d'analyse de la résilience des réseaux techniques est proposée. Elle requiert l'analyse des capacités de résistance, d'absorption et de récupération de ces réseaux. Dans ce cadre, des développements ont été réalisés afin d'analyser les propriétés structurelles des réseaux techniques, les interdépendances entre les réseaux techniques et la remise en service de ces réseaux. Ces développements reposent principalement sur la théorie des graphes, les méthodes issues de la Sûreté de Fonctionnement, l'optimisation linéaire et l'analyse spatiale. Enfin, un prototype web-SIG a été développé puis appliqué à la ville de Dublin.
|
420 |
Contribution des sous-ensembles flous à l'aide à la décision et à l'analyse structuraleSagaama, Sadok 11 July 1977 (has links) (PDF)
On se propose, dans cette étude, de montrer l'apport nouveau de la théorie des sous-ensembles flous dans le domaine de l'analyse de la décision. Dans un premier temps, on la démarque de celle des probabilités, et des probabilités subjectives en particulier, puis on étudie certaines applications des sous-ensembles flous a la prise de décision et a l'analyse structurale. On discute, ensuite, l'opportunité de l'emploi des opérateurs min et max, dans le cas d'une décision floue. Puis on présente une méthode topologique de la construction de la fonction d'appartenance. On présente ensuite une méthode d'analyse structurale basée sur des techniques floues, au lieu de la théorie des graphes, puis on étudie l'entropie floue et on la compare à l'entropie probabiliste au sens de Shannon.
|
Page generated in 0.0437 seconds