Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles

The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.

Backbone Colouring of Graphs

Consider an undirected graph G and a subgraph of G, H. A q-backbone k-colouring of (G,H) is a mapping f: V(G) {1, 2, ..., k} such that G is properly coloured and for each edge of H, the colours of its endpoints differ by at least q. The minimum number k for which there is a backbone k-colouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone k-colouring of (G,T) is at most 4 if G is a connected C4-free planar graph or non-bipartite C5-free planar graph or Cj-free, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2-backbone k-colouring of any connected planar graphs without adjacent triangles is at most 4 by using a discharging method. In the second part of this thesis we further improve these results by proving that for any graph G with χ(G) ≥ 4, BBC(G,T) = χ(G). In fact, we prove the stronger result that a backbone tree T in G exists, such that ∀ uv ∈ T, |f(u)-f(v)|=2 or |f(u)-f(v)| ≥ k-2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.

Réorganisation fonctionnelle et structurale des cortex auditifs, visuels et associatifs chez les sourds profonds congénitaux ou prélinguaux

En raison de l’utilisation d’un mode de communication totalement différent de celui des entendants, le langage des signes, et de l’absence quasi-totale d’afférences en provenance du système auditif, il y a de fortes chances que d’importantes modifications fonctionnelles et structurales s’effectuent dans le cerveau des individus sourds profonds. Les études antérieures suggèrent que cette réorganisation risque d’avoir des répercussions plus importantes sur les structures corticales situées le long de la voie visuelle dorsale qu’à l’intérieur de celles situées à l’intérieur de la voie ventrale. L’hypothèse proposée par Ungerleider et Mishkin (1982) quant à la présence de deux voies visuelles dans les régions occipitales, même si elle demeure largement acceptée dans la communauté scientifique, s’en trouve aussi relativement contestée. Une voie se projetant du cortex strié vers les régions pariétales postérieures, est impliquée dans la vision spatiale, et l’autre se projetant vers les régions du cortex temporal inférieur, est responsable de la reconnaissance de la forme. Goodale et Milner (1992) ont par la suite proposé que la voie dorsale, en plus de son implication dans le traitement de l’information visuo-spatiale, joue un rôle dans les ajustements sensori-moteurs nécessaires afin de guider les actions. Dans ce contexte, il est tout à fait plausible de considérer qu’un groupe de personne utilisant un langage sensori-moteur comme le langage des signes dans la vie de tous les jours, s’expose à une réorganisation cérébrale ciblant effectivement la voie dorsale. L’objectif de la première étude est d’explorer ces deux voies visuelles et plus particulièrement, la voie dorsale, chez des individus entendants par l’utilisation de deux stimuli de mouvement dont les caractéristiques physiques sont très similaires, mais qui évoquent un traitement relativement différent dans les régions corticales visuelles. Pour ce faire, un stimulus de forme définie par le mouvement et un stimulus de mouvement global ont été utilisés. Nos résultats indiquent que les voies dorsale et ventrale procèdent au traitement d’une forme définie par le mouvement, tandis que seule la voie dorsale est activée lors d’une tâche de mouvement global dont les caractéristiques psychophysiques sont relativement semblables. Nous avons utilisé, subséquemment, ces mêmes stimulations activant les voies dorsales et ventrales afin de vérifier quels pourraient être les différences fonctionnelles dans les régions visuelles et auditives chez des individus sourds profonds. Plusieurs études présentent la réorganisation corticale dans les régions visuelles et auditives en réponse à l’absence d’une modalité sensorielle. Cependant, l’implication spécifique des voies visuelles dorsale et ventrale demeure peu étudiée à ce jour, malgré plusieurs résultats proposant une implication plus importante de la voie dorsale dans la réorganisation visuelle chez les sourds. Suite à l’utilisation de l’imagerie cérébrale fonctionnelle pour investiguer ces questions, nos résultats ont été à l’encontre de cette hypothèse suggérant une réorganisation ciblant particulièrement la voie dorsale. Nos résultats indiquent plutôt une réorganisation non-spécifique au type de stimulation utilisé. En effet, le gyrus temporal supérieur est activé chez les sourds suite à la présentation de toutes nos stimulations visuelles, peu importe leur degré de complexité. Le groupe de participants sourds montre aussi une activation du cortex associatif postérieur, possiblement recruté pour traiter l’information visuelle en raison de l’absence de compétition en provenance des régions temporales auditives. Ces résultats ajoutent aux données déjà recueillies sur les modifications fonctionnelles qui peuvent survenir dans tout le cerveau des personnes sourdes, cependant les corrélats anatomiques de la surdité demeurent méconnus chez cette population. Une troisième étude se propose donc d’examiner les modifications structurales pouvant survenir dans le cerveau des personnes sourdes profondes congénitales ou prélinguales. Nos résultats montrent que plusieurs régions cérébrales semblent être différentes entre le groupe de participants sourds et celui des entendants. Nos analyses ont montré des augmentations de volume, allant jusqu’à 20%, dans les lobes frontaux, incluant l’aire de Broca et d’autres régions adjacentes impliqués dans le contrôle moteur et la production du langage. Les lobes temporaux semblent aussi présenter des différences morphométriques même si ces dernières ne sont pas significatives. Enfin, des différences de volume sont également recensées dans les parties du corps calleux contenant les axones permettant la communication entre les régions temporales et occipitales des deux hémisphères.

La conjecture de partitionnement des chemins

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés.

Intervention orthophonique et neurobiologie du cerveau : apports de la neuroimagerie à la prise en charge de l’aphasie chronique

L’aphasie est un trouble acquis du langage entraînant des problèmes de communication pouvant toucher la compréhension et/ou l’expression. Lorsque l’aphasie fait suite à un accident vasculaire cérébral, une régression des déficits communicatifs s'observe initialement, mais elle peut demeurer sévère pour certains et est considérée chronique après un an. Par ailleurs, l’aphasie peut aussi être observée dans l’aphasie progressive primaire, une maladie dégénérative affectant uniquement le langage dans les premières années. Un nombre grandissant d’études s’intéressent à l’impact de la thérapie dans l’aphasie chronique et ont démontré des améliorations langagières après plusieurs années. L’hémisphère gauche semble avoir un rôle crucial et est associé à de meilleures améliorations langagières, mais la compréhension des mécanismes de plasticité cérébrale est encore embryonnaire. Or, l’efficacité de la thérapie dans l’aphasie progressive primaire est peu étudiée. À l’aide de la résonance magnétique fonctionnelle, le but des présentes études consiste à examiner les mécanismes de plasticité cérébrale induits par la thérapie Semantic Feature Analysis auprès de dix personnes souffrant d’aphasie chronique et d’une personne souffrant d’aphasie progressive primaire. Les résultats suggèrent que le cerveau peut se réorganiser plusieurs années après une lésion cérébrale ainsi que dans une maladie dégénérative. Au niveau individuel, une meilleure amélioration langagière est associée au recrutement de l’hémisphère gauche ainsi qu’une concentration des activations. Les analyses de groupe mettent en évidence le recrutement du lobule pariétal inférieur gauche, alors que l’activation du gyrus précentral gauche prédit l’amélioration suite à la thérapie. D’autre part, les analyses de connectivité fonctionnelle ont permis d’identifier pour la première fois le réseau par défaut dans l’aphasie. Suite à la thérapie, l’intégration de ce réseau bien connu est comparable à celle des contrôles et les analyses de corrélation suggèrent que l’intégration du réseau par défaut a une valeur prédictive d’amélioration. Donc, les résultats de ces études appuient l’idée que l’hémisphère gauche a un rôle prépondérant dans la récupération de l’aphasie et fournissent des données probantes sur la neuroplasticité induite par une thérapie spécifique du langage dans l’aphasie. De plus, l’identification d’aires clés et de réseaux guideront de futures recherches afin d’éventuellement maximiser la récupération de l’aphasie et permettre de mieux prédire le pronostic.

Caractérisation des complexes ribonucléoprotéiques de Staufen1 et Staufen2

