Maths D Ulm 2016
Maths D Ulm 2016
Bonjour à tous!
Je me suis récemment attaqué au sujet de mathématiques D d’ULM de 2016, traitant des graphes finis et de leurs propriétés spectrales. Voilà un lien vers l’énoncé: https://www.ens.psl.eu/IMG/file/concour ... _mathd.pdf
En composant, je me suis senti freiné par mon incompréhension de l’endomorphisme $ T_{G} $, défini à la 2ème page. J’ai vraiment du mal à voir ce qu’il représente concrètement. Quelqu’un aurait-il une idée?
Merci d’avance !
Je me suis récemment attaqué au sujet de mathématiques D d’ULM de 2016, traitant des graphes finis et de leurs propriétés spectrales. Voilà un lien vers l’énoncé: https://www.ens.psl.eu/IMG/file/concour ... _mathd.pdf
En composant, je me suis senti freiné par mon incompréhension de l’endomorphisme $ T_{G} $, défini à la 2ème page. J’ai vraiment du mal à voir ce qu’il représente concrètement. Quelqu’un aurait-il une idée?
Merci d’avance !
Re: Maths D Ulm 2016
J'ai sous les yeux le commentaire du sujet dans un livre de corrigés écrit par un collègue. Il mentionne que T_G est le laplacien du graphe G mais pas vraiment plus. A toi de t'accrocher à cette définition un peu rude
Professeur de maths MP Lycée Sainte-Geneviève
Re: Maths D Ulm 2016
Ça a bien l’air d’être ça! En cherchant « Laplacien de graphe » sur internet, je suis tombé sur les matrices laplaciennes, qui semblent correspondre à l’endomorphisme $ T_{G} $. Je vais m’y pencher, merci pour votre réponse!
Re: Maths D Ulm 2016
Bonjour,
$(T_Gf)(x)$ quantifie si $f(x)$ est plus grand ou plus petit en moyenne que le $f$ des voisins de $x$. En effet, $$(T_Gf)(x) = (f(x) - \text{moyenne de $f$ sur les voisins de $x$}) \times {\rm val }(x).$$ Par exemple, si $f$ a un max local en $x$, alors $(T_Gf)(x) \geqslant 0$. D'où l'idée d'appeler ça un laplacien (enfin, ce serait plutôt l'opposé d'un laplacien).
$(T_Gf)(x)$ quantifie si $f(x)$ est plus grand ou plus petit en moyenne que le $f$ des voisins de $x$. En effet, $$(T_Gf)(x) = (f(x) - \text{moyenne de $f$ sur les voisins de $x$}) \times {\rm val }(x).$$ Par exemple, si $f$ a un max local en $x$, alors $(T_Gf)(x) \geqslant 0$. D'où l'idée d'appeler ça un laplacien (enfin, ce serait plutôt l'opposé d'un laplacien).
Re: Maths D Ulm 2016
Tu peux aussi voir $ T_G $ comme un opérateur qui a $ f $ associe quelque chose qui ressemble à (l'opposé de) sa divergence.
Parce que $ \displaystyle\sum_{y\textrm{ voisin de } x}{f(x)-f(y)} = \displaystyle\sum_{y:d(x,y)=1}\dfrac{f(x)-f(y)}{d(x,y)} $ est la somme des coordonnées de $ {-\nabla_x f = \left(\dfrac{f(x)-f(y)}{d(x,y)}, y\textrm{ voisin de } x\right)\in\mathbb{R}^{\textrm{val}(x)}} $
$ \nabla_x f $ est un gradient de f en x au sens où chaque $ f(y)-f(x) $ est un incrément de $ f $ sur la plus petite distance possible (i.e avec voisin direct) autour de x, qui vaut 1.
Parce que $ \displaystyle\sum_{y\textrm{ voisin de } x}{f(x)-f(y)} = \displaystyle\sum_{y:d(x,y)=1}\dfrac{f(x)-f(y)}{d(x,y)} $ est la somme des coordonnées de $ {-\nabla_x f = \left(\dfrac{f(x)-f(y)}{d(x,y)}, y\textrm{ voisin de } x\right)\in\mathbb{R}^{\textrm{val}(x)}} $
$ \nabla_x f $ est un gradient de f en x au sens où chaque $ f(y)-f(x) $ est un incrément de $ f $ sur la plus petite distance possible (i.e avec voisin direct) autour de x, qui vaut 1.
Re: Maths D Ulm 2016
Et le laplacien classique est égal à la divergence du gradient, donc ces interprétations se rejoignent.
Re: Maths D Ulm 2016
Merci beaucoup pour ces interprétations, c’est beaucoup plus clair!