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 considérée.
Si l'on considère , je note
l'ensemble de ses voisins directs dans le graphe ou le réseau formé à partir de
, c'est à dire plus rigoureusement
. 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 ; mais je n'ai aucune idée de comment le démontrer et si cette conjecture est juste pour
.
Comment puis-je le démontrer ?
Je vous remercie par avance !
Bonjour Lupa99.
Il faudra faire par récurrence.
Fais déjà pour x = 0.
Visualise ceci : dans les voisins de x à distance 1 de 0 sont de la forme de d-uplets de d-1 zéros et un "1".
Bonjour.
Si , alors tu peux d'abord montrer dans un premier temps que ses voisins dans le réseau
sont les points de la forme
où
pour tout
,à l'exception d'un seul
en particulier qui vérifie
ou
.
C'est assez simple à montrer. Ensuite, il suffit de dénombrer. On voit clairement qu'il y a 2 voisins différents possibles pour , soit
voisins différents possibles.
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 :
(
sont les coordonnées dans une base
orthonormée).
Or, et
donc
.
(-->Est-ce un peu trop rapide comme passage ici ??-->)
Donc il existe tel que
Enfin en dénombrant le nombre de possibilités, on se retrouve bien avec possibilités, donc
voisins !
Ma preuve est elle correcte ?
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 .
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)
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.
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 :