Dans la cellule, chaque ARNm se doit d’être régulé finement au niveau transcriptionnel, bien entendu, mais également au niveau de sa traduction, de sa dégradation ainsi que de sa localisation intracellulaire, et ce, afin de permettre l’expression de chaque produit protéique au moment et à l’endroit précis où son action est requise. Lorsqu’un mécanisme physiologique est mis de l’avant dans la cellule, il arrive souvent que plusieurs ARNm se doivent d’être régulés simultanément. L’un des moyens permettant d’orchestrer un tel processus est de réguler l’action d’une protéine commune associée à chacun de ces ARNm, via un mécanisme post-traductionnel par exemple. Ainsi l’expression d’un groupe précis d’ARNm peut être régulée finement dans le temps et dans l’espace selon les facteurs protéiques auxquels il est associé. Dans l’optique d’étudier certains de ces complexes ribonucléoprotéiques (mRNP), nous nous sommes intéressés aux isoformes et paralogues de Staufen, une protéine à domaine de liaison à l’ARN double-brin (dsRBD) impliquée dans de nombreux aspects de la régulation post-transcriptionnelle, tels la dégradation, la traduction ou encore la localisation d’ARNm. Chez la drosophile, un seul gène Staufen est exprimé alors que chez les mammifères, il existe deux paralogues de la protéine, soit Stau1 et Stau2, tous deux possédant divers isoformes produits suite à l’épissage alternatif de leur gène. Stau1 et Stau2 sont identiques à 50%. Les deux isoformes de Stau2, Stau259 et Stau262 ne diffèrent qu’en leur extrémité N-terminale. En effet, alors que Stau259 arbore un dsRBD1 tronqué, celui de Stau262 est complet. Ces observations introduisent une problématique très intéressante à laquelle nous nous sommes attaqué : ces différentes protéines, quoique très semblables, font-elles partie de complexes ribonucléoprotéiques distincts ayant des fonctions propres à chacun ou, au contraire, vu cette similarité de séquence, travaillent-elles de concert au sein des mêmes complexes ribonucléoprotéiques? Afin d’adresser cette question, nous avons entrepris d’isoler, à partir de cellules HEK293T, les différents complexes de Stau1 et Stau2 par la technique d’immunoprécipitation. Nous avons isolé les ARNm associés à chaque protéine, les avons identifiés grâce aux micropuces d’ADN et avons confirmé nos résultats par RT-PCR. Malgré la présence d’une population commune d’ARNm associée à Stau1 et Stau2, la majorité des transcrits identifiés furent spécifiques à chaque orthologue. Cependant, nous avons remarqué que les diverses populations d’ARNm participaient aux mêmes mécanismes de régulation, ce qui suggère que ces deux protéines possèdent des rôles complémentaires dans la mise en œuvre de divers phénomènes cellulaires. Au contraire, les transcrits associés à Stau259 et Stau262 sont davantage similaires, indiquant que celles-ci auraient des fonctions plutôt semblables. Ces résultats sont très intéressants, car pour la première fois, nous avons identifié des populations d’ARNm associées aux isoformes Stau155, Stau259 et Stau262. De plus, nous les avons analysées en parallèle afin d’en faire ressortir les populations spécifiques à chacune de ces protéines. Ensuite, connaissant l’importance de Stau2 dans le transport dendritique d’ARNm, nous avons cherché à caractériser les complexes ribonucléoprotéiques neuronaux associés à celle-ci. Dans un premier temps et à l’aide de la technique d’immunoprécipitation, nous avons identifié une population d’ARNm neuronaux associés à Stau2. Plus de 1700 ARNm montraient une présence d’au moins huit fois supérieure dans le précipité obtenu avec l’anticorps anti-Stau2 par rapport à celui obtenu avec le sérum pré-immun. Ces ARNm codent pour des protéines impliquées dans des processus de modifications post-traductionnelles, de traduction, de transport intracellulaire et de métabolisme de l’ARN. De façon intéressante, cette population d’ARNm isolée du cerveau de rat est relativement différente de celle caractérisée des cellules humaines HEK293T. Ceci suggère que la spécificité d’association Stau2-ARNm peut diffèrer d’un tissu à un autre. Dans un deuxième temps, nous avons isolé les protéines présentes dans les complexes ribonucléoprotéiques obtenus de cerveaux de rat et les avons identifiées par analyse en spectrométrie de masse. De cette façon, nous avons identifié au sein des particules de Stau2 des protéines liant l’ARN (PABPC1, hnRNPH1, YB1, hsc70), des protéines du cytosquelette (α- et β-tubuline), de même que la protéine peu caractérisée RUFY3. En poussant davantage la caractérisation, nous avons établi que YB1 et PABPC1 étaient associées à Stau2 grâce à la présence de l’ARN, alors que la protéine hsc70, au contraire, interagissait directement avec celle-ci. Enfin, cette dernière association semble être modulable par l’action de l’ATP. Ce résultat offre de nombreuses possibilités quant à la régulation de la fonction de Stau2 et/ou de son mRNP. Entre autres, cette étude suggère un mécanisme de régulation de la traduction au sein de ces particules. Pour faire suite à la caractérisation des mRNP de Stau, nous avons voulu déterminer au niveau neurophysiologique l’importance de ceux-ci. Comme l’étude de Stau2 avait déjà été entreprise préalablement par un autre laboratoire, nous avons décidé de concentrer notre étude sur le rôle de Stau1. Ainsi, nous avons démontré que celle-ci était nécessaire à la mise en place d’une forme de plasticité synaptique à long terme, la forme tardive de potentialisation à long terme ou L-LTP, dépendante de la transcription et de l’activité des récepteurs NMDA. La transmission de base, de même que la faculté de ces épines à faire de la E-LTP, la forme précoce de potentialisation à long terme, et la dépression à long terme ou LTD sont conservées. Ceci indique que les épines conservent la capacité d’être modulées. Ainsi, l’inhibition de la L-LTP, suite à la sous-expression de Stau1, n’est pas simplement due à la perte d’éléments fonctionnels, mais réside plutôt dans l’incapacité de ceux-ci à induire les changements synaptiques spécifiquement nécessaires à la mise en place de la L-LTP. De plus, au niveau synaptique, la sous-expression de Stau1 réduit à la fois l’amplitude et la fréquence des mEPSC. Ces résultats concordent avec l’observation que la sous-expression de Stau1 augmente significativement la proportion d’épines allongées et filopodales, des épines formant des synapses dites silencieuses. Par le fait même, elle diminue le nombre d’épines fonctionnelles, de forme dite normale. Ainsi, nous avons été en mesure de démontrer que l’absence, au niveau neuronal, de la protéine Stau1 induisait un déficit probable dans la localisation et/ou la traduction d’ARNm responsable de la restructuration de l’épine et de facteurs nécessaires à la mise en place de la L-LTP. En conclusion, nous avons participé à lever le voile sur la composition et l’importance des complexes ribonucléoprotéiques de Stau1 et Stau2. Nous avons identifié des populations distinctes et communes d’ARNm associées aux différents isoformes de Stau, à partir des mRNP présents au sein des cellules HEK293. De plus, nous avons réussi à mettre à l’avant plan certaines composantes des mRNP neuronaux de Stau2, dont un partenaire protéique direct, hsc70, partenaire dont l’association est modulable par l’action de l’ATP, ainsi qu’une population neuronale de transcrits d’ARNm. Enfin, nous avons mis en lumière l’importance de Stau1 dans la morphologie des épines dendritiques ainsi que dans le phénomène de la plasticité synaptique.

Réorganisation neurofonctionnelle permettant le maintien des habiletés d’évocation lexicale lors du vieillissement

Le maintien de performances cognitives optimales au cours du vieillissement a été associé à des changements adaptatifs au niveau de l’activité cérébrale relative à diverses habiletés qui tendent à décliner avec l’âge. Peu d’études ont toutefois évalué cette réorganisation neurofonctionnelle dans le cadre des habiletés de communication, notamment en ce qui concerne le langage expressif. Or, considérant que plusieurs composantes langagières demeurent généralement intègres chez les aînés, il s’avère nécessaire d’explorer davantage les mécanismes cérébraux sous-jacents afin de mieux cerner les déterminants du vieillissement cognitif réussi. L’objectif de la présente thèse est d’examiner en détail les effets de l’âge sur les patrons d’activations et les interactions fonctionnelles entre les substrats neuraux contribuant aux habiletés de communication expressive. Deux études en neuroimagerie fonctionnelle, ayant recours à des approches méthodologiques distinctes, ont ainsi été menées à l’aide d’un paradigme mixte novateur et d’une tâche auto-rythmée d’évocation lexicale sémantique et orthographique, effectuée par des participants jeunes et âgés présentant plusieurs années de scolarisation. S’intéressant spécifiquement aux patrons d’activations associés à un rendement élevé à cette tâche, la première étude révèle que le maintien des habiletés d’évocation lexicale lors du vieillissement s’accompagne de changements neurofonctionnels superficiels chez les adultes âgés performants. Par contre, la seconde étude indique que les interactions fonctionnelles entre les régions corticales contribuant aux productions lexicales déclinent considérablement avec l’âge, sans qu’il y ait toutefois d’impact au plan comportemental. Cet effet du vieillissement sur l’intégration fonctionnelle du réseau de l’évocation sémantique et orthographique est aussi exacerbé par la difficulté de la tâche, ce qui s’exprime par des perturbations locales de la connectivité fonctionnelle. Somme toute, cette thèse démontre qu’une réorganisation neurofonctionnelle afin de maintenir les habiletés d’évocation lexicale au cours du vieillissement s’avère superflue chez les adultes âgés instruits et performants, et ce, malgré une diminution des interactions fonctionnelles au sein des réseaux corticaux sous-jacents. Ces résultats reflètent possiblement une perte d’efficience neurale avec l’âge, toutefois insuffisante pour avoir un impact comportemental chez des individus bénéficiant de facteurs de protection susceptibles de favoriser le vieillissement réussi, ce qui est discuté à la lumière du concept de réserve cognitive.

