Cayley Graphs: Propriétés et Applications

Dans cours

Description

Cette séance de cours couvre les propriétés et les applications des graphes de Cayley, en se concentrant sur leur structure, leur connectivité et leur utilisation dans la théorie de groupe et l'analyse de réseau. L'instructeur discute du concept de générateurs, des fonctions bi-Lipschitz et de la relation entre les graphiques de Cayley et les éléments de groupe.

Connectez-vous pour regarder la vidéo

Enseignant

Source officielle

https://mediaspace.epfl.ch/media/0_63w3j8fg

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Séances de cours associées (287)

Concepts associés (88)

Un gel (du lat. gelu : gel, froid, glace ou congelés; ou gelatus : gelé, immobile -) est un solide qui peut avoir des propriétés allant de mou et ductile à dur et cassant. Au niveau microscopique, ce sont des systèmes réticulés de longues chaînes moléculaires (macromolécules, souvent de type polymères) diluées, ne présentant aucun écoulement lorsqu'ils sont à l'état stable. En masse, les gels sont principalement constitués de liquide, mais ont un comportement proche de celui des solides grâce à leur réseau tridimensionnel enchevêtré au sein du liquide.

alt=Appareil à électrophorèse sur gel d'agarose|vignette|Appareil pour électrophorèse d'ADN en gel d'agarose. Le gel est horizontal baigne dans le tampon qui remplit la cuve. L'ADN est déposé dans des puits à une extrémité du gel. L'alimentation en arrière-plan fournit la tension électrique continue qui permet la migration des fragments d'ADN dans le gel. L'électrophorèse sur gel est une variante de l'électrophorèse de zones.

vignette|Cuve remplie de tampon et transformateur utilisés pour l'électrophorèse sur gel d'agarose. L'électrophorèse sur gel d'agarose est une méthode utilisée en biochimie et en biologie moléculaire pour séparer l'ADN, l'ARN ou des protéines en fonction de leur masse moléculaire. La technique de l'électrophorèse sur gel d'agarose est basée sur la séparation des acides nucléiques chargés négativement sous l'effet d'un champ électrique.

Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.

En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.