Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Nombre de voisin d'une cellule d'un réseau carré, cubique...

Posté par
Lupa99
28-08-17 à 15:32

Bonjour,

Je cherche à démontrer le nombre de voisin qu'a une cellule d'un réseau carré, cubique, hypercubique...  quel que soit la dimension d considérée.
Si l'on considère x\in \mathbb{Z}^d, je note V(x) l'ensemble de ses voisins directs dans le graphe ou le réseau formé à partir de \mathbb{Z}^d, c'est à dire plus rigoureusement V(x)=\left \{ y \in \mathbb{Z}^d, ||x-y||=1 \right \}. Je cherche donc Card V(x) que je note pour simplifier k
Je me rend compte que pour d=1 :  k = 2, d=2 : k =4, d=3 : k=6.
Je conjecture donc que k = 2*d ; mais je n'ai aucune idée de comment le démontrer et si cette conjecture est juste pour d\geq 4.

Comment puis-je le démontrer ?

Je vous remercie par avance !

Posté par
jsvdb
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 28-08-17 à 15:39

Bonjour Lupa99.

Il faudra faire par récurrence.
Fais déjà pour x = 0.
Visualise ceci : dans \Z^d les voisins de x à distance 1 de 0 sont de la forme de d-uplets de d-1 zéros et un "1".

Posté par
WilliamM007
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 28-08-17 à 15:39

Bonjour.

Si x=(i_1,i_2,\cdots,i_d)\in\Z^d, alors tu peux d'abord montrer dans un premier temps que ses voisins dans le réseau \Z^d sont les points de la forme (j_1,\cdots,j_d)j_k=i_k pour tout 1\le k\le d,à l'exception d'un seul k_0 en particulier qui vérifie j_{k_0}=i_{k_0}+1 ou j_{k_0}=i_{k_0}-1.

C'est assez simple à montrer. Ensuite, il suffit de dénombrer. On voit clairement qu'il y a 2 voisins différents possibles pour 1\le k_0\le d, soit 2\times d voisins différents possibles.

Posté par
Lupa99
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 28-08-17 à 17:08

Merci pour vos réponse ! Je vais essayer les deux méthodes, mais j'ai déjà fais la deuxième :

Avec des notations évidentes :

Pour tout y\in V(x):
||x-y||^2 = \sum_{i=1}^d (x_i - y_i)^2 = 1 (x_i, y_i sont les coordonnées dans une base B orthonormée).
Or, x_i,y_i \in \mathbb{Z} et (x_i - y_i)^2 \leq 0 donc 0\leq(x_i - y_i)^2\leq 1.
(-->Est-ce un peu trop rapide comme passage ici ??-->)
Donc il existe i_0 \in [\![ 1; q]\!] tel que x_i-y_i = \pm 1

Enfin en dénombrant le nombre de possibilités, on se retrouve bien avec 2 \times d possibilités, donc 2 \times d voisins !

Ma preuve est elle correcte ?

Posté par
etniopal
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 28-08-17 à 17:25


On commence par remarquer que V(x) = x + V(O) pour tout x et qu'il suffit donc de dénombrer V(O) .

Si  y    V(O )  on a :   yk² = 1  donc il  existe un seul  k {1 ,..., n}  tel que yk² = 1 (puisue les yj sont des entiers )  .
V(O) est donc contenu dans { s(1)e1 + .... + s(n)en k , s(k) = 1 ou -1 } .
Comme l'inclusion inverse est évidente il y a égalité et V(O) est en bijection avec {- 1 , + 1}n qui a exactement 2n éléments  .

Posté par
Lupa99
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 28-08-17 à 17:39

Merci pour la remarque qui me permet de démontrer cela plus élégamment. Mais est-ce un propos qui m'a échappé ou il y a un problème avec la fin de votre démonstration ?

Je n'arrive pas à comprendre comme vous mettez ces deux ensembles en bijection, sachant de plus que pour d=3 (pour vous n=3), on a 6 voisins ? (et non pas 8)

Posté par
DOMOREA
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 28-08-17 à 18:46

bonjour,
c'est plus compliqué que cela !
regarde l'article hypercube de Wikipedia

Posté par
Lupa99
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 28-08-17 à 22:58

Je viens de voir cet article. Mais je précise que je parlais bien de voisin direct, et non pas de ceux aux "diagonales". Les voisins sont de même dimension, alors que dans la formule donné sur Wikipédia il s'agit de tout hypercube même de dimension inférieure.

Je pense que ma démonstration est juste ? (en remplaçant ma faute de frappe "q" par un d), donc techniquement si la démonstration est juste, la conjecture et donc le résultat le sont aussi ? Si vous voyez une erreur dans ma démo, n'hésitez pas à me le signaler.

Posté par
etniopal
re : Nombre de voisin d'une cellule d'un réseau carré, cubique.. 29-08-17 à 00:02

Je me suis trompé .
Après avoir démontré que si y est un voisin de O il existe un seul k tel que yk vérifie  yk² + 1 (et donc les autres  yj = 0 ) on conclut que V(O) est contenu dans { t.ek | t = 1 ou -1 , 1 k n } . L'inclusion inverse étant évidente , il y a 2n voisins de O dans  n .
Autant que de faces pour l'hyper-cube .

Si on prend la norme N : x Maxk(|xk) on en trouvera plus .



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !