Résumé : Les graphes définis à partir de structures algébriques possèdent d’excellentes propriétés de symétries particulièrement intéressantes. L’exemple le plus flagrant est la notion de graphe de Cayley qui s’est révélée très riche non seulement du point de vue théorique mais aussi pratique par ses applications à de nombreux domaines incluant l’architecture des réseaux ou les machines parallèles. Néanmoins, la régularité des graphes de Cayley se révèle parfois être une limite étant donné qu’ils sont toujours sommet-transitifs et donc en particulier non pertinents pour générer des réseaux semiréguliers.Cette observation a motivé, en 2005, la définition d’une nouvelle classe de graphes définis à partir d’un groupe, appelés G-graphes. Ils possèdent aussi de nombreuses propriétés de régularité mais de manière moins restrictive.Cette thèse propose un nouveau regard sur cette classe de graphes par une approche plutôt orientée recherche opérationnelle alors que la grande majorité des études précédentes est dominée par des approches essentiellement algébriques. Nous-nous sommes alors intéressés à plusieurs questions :— La caractérisation des G-graphes : nous proposons des améliorations par rapport aux précédents résultats.— Identifier des classes de graphes comme des G-graphes grâce à des isomorphismes ou en utilisant le théorème de caractérisation.— Etudier la structure et les propriétés de ces graphes, en particulier pour de possibles applications aux réseaux : colorations semi-régulières, symétries et robustesse.— Une approche algorithmique pour la reconnaissance de cette classe avec notamment un premier exemple de cas polynomial lorsque le groupe est abélien.
Interactions between graph theory and group theory have already led to interesting results for both domains. Graphs defined from algebraic groups have highly symmetrical structure giving birth to interesting properties. The most famous example is Cayley graphs, which revealed to be particularly interesting both from a theoretical and a practical point of view due to their applications in several domains including network architecture or parallel machines. Nevertheless, the regularity of Cayley graphs is also a limit as they are always vertex-transitive and therefore not relevant to generate semi-regular networks. This observation motivated the definition, in 2005, of a new family of graphs defined from a group, called G-graphs. They also have many regular properties but are less restrictive. These graphs are in particular semi-regular k-partite, with a chromatic number k directly given in the group representation and they can be either transitive or not.This thesis proposes a new insight into this class of graphs using an approach based on operational research while most of previous studies have been so far dominated by algebraic approaches. Then, the thesis addresses different kind of questions:— Characterizing G-graphs: we propose improvements of previous results.— Identifying some classes of graphs as G-graphs through isomorphism or using the characterization theorem.— Studying the structure and properties of these graphs, in particular for possible applications to networks: semi-regular coloring, symmetries and robustness.— Algorithmic approach for recognizing this class with a first example of polynomial case when the group is abelian.

http://www.theses.fr/2014AGUY0787/document

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we investigate on relations between the hyperbolicity of a graph G and the hyperbolicity of its atoms, that are the subgraphs output by the clique-decomposition invented by Tarjan [51, 65]. We prove that the maximum hyperbolicity taken over the atoms is at most one unit off from the hyperbol-icity of G and the bound is sharp. We also give an algorithm to slightly modify the atoms, called the " substitution method " , which is at no extra cost than computing the clique-decomposition, and so that the maximum hyperbolicity taken over the resulting graphs is exactly the hyperbolicity of the input graph G. An experimental evaluation of our method for computing the hyperbolicity of a given graph from its atoms is provided for collaboration networks and biological networks. Finally, on a more theoretical side, we deduce from our results the first linear-time algorithm for computing the hyperbolicity of an outerplanar graph.
ISSN: 0304-3975

hal-01540756
https://hal.inria.fr/hal-01540756
https://hal.inria.fr/hal-01540756/document
https://hal.inria.fr/hal-01540756/file/CCDL-2017.pdf
DOI : 10.1016/j.tcs.2017.06.001