Réseaux, homophilie et discours de collaboration scientifique au Québec : étude comparée sur le capital social des chercheurs junior et senior (1990-2009)

Notre étude porte sur la manière dont les chercheurs universitaires junior et senior en sciences sociales au Québec établissent leurs réseaux de cosignataires et donnent une interprétation discursive à leurs activités de collaboration face à l'impact du changement institutionnel universitaire pendant la période 1990-2009. Plus spécifiquement, notre recherche s'intéresse à montrer que la création des réseaux et la collaboration scientifique par cosignature peuvent être identifiées comme des « ajustements professionnels » et se présenter aussi comme une ressource du capital social qui peut être mobilisé et qui peut produire des avantages aux chercheurs en accord avec leur statut junior ou senior. Il s’agit donc d’une recherche qui relève de la sociologie des sciences. Notre approche a été opérationnalisée à partir de l'étude de 15 membres d'un centre de recherche universitaire au Québec, et leur réseau de 447 cosignataires (y compris les chercheurs de l'étude), et à travers l'application de 7 entretiens auprès de chercheurs junior et senior du même centre. Dans le même plan opérationnel, depuis une perspective qualitative, la thèse permet d'identifier le sens discursif que les chercheurs fournissent à la collaboration et à la participation en réseaux de cosignatures. Ensuite, depuis l'analyse structurelle des réseaux, notre étude montre les connexions individuelles et leurs formes d'interprétation — spécialement la théorie des graphes et ses mesures de centralité (la centralité de degré, la centralité d’intermédiarité et la centralité de vecteur propre) — de même que l'homophilie par statut entre chercheurs. Enfin, depuis l'analyse statistique, elle montre la corrélation des périodes de l'étude et des attributs socioprofessionnels des chercheurs étudiés (sexe, statut universitaire, affiliation institutionnelle, discipline d’appartenance, pays, région du Canada et ville de travail). Notamment, les résultats de notre thèse montrent que chaque catégorie de chercheurs possède ses propres particularités structurelles et discursives en ce qui a trait à ses pratiques de collaboration en réseau, et vont confirmer que les chercheurs senior, plus que les chercheurs junior, grâce à leur capital social mobilisé, ont conservé et obtenu plus d'avantages de leur réseau de cosignataires afin de s'adapter au changement institutionnel et mieux gérer leur travail de collaboration destiné à l’espace international, mais surtout à l'espace local.

Évaluation de l’effet de faux souvenirs en vieillissement normal : validation de scores composites des fonctions temporale médiane et frontale et contribution aux hypothèses théoriques

L’avancement en âge est associé à plusieurs modifications cognitives, dont un déclin des capacités à mémoriser et/ou à rappeler les événements vécus personnellement. Il amène parallèlement une augmentation des faux souvenirs, c.-à-d. le rappel d’événements qui ne se sont pas réellement déroulés. Les faux souvenirs peuvent avoir d’importantes répercussions dans la vie quotidienne des personnes âgées et il importe donc de mieux comprendre ce phénomène en vieillissement normal. Des études ont démontré l’importance de la fonction des lobes temporaux médians (FTM)/mémoire et de la fonction des lobes frontaux (FF)/fonctions exécutives dans l’effet de faux souvenirs. Ainsi, la première étude de la thèse visait à valider en français une version adaptée d’une méthode proposée par Glisky, Polster, & Routhieaux (1995), permettant de mesurer ces fonctions cognitives (Chapitre 2). L’analyse factorielle de cette étude démontre que les scores neuropsychologiques associés à la mémoire se regroupent en un facteur, le facteur FTM/mémoire, alors que ceux associés aux fonctions exécutives se regroupent en un deuxième facteur, le facteur FF/fonctions exécutives. Des analyses « bootstrap » effectuées avec 1 000 ré-échantillons démontrent la stabilité des résultats pour la majorité des scores. La deuxième étude de cette thèse visait à éclairer les mécanismes cognitifs (FTM/mémoire et FF/fonctions exécutives) ainsi que théoriques de l’effet de faux souvenirs accru en vieillissement normal (Chapitre 3). La Théorie des Traces Floues (TTF; Brainerd & Reyna, 1990) propose des explications de l’effet de faux souvenirs pour lesquelles la FTM/mémoire semble davantage importante, alors que celles proposées par la Théorie de l’Activation et du Monitorage (TAM; Roediger, Balota, & Watson, 2001) sont davantage reliées à la FF/fonctions exécutives. Les tests neuropsychologiques mesurant la FTM/mémoire ainsi que ceux mesurant la FF/fonctions exécutives ont été administrés à 52 participants âgés (moyenne de 67,81 ans). Basé sur l’étude de validation précédente, un score composite de la FTM/mémoire et un score composite de la FF/fonctions exécutives ont été calculés pour chaque participant. Ces derniers ont d’abord été séparés en deux sous-groupes, un premier au score FTM/mémoire élevé (n = 29, âge moyen de 67,45 ans) et un deuxième au score FTM/mémoire faible (n = 23, âge moyen de 68,26 ans) en s’assurant de contrôler statistiquement plusieurs variables, dont le score de la FF/fonctions exécutives. Enfin, ces participants ont été séparés en deux sous-groupes, un premier au score FF/fonctions exécutives élevé (n = 26, âge moyen 68,08 ans) et un deuxième au score FF/fonctions exécutives faible (n = 25, âge moyen de 67,36 ans), en contrôlant les variables confondantes, dont le score de la FTM/mémoire. Les proportions de vraie et de fausse mémoire (cibles et leurres associatifs) ont été mesurées à l’aide d’un paradigme Deese-Roediger et McDermott (DRM; Deese, 1959; Roediger & McDermott, 1995), avec rappel et reconnaissance jumelée à une procédure « Je me souviens / Je sais » (Tulving, 1985) chez les 52 participants âgés ainsi que chez 22 jeunes (âge moyen de 24,59 ans), apparié pour les années de scolarité. D’abord, afin de tester l’hypothèse de la TTF (Brainerd & Reyna, 1990), ces proportions ont été comparées entre les jeunes adultes et les deux sous-groupes de personnes âgées catégorisées selon le score de la FTM/mémoire. Ensuite, afin de tester l’hypothèse de la TAM (Roediger et al., 2001), ces proportions ont été comparées entre les jeunes adultes et les deux sous-groupes de personnes âgées catégorisées selon le score de la FF/fonctions exécutives. Il s’agit de la première étude qui compare directement ces hypothèses à travers de nombreuses mesures de vraie et de fausse mémoire. Les résultats démontrent que seule la FTM/mémoire modulait l’effet d’âge en vraie mémoire, et de manière quelque peu indirecte, en fausse mémoire et dans la relation entre la vraie et la fausse remémoration. Ensuite, les résultats démontrent que seule la FF/fonctions exécutives jouerait un rôle dans la fausse reconnaissance des leurres associatifs. Par ailleurs, en des effets d’âge sont présents en faux rappel et fausse remémorations de leurres associatifs, entre les jeunes adultes et les personnes âgées au fonctionnement cognitif élevé, peu importe la fonction cognitive étudiée. Ces résultats suggèrent que des facteurs autres que la FTM/mémoire et la FF/fonctions exécutives doivent être identifiés afin d’expliquer la vulnérabilité des personnes âgées aux faux souvenirs. Les résultats de cette thèse sont discutés à la lumière des hypothèses théoriques et cognitives en faux souvenirs (Chapitre 4).

Studies on Fuzzy Graphs

In this thesis an attempt to develop the properties of basic concepts in fuzzy graphs such as fuzzy bridges, fuzzy cutnodes, fuzzy trees and blocks in fuzzy graphs have been made. The notion of complement of a fuzzy graph is modified and some of its properties are studied. Since the notion of complement has just been initiated, several properties of G and G available for crisp graphs can be studied for fuzzy graphs also. Mainly focused on fuzzy trees defined by Rosenfeld in [10] , several other types of fuzzy trees are defined depending on the acyclicity level of a fuzzy graph. It is observed that there are selfcentered fuzzy trees. Some operations on fuzzy graphs and prove that complement of the union two fuzzy graphs is the join of their complements and complement of the join of two fuzzy graphs is union of their complements. The study of fuzzy graphs made in this thesis is far from being complete. The wide ranging applications of graph theory and the interdisciplinary nature of fuzzy set theory, if properly blended together could pave a way for a substantial growth of fuzzy graph theory.

Antimedian graphs

Antimedian graphs are introduced as the graphs in which for every triple of vertices there exists a unique vertex x that maximizes the sum of the distances from x to the vertices of the triple. The Cartesian product of graphs is antimedian if and only if its factors are antimedian. It is proved that multiplying a non-antimedian vertex in an antimedian graph yields a larger antimedian graph. Thin even belts are introduced and proved to be antimedian. A characterization of antimedian trees is given that leads to a linear recognition algorithm.

Studies on the Spectrum and the Energy of Graphs

Department of Mathematics, Cochin University of Science and Technology

CoObRA: Eine Plattform zur Verteilung und Replikation komplexer Objektstrukturen mit optimistischen Sperrkonzepten

In der vorliegenden Arbeit wird die Konzeption und Realisierung der Persistenz-, Verteilungs- und Versionierungsbibliothek CoObRA 2 vorgestellt. Es werden zunächst die Anforderungen an ein solches Rahmenwerk aufgenommen und vorhandene Technologien für dieses Anwendungsgebiet vorgestellt. Das in der neuen Bibliothek eingesetzte Verfahren setzt Änderungsprotokolle beziehungsweise -listen ein, um Persistenzdaten für Dokumente und Versionen zu definieren. Dieses Konzept wird dabei durch eine Abbildung auf Kontrukte aus der Graphentheorie gestützt, um die Semantik von Modell, Änderungen und deren Anwendung zu definieren. Bei der Umsetzung werden insbesondere das Design der Bibliothek und die Entscheidungen, die zu der gewählten Softwarearchitektur führten, eingehend erläutert. Dies ist zentraler Aspekt der Arbeit, da die Flexibilität des Rahmenwerks eine wichtige Anforderung darstellt. Abschließend werden die Einsatzmöglichkeiten an konkreten Beispielanwendungen erläutert und bereits gemachte Erfahrungen beim Einsatz in CASE-Tools, Forschungsanwendungen und Echtzeit-Simulationsumgebungen präsentiert.

Meshing highly regular structures: The case of super carbon nanotubes of arbitrary order

Mesh generation is an important step inmany numerical methods.We present the “HierarchicalGraphMeshing” (HGM)method as a novel approach to mesh generation, based on algebraic graph theory.The HGM method can be used to systematically construct configurations exhibiting multiple hierarchies and complex symmetry characteristics. The hierarchical description of structures provided by the HGM method can be exploited to increase the efficiency of multiscale and multigrid methods. In this paper, the HGMmethod is employed for the systematic construction of super carbon nanotubes of arbitrary order, which present a pertinent example of structurally and geometrically complex, yet highly regular, structures. The HGMalgorithm is computationally efficient and exhibits good scaling characteristics. In particular, it scales linearly for super carbon nanotube structures and is working much faster than geometry-based methods employing neighborhood search algorithms. Its modular character makes it conducive to automatization. For the generation of a mesh, the information about the geometry of the structure in a given configuration is added in a way that relates geometric symmetries to structural symmetries. The intrinsically hierarchic description of the resulting mesh greatly reduces the effort of determining mesh hierarchies for multigrid and multiscale applications and helps to exploit symmetry-related methods in the mechanical analysis of complex structures.

An improved method for discovering link criticality in transport networks

Quantitatively assessing the importance or criticality of each link in a network is of practical value to operators, as that can help them to increase the network's resilience, provide more efficient services, or improve some other aspect of the service. Betweenness is a graph-theoretical measure of centrality that can be applied to communication networks to evaluate link importance. However, as we illustrate in this paper, the basic definition of betweenness centrality produces inaccurate estimations as it does not take into account some aspects relevant to networking, such as the heterogeneity in link capacity or the difference between node-pairs in their contribution to the total traffic. A new algorithm for discovering link centrality in transport networks is proposed in this paper. It requires only static or semi-static network and topology attributes, and yet produces estimations of good accuracy, as verified through extensive simulations. Its potential value is demonstrated by an example application. In the example, the simple shortest-path routing algorithm is improved in such a way that it outperforms other more advanced algorithms in terms of blocking ratio