ED Mathématiques et Informatique
Problèmes de Distinction et de Détection dans les Graphes
par Clara MARCILLE (LaBRI - Laboratoire Bordelais de Recherche en Informatique)
Cette soutenance a lieu à 14h00 - Amphithéatre du LaBRI LaBRI (A33) 351 Cours de la Libération 33400 Talence
devant le jury composé de
- Hervé HOCQUARD - Professeur des universités - Université de Bordeaux - Directeur de these
- Julien BENSMAIL - Maître de conférences - Université Côte d'Azur - CoDirecteur de these
- Florent FOUCAUD - Maître de conférences - Université Clermont Auvergne - Examinateur
- Éric DUCHENE - Professeur des universités - Université Lyon 1 - Rapporteur
- Nicolas NISSE - Directeur de recherche - Université Côte d'Azur - Rapporteur
- Éric SOPENA - Professeur des universités - Université de Bordeaux - Examinateur
- Aline PARREAU - Chargée de recherche - Université Lyon 1 - Examinateur
- Cléophée ROBIN - Maîtresse de conférences - Université Paris Cité - Examinateur
Cette thèse traite de deux domaines à part en théorie des graphes. Dans la première partie, nous étudions l'irrégularité des graphes comme antonyme de la régularité. Nous nous concentrons sur des façons établies de distinguer les sommets adjacents par leurs degrés. Seuls certains graphes ont la propriété d'avoir toute paire de sommets adjacents de degrés distincts. Nous introduisons des façons d'étiqueter les arêtes d'un graphe, et considérons une fonction des étiquettes de ses arêtes incidentes au lieu du degré. Nous l'appelons somme résultante, et demandons qu'elle soit différente pour toute paire de sommets adjacents. Dans le domaine de la 1-2-3 Conjecture, introduite par Karoński et al., les étiquettes sont 1, 2, ou 3, et la somme résultante d'un sommet est la somme des étiquettes de ses arêtes incidentes. La 1-2-3 Conjecture dit que tout graphe connecté autre que K_2 peut être étiqueté, de sorte que les sommes résultantes de deux sommets adjacents soient distinctes. Une autre façon de rendre un graphe "irrégulier" est de le décomposer en partitionnant les arêtes pour que chaque part induise un graphe localement irrégulier. En ajustant la définition de somme résultante, les étiquettes et la condition de distinction, nous pouvons définir d'autres problèmes de distinction. Nous en introduisons de nouveaux et prouvons des liens entre eux. Dans le Chapitre 2, nous décomposons les graphes en graphes fortement localement irréguliers, où chaque part induit un graphe où les degrés de deux sommets adjacents diffèrent d'au moins 2. Dans le Chapitre 3, nous étudions une généralisation des décompositions localement irrégulières et des étiquetages d'arêtes, introduite par Baudon et al. Dans le Chapitre 4, nous étendons la définition d'étiquetages aux graphes signés, et nous donnons un formalisme pour les problèmes de distinction de cette thèse, que nous utilisons pour donner des énoncés et des résultats unifiés. Dans la deuxième partie, nous surveillons les réseaux pour détecter les défaillances, où les réseaux sont représentés par des graphes. Introduit par Foucaud et al., un ensemble de surveillance d'arêtes (MEG-set) d'un graphe est un ensemble de sondes sur les nœuds (sommets) qui se "ping" les unes les autres (mesurent leur distance les uns aux autres). Nous demandons également que les sondes soient placées de sorte que, s'il y a une défaillance dans le réseau (une arête est supprimée), les pings entre deux sondes changent (la distance augmente). Cette notion appartient à la famille des paramètres métriques, qui regroupe des façons de détecter des évènements dans un graphe en utilisant les distances entre les sommets. Nous étudions plusieurs questions relatives aux MEG-set. Les sondes étant coûteuses, nous voulons minimiser leur nombre. Ce problème étant NP-dur, nous étudions des graphes particuliers. Dans le Chapitre 6, nous étudions les graphes ayant un seul MEG-set minimal. Nous prouvons des propriétés de tous les MEG-set d'un graphe, qui donnent des algorithmes en temps polynomial pour calculer les MEG-set minimaux de plusieurs classes de graphes. Au Chapitre 7, nous prouvons que, si la recherche un MEG-set minimal est NP-dure, elle est FPT en la largeur de clique plus le diamètre du graphe d'entrée. Nous donnons aussi un algorithme qui produit un MEG-set plus grand que l'optimal par un facteur logarithmique de l'ordre du graphe d'entrée, mais qui s'exécute en temps polynomial. Nous prouvons aussi qu'un tel algorithme n'existe pas pour un facteur d'approximation constant. Enfin, dans le Chapitre 8, nous introduisons les MAG-set comme analogues aux MEG-set sur les graphes orientés, et les étudions pour plusieurs classes de graphes. Nous introduisons aussi deux problèmes de décision. L'un consiste à trouver la taille d'un MAG-set minimal, l'autre à trouver une orientation d'un graphe telle que le seul MAG-set soit l'ensemble des sommets. Nous prouvons que ces problèmes sont NP-durs.
ED Entreprise Economie Société
SITUATIONS FAMILIALES ET MOBILITES TOURISTIQUES : L'EFFET DES ENFANTS A CHARGE SUR LES SEJOURS HORS DOMICILE DES MENAGES DE FRANCE METROPOLITAINE
par Yuejia SUN (COMPTRASEC - Centre de Droit Comparé de Travail et de la Sécurité Sociale)
Cette soutenance a lieu à 14h30 - 250 Salle des thèses de la faculté de droit COMPTRASEC - UMR CNRS 5114 Université de Bordeaux 16 avenue Léon Duguit 33608 Pessac Cedex
devant le jury composé de
- Christophe BERGOUIGNAN - Professeur des universités - Université de Bordeaux - Directeur de these
- Frédéric SANDRON - Directeur de recherche - Université Paris Descartes - Rapporteur
- Claire SCODELLARO - Maîtresse de conférences - Université Paris 1-Panthéon-Sorbonne - Rapporteur
- Didier BRETON - Professeur des universités - Université de Strasbourg - CoDirecteur de these
- Jacques VERON - Directeur de recherche émérite - Institut national d'études démographiques - Examinateur
Cette thèse explore l'influence de la structure du ménage sur la participation, la fréquence et la durée des séjours, ainsi que les dépenses lors du dernier séjour, et la distance, les motifs, et destinations en introduisant une nouvelle mesure de la charge relative d'enfant, qui tient compte de l'âge des individus en charge de ces enfants. En établissant un lien entre la perspective du parcours de vie, les contraintes de loisirs et les pratiques culturelles, un cadre révisé permet de saisir de manière plus nuancée les responsabilités liées aux enfants et leur influence sur les pratiques de tourisme familial. En utilisant les données de l'enquête sur le budget des ménages français de 2017, les résultats montrent que, loin d'être une contrainte structurelle, la charge d'enfant relative affecte les pratiques de séjour, ce qui implique que la recherche devrait aller au-delà de l'approche habituelle consistant à ne prendre en compte que la présence et le nombre d'enfants, afin de mieux refléter les divergences temporelles dans le calendrier de la parentalité.