Spelling suggestions: "subject:"[een] DOMINATION"" "subject:"[enn] DOMINATION""
111 |
Domination in BenzenoidsBukhary, Nisreen 07 May 2010 (has links)
A benzenoid is a molecule that can be represented as a graph. This graph is a fragment of the hexagon lattice. A dominating set $D$ in a graph $G$ is a set of vertices such that each vertex of the graph is either in $D$ or adjacent to a vertex in $D$. The domination number $\gamma=\gamma(G)$ of a graph $G$ is the size of a minimum dominating set. We will find formulas and bounds for the domination number of various special benzenoids, namely, linear chains $L(h)$, triangulenes $T_k$, and parallelogram benzenoids $B_{p,q}$. The domination ratio of a graph $G$ is $\frac{\gamma(G)}{n(G)}$, where $n(G)$ is the number of vertices of $G$. We will use the preceding results to prove that the domination ratio is no more than $\frac{1}{3}$ for the considered benzenoids. We conjecture that is true for all benzenoids.
|
112 |
Very Cost Effective Domination in GraphsRodriguez, Tony K 01 May 2014 (has links)
A set S of vertices in a graph G=(V,E) is a dominating set if every vertex in V\S is adjacent to at least one vertex in S, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is very cost effective if every vertex in S is very cost effective. The minimum cardinality of a very cost effective dominating set of G is the very cost effective domination number of G. We first give necessary conditions for a graph to have equal domination and very cost effective domination numbers. Then we determine an upper bound on the very cost effective domination number for trees in terms of their domination number, and characterize the trees which attain this bound. lastly, we show that no such bound exists for graphs in general, even when restricted to bipartite graphs.
|
113 |
La philosophie comme manière de vivre ou les impasses de la domination. Sur une lecture des Caractères de la Bruyère / Philosophy as a Way of Life or the Impasses of Domination. On a Reading of The Characters of La BruyèrePicardi, Emmanuel 01 February 2017 (has links)
À l’appui des Caractères de la Bruyère, nous ouvrons à nouveau une question laissée en suspens par les études qui ont été menées autour de « la philosophie comme manière de vivre ». Cette question concerne la nouvelle relation entre la parole et l’action qui se serait établie à partir des XVIe et le XVIIe siècles en Occident. Au travers des différentes hypothèses proposées, nous avons choisi d’étudier le rôle qu’y a joué la parole de type machiavélien ou la logique de la domination. À la fois mode d’accès à la connaissance, mode de constitution de soi et rapport à la politeia, cette logique en laquelle s’est inscrit progressivement le savoir moderne nous détourne d’un accès au texte de la Bruyère pouvant libérer tout son potentiel de réformation éthique – sa psychagogie. Pour accéder à ce potentiel, il nous faut tour à tour prendre distance avec la logique de la domination et renouer avec cet autre rapport au langage qu’elle n’a cessé par ailleurs de discréditer, à savoir ce rapport d’origine socratique que relaient les différentes productions philosophiques de l’Antiquité auxquelles se réfèrent les Caractères. Aussi, devrons-nous réévaluer objectivement les postulats anthropologiques qui sont autant de motifs éthiques qui innervent la pensée politique et sociologique moderne et qui configurent le foyer de notre expérience politique actuelle. / By having recourse to La Bruyère’s Characters, this work aims at reassessing a question that has been let aside by scholarly studies dedicated to « the philosophy as a way of life ». This question deals with the new relation between speech and action which is believed to have occurred in the 16th-17th centuries in the West. Through different hypotheses, we have chosen to examine the role played by the Machiavellian type of speech, or the logic of the domination. Being at the same time a way to access knowledge, a mode of self-constitution and a relationship to politeia, this logic is the place where the Modern knowledge gradually falls within and also turns us away from an access to La Bruyère’s text that can release its potential of ethical reformation – its psychagogy. In order to gain access to this potential, we have in turns to distance ourselves from the discursive logic of domination and to renew with this other relation to language, to oneself and to politeia that this logic constantly brings into disrepute, in other words to this Socrastic relation to be found in the philosophical production of the Antiquity to which the Characters refer to.
|
114 |
Penser les injustices de genre. Approche par les violences sexuelles / Injustice and Gender. Thinking Sexual ViolenceChartron, Marie-Pauline 17 December 2018 (has links)
Comment rendre intelligibles les injustices de genre dans toute leur extension ? Cette démarche de philosophie politique appliquée conduit à en tenter l’approche par les violences sexuelles comprises comme extrémisation de ces injustices. Dans une première partie, les limites de l’apport des théories de la justice sont mises en lumière à travers le féminisme libéral complexe de Susan Okin, qui centre sur les injustices de genre dans le travail et dans la famille. L’examen des évolutions de son questionnement y fait apparaître l’intuition de certaines exigences pour penser les violences sexuelles comme injustices, laissées par elle inexplorées. La deuxième partie, centrée sur des études contextuelles, est consacrée à des phénoménalisations de ces violences dans la société contemporaine. À partir de la théorisation du genre par Catherine MacKinnon comme domination sexualisée, et à l’aide des données fournies par des travaux d’anthropologie, se trouvent investiguées les violences hétérosexuelles entre adultes et les violences sexuelles intrafamiliales. De ce moment d’expérimentation la domination genrée ressort comme fonction dynamique des violences sexuelles. Une ultime étape explore des remédiations. Deux pratiques collectives de réparation et de prévention ouvrent sur une éthique féministe de la reconstruction dont la portée politique fait surgir les violences comme injustices structurelles. Des travaux d’Iris M. Young sont dégagées les exigences d’une prise en charge sociale de telles injustices. Le geste est amorcé enfin d’une reconstruction normative traçant les contours d’une justice non seulement distributive et réparatrice, mais aussi transformative. / How can one think of gender injustice in all its extension ? This research in applied political philosophy seeks to shed light on this problem by focusing on sexual violence as a social and structural phenomenon.In a first part, the limits of « theory of justice approach » are highlighted through an examination of one of its fullest attempts regarding gender, that is Susan Okin’s feminist liberalism. Evolutions in her works allow me to bring out some intuitions regarding the political implications of what would be an account of sexual violence taken as social injustice, yet such intuitions remained unexplored. Taking these limits seriously, the second part of this research sets to examine sexual violence as phenomenonalized in contemporary society. With MacKinnon’s theory of gender as sexualised domination as a critical background given by Okin herself for my investigation, I tackle heterosexual violence between adults as well as intrafamilial sexual violence. This experimental gesture leads me to elaborate gendered domination as a dynamic function of sexual violence. A last moment explores the remedies implied by such comprehension. Two forms of collective and feminist praxis as reparative and preventive, are analysed so as to bring out the normative foundations of what appears as a feminist ethics of reconstruction. Its political dimension leads to an apprehension of sexual violence as structural injustice. Iris Young’s work is discussed in the respect, so as to highlight the conditions of a full apprehension of sexual violence as injustice. A normative reconstruction that leads to envisage justice not only as distributive or reparative, but also as transformative.
|
115 |
Communication de l’État en contexte de crise financière internationale. : Le cas des crises : krach boursier de 1987, crise asiatique de 1997-1998, subprimes en 2007-2008 / State communication in the context of international financial crisis. : The case of crises : stock market crash of 1987, Asian crisis of 1997-1998, subprime in 2007-2008Fusi, Mathieu 26 October 2018 (has links)
Les « crises financières internationales » sont des événements forts qui remettent en cause l’ordre du secteur financier tout en impactant le reste de la société, notamment aux niveaux économique (baisse des crédits par exemple) et social (chômage par exemple). Elles présentent donc l’intérêt de situer clairement les valeurs et les normes que l’État et ses représentants défendent lorsque ceux-ci communiquent sur ces « crises ». Notre recherche s’appuie sur les activités de communication des membres de l’exécutif (les ministres et le Président de la République) pendant le « krach boursier de 1987 », la « crise asiatique de 1997-1998 » et la « crise des subprimes de 2007-2008 ». Il existe en effet un lien symbolique entre les activités de communication des membres de l’exécutif et la communication de l’État. Les ministres et le Président sont légitimes pour incarner l’État et le faire agir au travers de leurs activités communicationnelles. À partir de ce lien, il est possible de comprendre le rôle de la communication de l’État pendant une « crise financière internationale ». Cette thèse interroge la participation de la communication étatique au gouvernement de la société française. Elle porte également sur les rapports de collaboration et de concurrence que les représentants de l’État entretiennent, par l’intermédiaire de la communication, avec des acteurs différents – comme les journalistes ou les acteurs politiques d’autres États – participant à la construction d’une « crise ». En somme, notre recherche propose d’inclure la communication de l’État dans des logiques de domination et de rapports de force. / "International financial crises" are meaningful events who question the order of the financial sector while impacting the rest of the society, notably at economic (drop of credits for example) and social levels (unemployment for example). In consequence, they clearly show values and norms that the state and its representatives stand up for when they communicate. Our research is based on communication activities of the members of the executive (ministers and the president of the Republic) during the "stock market crash of 1987", the "asian crisis of 1997-1998", and the "subprimes crisis of 2007-2008". Indeed there is a symbolic link between communication activities of the members of the executive and State communication. Ministers and the President are legitimate to embody the State and make it act through their communication activities. From this link, it is possible to understand the role of the State communication during an "international financial crisis". This thesis examines the participation of State communication in the government of French society. It also addresses the collaborative and competitive relationships, through of communication, that State officials have with different actors - such as journalists or political actors of other States - involved in building a "crisis". In short, our research suggests to include the communication of the State in logics of domination and power relations.
|
116 |
Visibilité du capital social à travers les médias sociaux : Etudes de cas sur les dynamiques sociales de l'appropriation d'un outil d'Analyse de Réseaux Sociaux / Visibility of social capital through social media : Case studies on the social dynamics of the ownership of a Social Network Analysis ToolKaroui, Myriam 21 September 2012 (has links)
Ce travail de thèse vise à comprendre les dynamiques sociales qui viennent influencer le processus d’appropriation d’une technologie SNA au sein d’une organisation. Pour ce faire, nous avons mené une étude inter-cas menée au sein de deux collectivités territoriales françaises et une étude intra-cas chez BOUYGUES CONSTRUCTION en nous appuyant sur un cadre théorique mobilisant la théorie de l’acteur stratégique de Crozier et Friedberg et la théorie de la pratique de Bourdieu. Un des principaux résultats de cette thèse est que l’appropriation d’une technologie SNA passe principalement par une appropriation socio-politique en deux phases : une phase d’appropriation de la nouvelle dimension donnée au capital social et une phase d’appropriation de la technologie pour servir les intérêts des acteurs concernant le développement du capital social. Nous avons également identifié que l’introduction d’un outil SNA est assignée à différentes notions symboliques (symbole de la légitimité du contrôle et de la supervision, symbole du soutien du top-management des pratiques de travail transversales, le symbole de la rigidité des structures organisationnelles, le symbole de la gestion des ressources informelles comme une ressource spécifique, le symbole de l’exclusion…) qui viennent légitimer et asseoir les différentes stratégies des groupes d’acteurs. Enfin, nous avons constaté que certains symboles liés à l’introduction du SNA sont étroitement liés à la culture de l’organisation. Ces principaux résultats ont pu être confortés par l’étude intra-cas menée chez BOUYGUES CONSTRUCTION, présentée comme une étude d’un cas particulier pouvant complémenter l’investigation menée au sein des deux collectivités territoriales. / This thesis aims to understand the social dynamics that influences actors’ adoption of a SNA tool in an organization. We have conducted multiple-case studies of two French Administrations (Mayoral offices) and an additional single case referred to a French industry BOUYGUES CONSTRUCTION drawing on Crozier and Friedberg’s theory of strategic actor and Bourdieu’s theory of practice. The first principle result is that the adoption of a SNA technology is primarily a socio-political appropriation that occurs through two phases: in the first phase actors discover social capital as a new symbolic capital and in a second phase they use the technology to influence the development of the organizational social capital in order it can serve their own interests. We have also identified that the introduction of a SNAS tool is assigned to different symbolic notions (symbol of the legitimization for control and supervision, symbol of top-management support for the development of transversal work practices, symbol of the rigidity of organizational structure, symbol of the management of informal resource as specific resource, symbol of exclusion) useful to provide legitimacy to the actors’ strategies in organizations. Finally, we highlight that these symbolic notions appear connected to the organizational culture. These key findings have emerged from our multiple-case study and have been reinforced the additional single case studied in BOUYGUES CONSTRUCTION. This single case complements the investigation conducted in the two Mayoral offices.
|
117 |
La formation de la croyance en la valeur littéraire en situation coloniale et postcoloniale : étude des trajectoires de consécration des écrivains algériens francophones Assia Djebar et Kateb Yacine, en France, entre 1950 et 2009 / The formation of belief in literary value in colonial and postcolonial situation : study of consecration’s career of Algerian authors of French language Assia Djebar and Kateb Yacine, between 1950 and 2009, in FranceHarchi, Kaoutar 12 September 2014 (has links)
La présente thèse de doctorat s’intéresse à la formation de la croyance en la valeur littéraire en la situation coloniale et postcoloniale, entre 1950 et 2009, en France. Pour cela, nous avons fait le choix de porter notre attention sur les trajectoires de consécration de deux auteurs algériens de langue française ayant fait l’objet d’une consécration littéraire sociologiquement objectivable, à savoir Assia Djebar (1936-) et Kateb Yacine (1929-1989). La problématique littéraire algérienne de langue française ne pouvant pertinemment être abordée au prisme de la théorie des champs de Pierre Bourdieu, nous avons fait le choix de recourir, à travers notre étude, à la notion d’institution littéraire telle que l’a notamment définie Jacques Dubois. Selon ce que nous avons alors pu observer à travers un corpus constitué d’entretiens, d’articles de presse, de discours officiels, de correspondances privées, le phénomène de consécration littéraire des deux auteurs algériens de langue française serait modélisable sous la forme de cinq étapes : la découverte, la publication, la réception critique, l’entrée dans l’univers académique, l’entrée dans l’univers de l’enseignement scolaire et universitaire. L’intérêt de cette modélisation repose principalement sur sa capacité à révéler, au-delà de la doxa littéraire, les modalités sociales ayant concouru à la formation d’une croyance en la qualité des productions textuelles données. Et, à chaque étape de la trajectoire de consécration d’Assia Djebar et de Kateb Yacine, se donnent à voir des relations fortes entre, d’une part, le littéraire et, d’autre part, l’extra-littéraire. En ce sens, l’idée couramment répandue selon laquelle la consécration d’un auteur n’aurait pour seule cause que son talent se trouve fortement remise en cause. La littérature francophone ou, plus précisément, la francophonie littéraire – dénomination sous laquelle Assia Djebar et Kateb Yacine sont régulièrement catégorisés – apparaît donc être un système réglé selon des intérêts qui, loin d’être prétendûment « purs », relèvent de logiques politique et idéologique. Engagés dans des rapports de domination symbolique et matériel dont la consécration littéraire est l’une des formes paradoxales, Assia Djebar et Kateb Yacine ont tous deux, au cours de leur trajectoire respective, mis en place des stratégies spécifiques afin de limiter la valeur instrumentale dont leurs productions textuelles ont été investies et imposer leur définition de ce que serait la littérature algérienne de langue française. / The present doctoral thesis is intersestd in the formation of the belief in literary value in colonial and postcolonial situation, between 1950 and 2009, in France. For that, we made the choice to pay our attention to the paths of recognition of two Algerian authors of French language who have been the object of an objectivable literary achievment, namely Assia Djebar (1936-) and Kateb Yacine (1929-1989). Since the Algerian literary of French language core statement can’t pertinently be approached via the prism of the fields theory by Pierre Bourdieu, we made the choice to resort, through our study, to the concept of literary insitution defined by the likes of Jacques Dubois. According to what we then could have observed through a corpus made up of talks, press articles, official discourses, private correspondences, the literary phenomenon of recognition of the two Algerian authors would be modeled in the form of five stages: the discovery, the publication, the critical reception, the entry in the academic field and the entry in the universe of secondary education. The interest of this modeling is mainly based on its capacity to reveal, beyond the literary doxa, the social methods that have contributed to the formation of a belief in the quality of the given textual productions. And, at each stage of the paths of recognition of Assia Djebar and Kateb Yacine, we can observe strong relations between, on the one hand, the literary and, on the other hand, the extra-literary. In this direction, the commonly widespread idea according to which the recognition of an author would only be based on talent is strongly questionned. The French-speaking literature or, more precisely, the literary francophonie – denomination under which Assia Djebar and Kateb Yacine are regularly categorized – thus appears to be a regulated system depending on interests far from being allegedly “pure”, but driven by ideological and political logics. Engaged in relations of symbolic domination, Assia Djebar and Kateb Yacine have both, during their respective paths, set up of specific strategies in order to limit the instrumental value of their textual productions and impose their own definition of what Algerian literature of French language truly should be.
|
118 |
Comment les rapports de domination se « réalisent-ils » ? : Appréhender les rapports sociaux de sexe, de race et de classe dans les mobilisations des migrant.e.s brésilien.ne.s au Japon dans les années 2000 / How do relations of domination « accomplish » ? : Capturing social relations of sex, race and class within the mobilizations of Brazilian migrants in Japan in the 2000sMarchadour, Guénolé 27 February 2015 (has links)
Au croisement de la sociologie des mobilisations, de la sociologie des migrations et des études genre, cette thèse vise à saisir la réalisation des rapports de domination dans l’action collective des migrant.e.s brésilien.ne.s au Japon dans les années 2000. Au delà des catégorisations ethnoraciales (descendant.e / non descendant.e de Japonais) et classées (ouvrier.ère / indépendant.e), généralement utilisées pour décrire ce fait migratoire, les catégories de sexe contribuent aussi à le caractériser. Dans la perspective de l’intersectionnalité, la thèse s’appuie sur l’ethnographie multisituée pour appréhender la réalisation des rapports sociaux de sexe, de race et de classe. Ceux-ci s’actualisent dans des pratiques circonscrites mais aussi dans des contextes variés où l’intersectionnalité se révèle d’autant mieux que les rapports de pouvoir peuvent changer, s’inverser, « s’invisibiliser ». Pour ce faire, trois espaces de mobilisation ont été explorés : des écoles brésiliennes, des syndicats et des associations locales. Des observations in situ étalées entre 2006 et 2011 ont été complétées par quatre-vingt-dix entretiens semi-directifs en portugais et en japonais avec des familles migrantes, les migrant.e.s mobilisé.e.s, les leaderships et leurs soutiens extérieurs. En examinant leurs interactions, l’enquête multisituée montre que la réalisation des rapports de domination s’appréhende à partir de trois échelles d’analyse : nationale (les contextes japonais et brésilien), sectorielle (syndical, éducatif et associatif) et situationnelle (les dynamiques des organisations dans chaque secteur). De cette façon, la thèse fait ressortir les nouvelles frontières de la société japonaise et les reconfigurations de l’imaginaire national brésilien selon les sites de l’enquête. / At the intersection of the sociology of mobilization, the sociology of migration and the gender studies, this thesis aims at capturing the accomplishment of relations of domination in the collective actions of Brazilian migrants in Japan in the 2000s. Beyond ethnoracial (descendants / non descendants of Japanese people) and class-based (unskilled workers / self-employed) categorizations, generally used to describe this migration, the social relations of sex also help to categorize the phenomenon. In the wake of the theory of intersectionality, this thesis – based on a multisited ethnography – analyzes the production of social relations of sex, race and class. These can be observed in specific practices but also in a variety of contexts where intersectionality becomes all the more noticeable as the relations of power may change, interchangeable and « invisible ». To do so, three spaces of mobilization have been explored : Brazilian schools, workers’ unions and grassroots organizations. In situ observations were conducted from 2006 to 2011 and ninety semi-structured interviews were led in Japanese and Portuguese with migrant families, members and leaderships of the groups, and their external supporters. The multisited field study shows that the accomplishment of the relations of domination can be captured by focusing on three scales of analysis : national (Brazilian and Japanese contexts), sector-based (education, unionism and voluntary sector), situational (organizational dynamics in each sector). In this way, the thesis highlights the new boundaries of Japanese society and the reconfigurations of an imagined Brazilian community depending on the sites studied.
|
119 |
Les mondes de la chasse : contribution à une étude de rapports sociaux spatialisés en Seine-et-Marne et en Côte-d’Or / The worlds of hunting : studying spatialized relationships between social classes in Seine-et-Marne and Côte-d'OrFradkine, Héloïse 07 July 2015 (has links)
Consacrée à l’étude de rapports sociaux qui se nouent autour de la chasse, cette thèse se veut une contribution à une sociologie des modes de vie qui, prenant en charge l’inscription spatiale du social, permet de donner concrètement à voir la dimension relationnelle de la construction des classes sociales. La constitution des mondes de la chasse à l’échelle nationale est d’abord retracée et mise en perspective aux plans historique et socio-démographique. L’attention est en particulier orientée vers les transformations des conditions de la chasse en lien avec les évolutions récentes des espaces ruraux et périurbains. Les deuxième et troisième parties de la thèse se fondent principalement sur l’analyse de matériaux recueillis, selon des méthodes de type ethnographique, sur deux espaces contrastés : le Germanois (Côte-d’Or) et les environs bellifontains (Seine-et-Marne). Sur chaque terrain, différents groupements cynégétiques ont été observés : sociétés communales de chasse, groupes de chasse à tir privés, équipages de chasse à courre. Les manières dont leurs adhérents, qui appartiennent à des classes et des fractions de classes diverses, embrassent les enjeux auxquels ils sont confrontés – au premier rang desquels la dégradation de l’image de la chasse et l’environnementalisation de sa pratique – sont restituées. L’analyse se resserre ensuite autour des modalités organisationnelles et des logiques d’investissement dans la chasse privilégiées par les représentants de certaines fractions de classes ; celles-ci permettent de rendre compte des significations de leur engagement et de les réinscrire dans les styles de vie qui sont les leurs. / This thesis, studying the social relationships linked to hunting, is contributing to a sociology of the lifestyles that shows how social relationships are linked to space, and how social classes are built through interactions. The first part recounts the constitution of the different hunting worlds on a national level, using historical and socio-demographical perspectives. Special attention is laid on the transformation of the conditions of hunting due to recent evolution of the rural and periurban spaces. The second and third parts are mainly based upon the analysis of data, which were collected using ethnographical methods on two contrasted spaces: the Germanois (Côte-d'Or) and around Bellifontain (Seine-et-Marne). On each field, different hunting groups have been observed: district (“commune”) shooting groups, private shooting groups, hunting with hounds crews. The members of these groups belong to different classes and fractions of these classes. This thesis studies the differentiated ways they cope with what is nowadays at stake in their activity, essentially the deterioration of the image of hunting and the “environmentalization” of their practices. The analysis focuses then on how some of them, representing different social classes and fractions of classes, organize and involve themselves into hunting. It allows to present the meanings of their commitment in keeping with their lifestyles.
|
120 |
Planar graphs : non-aligned drawings, power domination and enumeration of Eulerian orientations / Graphes planaires : dessins non-alignés, domination de puissance et énumération d’orientations EulériennesPennarun, Claire 14 June 2017 (has links)
Dans cette thèse, nous présentons trois problèmes concernant les graphes planaires.Nous travaillons tout d'abord sur les dessins planaires non-alignés, c'est-à-dire des dessins planaires de graphes sur une grille sans que deux sommets se trouvent sur la même ligne ou la même colonne.Nous caractérisons les graphes planaires possédant un tel dessin sur une grille de taille $n times n$, et nous présentons deux algorithmes générant un dessin planaire non-aligné avec arêtes brisées sur cette grille pour tout graphe planaire, avec $n-3$ ou $min(frac{2n-3}{5},$ $#{text{triangles s{'e}parateurs}}+1)$ brisures au total.Nous proposons également deux algorithmes dessinant un dessin planaire non-aligné sur des grilles d'aire $O(n^4)$. Nous donnons des résultats spécifiques concernant les graphes 4-connexes et de type triangle-emboîté.Le second sujet de cette thèse est la domination de puissance dans les graphes planaires. Nous exhibons une famille de graphes ayant un nombre de domination de puissance $gamma_P$ au moins égal à $frac{n}{6}$. Nous montrons aussi que pour tout graphe planaire maximal $G$ à $n geq 6$ sommets, $gamma_P(G) leq frac{n-2}{4}$. Enfin, nous étudions les grilles triangulaires $T_k$ à bord hexagonal de dimension $k$ et nous montrons que $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Nous étudions également l'énumération des orientations planaires Eulériennes. Nous proposons une nouvelle décomposition de ces cartes. En considérant les orientations des dernières $2k-1$ arêtes autour de la racine, nous définissons des sous- et sur-ensembles des orientations planaires Eulériennes paramétrés par $k$.Pour chaque classe, nous proposons un système d'équations fonctionnelles définissant leur série génératrice, et nous prouvons que celle-ci est toujours algébrique. Nous montrons ainsi que la constance de croissance des orientations planaires Eulériennes est entre 11.56 et 13.005. / In this thesis, we present results on three different problems concerning planar graphs.We first give some new results on planar non-aligned drawings, i.e. planar grid drawings where vertices are all on different rows and columns.We show that not every planar graph has a non-aligned drawing on an $n times n$-grid, but we present two algorithms generating a non-aligned polyline drawings on such a grid requiring either $n-3$ or $min(frac{2n-3}{5},$ $#{text{separating triangles}}+1)$ bends in total.Concerning non-minimal grids, we give two algorithms drawing a planar non-aligned drawing on grids with area of order $n^4$. We also give specific results for 4-connected graphs and nested-triangle graphs.The second topic is power domination in planar graphs. We present a family of graphs with power dominating number $gamma_P$ at least $frac{n}{6}$. We then prove that for every maximal planar graph $G$ of order $n$, $gamma_P(G) leq frac{n-2}{4}$, and we give a constructive algorithm.We also prove that for triangular grids $T_k$ of dimension $k$ with hexagonal-shape border, $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Finally, we focus on the enumeration of planar Eulerian orientations. After proposing a new decomposition for these maps, we define subsets and supersets of planar Eulerian orientations with parameter $k$, generated by looking at the orientations of the last $2k-1$ edges around the root vertex.For each set, we give a system of functional equations defining its generating function, and we prove that it is always algebraic.This way, we show that the growth rate of planar Eulerian orientations is between 11.56 and 13.005.
|
Page generated in 0.0385 seconds