Éditeur(s) : Gauthier-Villars
Résumé : The seasonal variations of total dissolved copper were surveyed during one year (1983/1984) in the Aulne estuary (Western Brittany, France), an ecosystem with a high rate of water renewal. Copper in filtered water samples (after and without acidification) was determined after preconcentration on Chelex 100, and the eluates were analyzed by graphite furnace atomic absorption spectroscopy. The concentrations of free and complexed copper were then plotted versus chlorosity. Globally, the total dissolved copper concentrations tend to decrease with salinity. The role of physicochemical parameters such as pH and suspended matter (adsorption-desorption mechanisms) on dissolved copper content is shown to be significant. With a variable intensity, desorption (release) takes place in summer and in autumn, while adsorption is observed at very low chlorosity in winter. The dissolved copper concentrations in the Aulne estuary (0.26 to 2.52-mu-g.l-1, with the highest values in autumn) are similar to most estuarine copper values. The proportion of complexed species ranges from 4 to 69% (average of 27%).
Les variations saisonnières des concentrations en cuivre dissous dans l'estuaire de l'Aulne (Bretagne occidentale) ont été mesurées au cours d'un cycle annuel (1983/1984). Les concentrations en cuivre libre et celles en cuivre complexé ont été suivies séparément en fonction de la chlorosité, un paramètre conservatif. Les profils obtenus pour le cuivre total dissous montrent généralement une décroissance des teneurs en métal des eaux douces aux eaux marines, tout en restant supérieures à celles de la droite théorique de mélange. On montre le rôle fondamental de la variation du pH concomitante de celle de la matière en suspension (mécanisme d'adsorption-désorption) dans l'évolution des teneurs en cuivre dissous. Ce processus agit plus ou moins intensément dans le sens de la désorption (été, automne) ou de l'adsorption (hiver aux faibles chlorosités). Dans l'ensemble, les teneurs en cuivre total dissous (de 0,26 à 2,52 J.lg.l- 1 , les valeurs automnales étant les plus élevées) sont comparables à celles de nombreux autres écosystèmes estuariens, avec un taux de complexation compris entre 4 et 69% (moyenne de 27% ).
Oceanologica Acta (0399-1784) (Gauthier-Villars), 1991 , Vol. 14 , N. 5 , P. 445-457

Droits : Gauthier-Villars
http://archimer.ifremer.fr/doc/00103/21377/18977.pdf
http://archimer.ifremer.fr/doc/00103/21377/43066.pdf
http://archimer.ifremer.fr/doc/00103/21377/

Résumé : Dans cette thèse, nous nous intéressons à des inclusions de la forme 0∈ f( x) + F(x), où f est une application univoque et F est une application multivoque à graphe fermé. Ces dernières années, diverses méthodes de résolutions d'inclusions de ce type ont été développées par les chercheurs et, après un bref rappel sur quelques notions d'analyse (univoque et multivoque) nous en présentons quelques unes utilisant l'hypothèse de régularité métrique sur l'application multivoque. Dans la suite de notre travail, plutôt que d'utiliser cette hypothèse de régularité métrique, nous lui préférons des hypothèses directement liées à la solution qui sont la semistabilité et l'hemistabilité. Notons que la semistabilité d'une solution x̅ de l'inclusion 0∈G(x) est en fait équivalente à la sous-régularité métrique forte de l'application multivoque G en x̅ pour 0. Après avoir présenté des méthodes utilisant la semistabilité et l'hemistabilité, nous exposons les nouveaux résultats auxquels nous avons abouti qui consistent essentiellement en des améliorations des méthodes présentées. Ce que nous entendons par améliorations se décline en deux points principaux : soit nous obtenons un meilleur taux de convergence, soit nous utilisons des hypothèses plus faibles qui nous permettent d'obtenir des taux de convergence similaires.
In this thesis, we focus on inclusions in the form of 0∈ f( x) + F(x), where f is a single-valued function and F is a set-valued map with closed graph. In the last few years, various methods to solve such inclusions have been developed; after having recalled some notions in analysis (single-valued and set-valued) we present some of them using metric regularity on the set-valued map. Then, instead of considering this metric regularity assumption, we prefer assumptions which are directly connected to the solution, that are semistability and hemistability. One can note that semistabily of a solution x̅ of the inclusion 0∈G(x) is actually equivalent strong metric subregularity on the set-valued map G at x̅ for 0. After having presented some methods using semistability and hemistability, we show the new results we obtained, most of them being improvement of the presented methods. What we mean by improvement is mainly a better convergence rate on the one hand, and weaker assumptions that lead to similar convergence rate, on the other.

http://www.theses.fr/2012AGUY0594/document