Spelling suggestions: "subject:"degré"" "subject:"segré""
51 |
Computational and Mathematical Methods for Data Analysis in Biology and Finance / Méthodes mathématiques et computationnelles pour l'analyse de données en biologie et en financeRiposo, Julien 17 September 2015 (has links)
Les mathématiques sont comprises en tant qu’ensemble d’idées abstraites, dans le sens où le monde réel – ou plutôt réalité – n’a pas à intervenir. Pourtant, certains faits mathématiques observables dans des données expérimentales ou simulées peuvent être contre-intuitifs. La thèse est divisée en deux parties : premièrement, on étudie mathématiquement les matrices du genre celles dont nous avons discutées en biologie et finance. En particulier, nous mettons en évidence le fait contre-intuitif suivant : pour ces matrices, le vecteur propre associé à la plus haute valeur propre est très proche de la somme de chacune des lignes de la matrice, colonne par colonne. Nous discutons aussi d’applications en théorie des graphes avec bon nombre de simulations numériques. Dans un second temps, nous attaquons le problème des contacts géniques : à partir d’une carte de contact génique, un vrai défi actuel est de retrouver la structure tridimensionnelle de l’ADN. Nous proposons diverses méthodes d’analyse matricielle de données, dont une met en évidence l’existence, dans le noyau, de zones disjointes où les interactions sont de différents types. Ces zones sont des compartiments nucléaires. Avec d’autres données biologiques, nous mettons en évidence la fonction biologique de chacun de ces compartiments. Les outils d’analyses sont ceux utilisés en finance pour analyser des matrices d’auto-corrélation, ou même des séries temporelles. / Mathematics are understood as a set of abstract ideas, in the measure of the real world – or reality – has no way to intervene. However, some observable mathematical facts in experimental or simulated data can be counter-intuitive. The PhD is divided into two parts: first, we mathematically study the matrices of the same type of the ones in biology and finance. In particular, we show the following counter-intuitive fact: for these matrices, the eigenvector associated with the highest eigenvalue is close to the sum of each row, column by column. We also discuss some applications to graph theory with many numerical simulations and data analysis.On the other hand, we will face the genetic contact problem: from a contact map, a real current challenge is to find the DNA 3D-structure. We propose several matrix analysis methods, which one show disjoinct areas in the nucleus where the DNA interactions are different. These areas are nuclear compartments. With other biological features, we characterize the biological function of each of the compartments. The analysis tools are the ones already used in finance to analyze the autocorrelation matrices, or even time series.
|
52 |
De la variabilité du rapport des enseignants de l’école primaire à l’orthographe appréhendée comme une norme sociale : discours et pratiques / Variability in the relationships primary school teachers have to spelling analyzed as a social norm : speech and teaching practices.Combalier-Combaz-Champlaine, Catherine 23 November 2017 (has links)
Notre recherche étudie le rapport des enseignants de l’école primaire française à l’orthographe appréhendée comme une norme sociale à travers leurs propos déclaratifs et à travers leurs pratiques enseignantes. En France, l’orthographe revêt des enjeux sociaux d’importance. Si l’orthographe est un ensemble de règles provenant du système linguistique, elle est aussi une pratique sociale qui s’impose à tous les utilisateurs. Elle appartient dès lors aux normes culturelles d’une société donnée. C’est pourquoi, nous avons cherché à apprécier l’adhésion des maitres à cette norme et à savoir s’il existait, entre eux, une certaine variabilité dans cette adhésion. Pour ce faire, nous avons opérationnalisé le concept de norme sociale. Nous avons mené 30 entretiens semi-directifs auprès d’enseignants de CM1 et CM2. Leurs réponses ont été analysées grâce à une analyse de contenu thématique et à une analyse statistique. Cela a permis de dégager cinq profils ortho-normatifs qui témoignent d’une variabilité du rapport des maitres à cette norme sociale orthographique et d’établir une typologie. Puis, nous avons cherché à percevoir ces rapports ortho-normatifs lorsqu’ils enseignent en classe auprès de leurs élèves pour éprouver les propos de Jaurès « on n’enseigne pas ce que l’on sait ou ce que l’on croit savoir : on enseigne et on ne peut enseigner que ce que l’on est » et apprécier la présence de leurs logiques d’arrière-fond (Bucheton, 2011). Chaque enseignant montre sa façon singulière d’incarner son profil ortho-normatif et de rendre présente cette norme sociale lors d’une séance d’enseignement d’un point particulier du système linguistique. Ce faisant, il construit le curriculum caché des élèves. / Our research studies how French primary school teachers deal with spelling considered as a social norm through their declarative words as well as their teaching practices. In France, with spelling, important social issues are at stake. If spelling is a set of rules linked to the linguistic system, it is also a social practice which is imposed on all users. As such it belongs to the cultural norms of a given society. That’s why we tried to estimate teachers ’adhesion to this norm and see if there was a certain variability to it among them.In order to achieve this, we operationalized the concept of social norm. We led 30 semi-directive interviews with 4th and 5th year primary school teachers. Their answers were analyzed thanks to both a thematic content analysis and a statistical one. The result highlighted the existence of five “ortho-normative profiles” which shows a variability in the relationship teachers have to this social spelling norm and enabling us to establish a typology.Then, we tried to grasp these “ortho-normative relationships” when they teach in class to test Jaurès ‘s words : “we don’t teach what we know or what we think we know, we teach and can only teach what we are” and thus estimated their background logics (Bucheton, 2011). Each teacher showed his personal way to embody his own “ortho-normative profile” and made this social norm present during a teaching session of a particular point of the linguistic system. In doing so, he builds the pupils’hidden curriculum.
|
53 |
Une approche orientée utilisateur pour la supervision des orchestrations de servicesFakhfakh, Nabil 06 June 2012 (has links) (PDF)
La qualité de service est devenue aujourd'hui une notion incontournable dans le développement des applications logicielles, en particulier dans le cadre des architectures orientées services. Les travaux de cette thèse se focalisent sur la supervision de la qualité de service des applications orientées services, définies sous forme d'orchestrations de services. L'approche de supervision proposée dans ce contexte est générique. Elle repose sur des patrons de flux de contrôle des orchestrations de services pouvant être implémentés en intégralité ou en partie par tout langage d'orchestration de services. D'autre part, elle ne pose aucune restriction, ni sur les attributs qualité à surveiller par le système de supervision, ni sur leurs représentations. Cette approche de supervision se distingue des approches existantes par l'exploitation d'un modèle de préférences orienté utilisateur, permettant de représenter fidèlement la satisfaction de ce dernier. Le degré de satisfaction, issu du modèle de préférences, constitue une information de haut niveau représentant la qualité globale de l'orchestration étudiée. Sur la base de ce degré de satisfaction, de nouvelles stratégies de surveillance sont proposées afin de satisfaire les attentes de l'utilisateur. L'élaboration du modèle de préférences exploite la méthode d'aide à la décision multi-critères MACBETH étendue avec l'opérateur d'agrégation de l'intégrale de Choquet 2-additive. Une illustration de l'approche de supervision a été réalisée sur une orchestration de services, représentant un processus industriel dans le domaine du pilotage d'atelier de production. Les travaux de cette thèse ont été réalisés dans le cadre d'un projet R&D regroupant sept éditeurs de progiciels dans le domaine du MES (Manufacturing Execution System).
|
54 |
Travail en mode projet distribué géographiquement : mesure des compétences, de la collaboration et des performances individuelles selon le degré de virtualitéLacasse, Caroline 09 1900 (has links)
Dans un contexte où le monde du travail s’internationalise et où l’innovation est fondamentale, les organisations d’aujourd’hui doivent structurer le travail en tenant compte des distances géographiques et du besoin de bien performer dans les tâches reliées aux différents projets. Toutefois, le recours à des projets innovants et l’accès à des moyens de communication ne sont pas des conditions suffisantes pour assurer une performance adéquate. Différents facteurs, comme les compétences adaptées au travail virtuel et le degré de virtualité qui sépare les gens, doivent être pris en compte pour favoriser l’atteinte d’une bonne performance. De plus, afin de sélectionner les candidats qui seront en mesure de bien performer dans ce contexte, le recours à des outils d’évaluation appropriés et disponibles dans plusieurs langues est essentiel.
Cette thèse présente en premier lieu un processus de traduction, d’adaptation et de validation en français et en anglais d’un outil en allemand visant l’évaluation des compétences requises lorsque le travail est organisé en mode distribué. Un premier article présente les limites fréquemment observées dans les études qui effectuent de telles adaptations.
Un deuxième article met ensuite en lumière l’importance relative d’un ensemble de compétences liées à deux types de performances individuelles appropriées au travail en projet virtuel. Les résultats montrent que la créativité, l’autonomie, l’intégrité, la loyauté et la minutie sont directement liées à la performance proactive. Il est cependant nécessaire de prendre en compte l’effet positif de la perception de collaboration et l’effet négatif du degré de virtualité pour comprendre comment les compétences que constituent la motivation à apprendre, l’autonomie, l’intégrité, la loyauté et la minutie agissent sur la performance adaptative.
En somme, cette thèse propose d’abord un processus rigoureux permettant l’adaptation, la traduction et la validation d’outils dans plusieurs langues. Ce processus permet d’éviter les limites auxquelles se buteraient des méthodes plus simples dans un contexte international où il est primordial d’avoir une très grande confiance en l’équivalence des instruments. Cette thèse représente également un avancement intéressant en ce qui a trait à la compréhension des différents déterminants de la performance individuelle lorsque le travail est organisé en projets virtuels. Des recommandations sont présentées afin de favoriser la performance individuelle, et des pistes de recherches futures sont également amenées pour continuer à approfondir les connaissances sur le sujet. / In a context where workplaces are becoming more internationalized, and where innovation is critical, today's organizations must structure jobs by taking into account geographical distance and the need to perform well in tasks related to different projects. However, innovative projects and access to communication tools are not sufficient conditions to ensure adequate performance. Various factors, such as skills relevant to teleworking and the degree of virtuality that separates people must be factored in to achieve good performance. Furthermore, in order to select candidates who will be able to perform well in this context, the use of appropriate and available assessment tools in several languages is essential.
First, this thesis presents a process of translation, adaptation and validation in French and English of a German questionnaire used for the assessment of skills when work is organized in a distributed mode. The first article address limitations that characterize studies that perform such adaptations.
A second article then highlights the relative importance of a set of competencies related to two types of individual performance suitable for projects in virtual mode. Results show that creativity, independence, integrity, loyalty and conscientiousness are directly related to proactive performance. However, it is necessary to take into account the positive effect of the perception of collaboration and the negative effect of the degree of virtuality to understand how competencies such as learning motivation, independence, integrity, loyalty and conscientiousness affect adaptive performance.
In sum, this thesis first proposes a rigorous process to adapt, translate, and validate instruments in several languages. This process helps avoid common limitations simpler methods are prone to and is better adapted to an international context where it is essential to have great confidence in the equivalences of the instruments. This thesis is also an interesting advancement in regard to understanding the various determinants of individual performance when work is organized in virtual projects. Recommendations are given to foster individual performance, and suggestions for future research are also presented in order to further deepen knowledge on the subject.
|
55 |
Le nombre b-chromatique de quelques classes de graphes généralisant les arbresFerreira Da Silva, Ana Shirley 24 November 2010 (has links) (PDF)
Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres: cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1.) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1.
|
56 |
Quelques théorèmes de points critiques basés sur une nouvelle notion d'enlacementBoulanger, Laurence 12 1900 (has links)
Une nouvelle notion d'enlacement pour les paires d'ensembles $A\subset B$, $P\subset Q$ dans un espace de Hilbert de type $X=Y\oplus Y^{\perp}$ avec $Y$ séparable, appellée $\tau$-enlacement, est définie. Le modèle pour cette définition est la généralisation de l'enlacement homotopique et de l'enlacement au sens de Benci-Rabinowitz faite par Frigon. En utilisant la théorie du degré développée dans un article de Kryszewski et Szulkin, plusieurs exemples de paires $\tau$-enlacées sont donnés. Un lemme de déformation est établi et utilisé conjointement à la notion de $\tau$-enlacement pour prouver un théorème d'existence de point critique pour une certaine classe de fonctionnelles sur $X$. De plus, une caractérisation de type minimax de la valeur critique correspondante est donnée. Comme corollaire de ce théorème, des conditions sont énoncées sous lesquelles l'existence de deux points critiques distincts est garantie. Deux autres théorèmes de point critiques sont démontrés dont l'un généralise le théorème principal de l'article de Kryszewski et Szulkin mentionné ci-haut. / A new notion of linking for pairs of sets $A\subset B$, $P\subset Q$ in a Hilbert space of the form $X=Y\oplus Y^{\perp}$ with $Y$ separable, called $\tau$-linking, is defined. The model for this definition is the generalization of homotopical linking and linking in the sense of Benci-Rabinowitz made by Frigon. Using the degree theory developped in an article of Kryszewski and Szulkin, many examples of $\tau$-linking pairs are given. A deformation lemma is established and used jointly with the notion of $\tau$-linking to prove an existence theorem for critical points of a certain class of functionals defined on $X$. Moreover, a characterization of a minimax nature for the corresponding critical value is given. As a corollary of this theorem, conditions are stated under which the existence of two distinct critical points is guaranteed. Two other critical point theorems are demonstrated, one of which generalizes the main theorem of the article of A new notion of linking for pairs of sets $A\subset B$, $P\subset Q$ in a Hilbert space of the form $X=Y\oplus Y^{\perp}$ with $Y$ separable, called $\tau$-linking, is defined. The model for this definition is the generalization of homotopical linking and linking in the sense of Benci-Rabinowitz made by Frigon~\cite{frigon:1}. Using the degree theory developped in~\cite{szulkin:1}, many examples of $\tau$-linking pairs are given. A deformation lemma is established and used jointly with the notion of $\tau$-linking to prove an existence theorem for critical points of a certain class of functionals defined on $X$. Moreover, a characterization of a minimax nature for the corresponding critical value is given. As a corollary of this theorem, conditions are stated under which the existence of two distinct critical points is guaranteed. Two other critical point theorems are demonstrated, one of which generalizes the main theorem of the article by Kryszewski and Szulkin cited above.
|
57 |
Travail en mode projet distribué géographiquement : mesure des compétences, de la collaboration et des performances individuelles selon le degré de virtualitéLacasse, Caroline 09 1900 (has links)
Dans un contexte où le monde du travail s’internationalise et où l’innovation est fondamentale, les organisations d’aujourd’hui doivent structurer le travail en tenant compte des distances géographiques et du besoin de bien performer dans les tâches reliées aux différents projets. Toutefois, le recours à des projets innovants et l’accès à des moyens de communication ne sont pas des conditions suffisantes pour assurer une performance adéquate. Différents facteurs, comme les compétences adaptées au travail virtuel et le degré de virtualité qui sépare les gens, doivent être pris en compte pour favoriser l’atteinte d’une bonne performance. De plus, afin de sélectionner les candidats qui seront en mesure de bien performer dans ce contexte, le recours à des outils d’évaluation appropriés et disponibles dans plusieurs langues est essentiel.
Cette thèse présente en premier lieu un processus de traduction, d’adaptation et de validation en français et en anglais d’un outil en allemand visant l’évaluation des compétences requises lorsque le travail est organisé en mode distribué. Un premier article présente les limites fréquemment observées dans les études qui effectuent de telles adaptations.
Un deuxième article met ensuite en lumière l’importance relative d’un ensemble de compétences liées à deux types de performances individuelles appropriées au travail en projet virtuel. Les résultats montrent que la créativité, l’autonomie, l’intégrité, la loyauté et la minutie sont directement liées à la performance proactive. Il est cependant nécessaire de prendre en compte l’effet positif de la perception de collaboration et l’effet négatif du degré de virtualité pour comprendre comment les compétences que constituent la motivation à apprendre, l’autonomie, l’intégrité, la loyauté et la minutie agissent sur la performance adaptative.
En somme, cette thèse propose d’abord un processus rigoureux permettant l’adaptation, la traduction et la validation d’outils dans plusieurs langues. Ce processus permet d’éviter les limites auxquelles se buteraient des méthodes plus simples dans un contexte international où il est primordial d’avoir une très grande confiance en l’équivalence des instruments. Cette thèse représente également un avancement intéressant en ce qui a trait à la compréhension des différents déterminants de la performance individuelle lorsque le travail est organisé en projets virtuels. Des recommandations sont présentées afin de favoriser la performance individuelle, et des pistes de recherches futures sont également amenées pour continuer à approfondir les connaissances sur le sujet. / In a context where workplaces are becoming more internationalized, and where innovation is critical, today's organizations must structure jobs by taking into account geographical distance and the need to perform well in tasks related to different projects. However, innovative projects and access to communication tools are not sufficient conditions to ensure adequate performance. Various factors, such as skills relevant to teleworking and the degree of virtuality that separates people must be factored in to achieve good performance. Furthermore, in order to select candidates who will be able to perform well in this context, the use of appropriate and available assessment tools in several languages is essential.
First, this thesis presents a process of translation, adaptation and validation in French and English of a German questionnaire used for the assessment of skills when work is organized in a distributed mode. The first article address limitations that characterize studies that perform such adaptations.
A second article then highlights the relative importance of a set of competencies related to two types of individual performance suitable for projects in virtual mode. Results show that creativity, independence, integrity, loyalty and conscientiousness are directly related to proactive performance. However, it is necessary to take into account the positive effect of the perception of collaboration and the negative effect of the degree of virtuality to understand how competencies such as learning motivation, independence, integrity, loyalty and conscientiousness affect adaptive performance.
In sum, this thesis first proposes a rigorous process to adapt, translate, and validate instruments in several languages. This process helps avoid common limitations simpler methods are prone to and is better adapted to an international context where it is essential to have great confidence in the equivalences of the instruments. This thesis is also an interesting advancement in regard to understanding the various determinants of individual performance when work is organized in virtual projects. Recommendations are given to foster individual performance, and suggestions for future research are also presented in order to further deepen knowledge on the subject.
|
58 |
Propriétés physico-chimiques et rhéologiques de la farine et de l'amidon de taro (Colocasia esculenta L. Schott) variété Sosso du Tchad en fonction de la maturité et du mode de séchage / Physicochemical and rheological properties from taro (Colocasia esculenta L. Schott) flour and starch of Sosso Chad variety as affected by drying method and maturity stageHimeda, Makhlouf 11 September 2012 (has links)
Les résultats montrent que la teneur en cendres, protéines brutes, sucres disponibles, oxalates totaux, amidons et phosphore augmente significativement (p<0,05) avec la maturité. En revanche la teneur en amylose baisse avec la maturité. La capacité d'absorption d'eau, l'indice de solubilité, la température et l'enthalpie de gélatinisation (delta H) des farines et amidons augmentent significativement (p<0,05) en fonction du degré de maturité. Quel que soit le degré de maturité, les granules d'amidon ont présenté un diffractogramme caractéristique de type "A". Les précurseurs de brunissement augmentent significativement (p<0,05) avec le degré de maturité. Le paramètre L* des farines et des pâtes augmente alors que a* diminue en fonction du degré de maturité. Le paramètre L* est plus élevé et a* moins élevé dans le cas du séchage électrique que le séchage solaire. Les caractéristiques sensorielles des pâtes de taro Sosso sont affectées positivement par le degré de maturité et le séchage électrique. L'acceptabilité générale des pâtes de taro Sosso est corrélée à la couleur de celles-ci. Cette étude suggère que 10 mois de maturité de taro Sosso et le séchage électrique (40°C) sont des conditions favorables à l'obtention des pâtes de qualité acceptable / Results showed that the ash content, crude proteins, available sugars, total oxalate, starch and phosphorus content increased significantly with the maturity stage. On the other hand the amylose content decreased as function of the maturity. The water adsorption capacity, the water solubility index, the temperature and the enthalpy of gelatinization of the flour and starch increased significantly with the maturity stage. Irrespective of the degree of maturity the starch granules diffractogramm were exhibited an "A" type cristallinity. The browning indicators increased significantly (p<0.05) with the maturity stage of the tuber. The color coordinate L* of the flours and that of its dough increased while a* decreased with the maturity stage. These two coordinates lend themselves better with electric drying than solar drying. The sensory characteristics of the taro Sosso dough were positively affected by the maturity stage and electric drying. The overall acceptability of taro Sosso dough was correlated with its color. These results suggest that 10 months of the taro Sosso maturity and the electric drying (40°C) are the best conditions to obtain the acceptable pastes. These optimum conditions might be used to produce the taro flour at industrial scale
|
59 |
L'enseignement des langues étrangères dans la formation professionnelle du second degré en Allemagne, en Catalogne et en France : statuts, usages, représentations / Teaching foreign languages in vocational education in Germany, Catalonia and France : status, uses and representationsPichard-Doustin, Dominique 29 November 2018 (has links)
Cette thèse explore et compare des représentations élaborées au sujet des langues étrangères ayant leur place dans les curricula de la formation professionnelle du second degré de trois entités socio-historiques et politiques, l’Allemagne, la Catalogne et la France. Elle s’intéresse aussi aux finalités de l’enseignement de ces langues étrangères et aux éventuelles influences exercées par les contextes politiques, idéologiques, sociolinguistiques et éducatifs sur les représentations élaborées par les personnes interrogées. Ces questionnements permettent de formuler que dans les représentations élaborées par des personnes résidant en Allemagne, en Catalogne et en France, une langue étrangère et une finalité de l’apprentissage de langues étrangères dominent : l’anglais et la fonction utilitariste de la langue. / This doctoral thesis seeks to explore and compare representations about forein languages to learn in vocational education in three socio-historical and political entities, Germany, Catalonia and France. It also aims to explore and compare the finalities of learning foreign languages in this kind of education and the eventual influences of political, ideological, sociolinguistical and educational contexts on the representations of the interviewed persons. Those questions allow to formulate that one language and one finality are hegemonical in the representations, english and the utility to learn a foreign language.
|
60 |
Vertex partition of sparse graphs / Partition des sommets de graphes peu densesDross, François 27 June 2018 (has links)
Le Théorème des Quatre Couleurs, conjecturé en 1852 et prouvé en 1976, est à l'origine de l'étude des partitions des sommets de graphes peu denses. Il affirme que toute carte plane peut être coloriée avec au plus quatre couleurs différentes, de telle manière que deux régions qui partagent une frontière aient des couleurs différentes. Énoncé en terme de théorie des graphes, cela veut dire que tout graphe planaire, c'est à dire tout graphe qui peut être représenté dans le plan sans que deux arêtes ne se croisent, peut voir son ensemble de sommets partitionné en quatre ensembles tels que chacun de ces ensembles ne contient pas les deux extrémités d'une même arête. Une telle partition est appelée une coloration propre en quatre couleurs. Dans cette thèse, on s'intéresse à l'étude de la structure des graphes peu denses, selon différentes notions de densité. D'une part, on étudie les graphes planaires sans petits cycles, et d'autre part les graphes dont tous les sous-graphes ont un degré moyen peu élevé. Pour ces classes de graphes, on recherche tout d'abord le plus petit nombre de sommets à retirer pour obtenir une forêt, c'est à dire un graphe sans cycles. Cela peut être vu comme une partition des sommets du graphe en un ensemble induisant une forêt et un ensemble de sommets contenant au plus une fraction donnée des sommets du graphe. La motivation première de cette étude est une conjecture d'Albertson et Berman (1976) comme quoi tout graphe planaire admettrait une telle partition où la forêt contient au moins la moitié des sommets du graphe. Dans un second temps, on s'intéresse aux partitions des sommets de ces graphes en deux ensembles, tels que les sous-graphes induits par ces deux ensembles ont des propriétés particulières. Par exemple, ces sous-graphes peuvent être des graphes sans arêtes, des forêts, des graphes de degré borné, ou des graphes dont les composantes connexes ont un nombre borné de sommets. Ces partitions des sommets sont des extensions de la notion de coloration propre de graphe.On montre, pour différentes classes de graphes peu denses, que tous les graphes de ces classes admettent de telles partitions. On s'intéresse également aux aspect algorithmiques de la construction de telles partitions. / The study of vertex partitions of planar graphs was initiated by the Four Colour Theorem, which was conjectured in 1852, and proven in 1976. According to that theorem, one can colour the regions of any planar map by using only four colours, in such a way that any two regions sharing a border have distinct colours. In terms of graph theory, it can be reformulated this way: the vertex set of every planar graph, i.e. every graph that can be represented in the plane such that edges do not cross, can be partitioned into four sets such that no edge has its two endpoints in the same set. Such a partition is called a proper colouring of the graph.In this thesis, we look into the structure of sparse graphs, according to several notions of sparsity. On the one hand, we consider planar graphs with no small cycles, and on the other hand, we consider the graphs where every subgraph has bounded average degree.For these classes of graphs, we first look for the smallest number of vertices that can be removed such that the remaining graph is a forest, that is a graph with no cycles. That can be seen as a partition of the vertices of the graph into a set inducing a forest and a set with a bounded fraction of the vertices of the graph. The main motivation for this study is a the Albertson and Berman Conjecture (1976), which states that every planar graph admits an induced forest containing at least one half of its vertices.We also look into vertex partition of sparse graphs into two sets both inducing a subgraph with some specific prescribed properties. Exemples of such properties can be that they have no edges, or no cycles, that they have bounded degree, or that they have bounded components. These vertex partitions generalise the notion of proper colouring. We show, for different classes of sparse graphs, that every graph in those classes have some specific vertex partition. We also look into algorithmic aspects of these partitions.
|
Page generated in 0.0543 seconds