Bonjour, on va essayer de créer un réseau de neurones qui doit vérifier : 2 neurones sont toujours connectés directement ou connectés indirectement via un unique neurone intermédiaire sur le chemin.
Ex : A<->B<->C connecte directement A avec B et B avec C mais aussi indirectement A avec C car seul B est un neurone intermédiaire.
Chaque neurone possède au maximum connections directes, quelle est la valeur minimale de ?
1) Pour avec croisement autorisé des connections et sans croisement autorisé des connections
2) Pour avec croisement autorisé des connections et sans croisement autorisé des connections
je m'en doutais bien sûr et c'était pour te titiller !!
sans aucune prétention mais avec uniquement de l'intuition je dirai que quelle que soit la situation (croisement ou non) que c > n/2 (avec peut-être un = même)
et que c ne me semble pas proportionnel à n
en notant c pour "avec croisement" et C pour "sans croisement" je dirai évidemment que :
C > c
c(8) = 5et peut-être 4
c(16) € {8, 9} et peut-être même 10
il faudrait bien évidemment commencer avec n € {4, 5} et un schéma mais c'est pour faire avancer le schmilblick et appâter le chaland !!
Bonsoir,
Je considère les graphes avec croisement possible, comme si on était dans un espace à trois dimensions.
@Verdurin : je ne pense pas que tu puisses relier deux sommets opposés d'un cube en suivant les arêtes et avec un seul sommet intermédiaire .
Imod
Avec c=4, on peut traiter 10 points.
Mais on voit que pour relier A à N par exemple, on a 3 chemins possibles, en passant par E, J ou M.
Donc c'est loin d'être optimisé. On imagine que c=4 permet d'avoir n plus grand que 10.
Probablement n=15.
Les 2 options sont demandées.
Sans croisement, j'ai l'impression qu'on va vite avoir des limites sur n.
A l'opposé, si les croisements sont autorisés, on va vite arriver à des dessins illisibles.
Exercice amusant en tout cas.
En effet mais la multiplication des questions dilue l'intérêt
On peut sûrement montrer que pour n=8 avec un graphe planaire , c=3 ne convient pas . Cela rappelle le problème des trois maisons qu'il faut connecter aux réseaux d'eau de gaz et d'électricité .
Imod
Peut-être mais la multiplication des questions fait durer le plaisir
En tout cas, je suis d'accord avec Imod pour un graphe planaire (donc sans croisement) mais pas avec croisement où on peut faire justement.
Les figures d'Imod montre aussi un graphe sans croisement pour neuf points.
Peut-on avoir plus de neuf points dans un tel graphe ?
Pour 16 points en autorisant les croisements on peut faire c=6 , c'est sans doute perfectible :
Imod
J'ai tenté l'approche inverse, on se fixe c, et on regarde quelles valeurs de n on peut atteindre.
Je m'autorise les croisements.
Je fais un dessin avec un point central, il est relié à c points qui sont sur un premier cercle.
Et chacun de ces c points est relié à c-1 points sur un second cercle.
Notons B le point central, Bi les points du premier cercle, et Bij les points du 2nd cercle : pour i fixé, i=1 par exemple, le point B1 est relié aux points B1k par un segment. Les B1k sont les enfants de B1.
A ce niveau, le point central est bien en liaison avec tous les autres.
Tous les points du 1er cercle sont en liaison entre eux (en passant par le point central), et on peut tracer encore c-1 segments à partir de points du 2nd cercle.
On doit a priori pouvoir choisir ces segments pour que tous les points du réseau soient connectés.
Il faut que chaque enfant de B1 soit relié à un enfant de chacun des Bi, et il faut qu'entre 2 points M et N, il y ait un chemin unique ( de 1 segment ou 2 segments). Si il y a 2 points M et N pour lesquels il y a 2 trajets possibles, alors il y aura un autre point P qui ne sera pas connecté à M.
Pour c fixé, on pourrait donc avoir n=1+c+c(c-1) = c²+1.
Je dis 'pourrait' , au conditionnel, parce que pour c=4 ou 5, je n'ai pas trouvé le dessin qui convient.
Mais je pense que c'est possible.
A chacun son angle d'attaque et c'est bien comme ça .
Je crois plutôt en une solution symétrique en chacun des points par exemple pour c=4 , on peut atteindre 11 points sur un cercle ( mais pas plus ) :
Mais tu trouveras peut-être mieux
Imod
Pour 11 points, il n'y a pas de solution avec c=3. C'est certain.
Si c=3, un point A a au maximum 3 enfants, et 3x2=6 petits enfants.
Il peut donc être relié au maximum à 9 autres points.
Donc pour n=11 points, ta solution avec c=4 est optimale.
Mais, je conjecture que pour c=4, on peut aller jusqu'à n=17
Sur ton dessin, on voit qu'il y a beaucoup de redondances. Pour aller du point 1 au point 6, on peut passer par (1,5,6) ou par(1,2,6)
Et pareil pour aller de 1 à 4, on peut passer par (1,5,4) ou (1,0,4).
Il est clair qu'il y a des redondances mais c'est le plus "mauvais" point qui donne sa valeur à c . As-tu un exemple avec simplement : c=4 et n=12 ?
Imod
Si on ne peut pas faire mieux que le schéma dans le cercle :
n=3c-1 est le maximum pour c donné .
Imod
j'étais parti sur la même idée que Imod
il me semble que la figure suivante donne c = 5
j'ai commencé par tracer les diamètres AI, BJ, ... HP (un demi-tour suffit)
du points A les fils sont B, I et P et les petits fils sont C, H, J et O
pour éviter des redondances dons une certaines mesures (et donc trop d'arêtes) il faut "sauter" convenablement les points en pensant aux petits-fils : donc j'ai tracé les arêtes AK, BM, CN, ... en sautant de deux (mais il faut cette fois faire le tour complet)
les nouveaux fils de A sont F et L
ses nouveaux petits fils sont alors : D, E, G, K, M et N
et il me semble avoir fait le tour ...
Il reste à trouver le graphe planaire à 16 sommets . Pour le moment nous n'avons qu'un malheureux c=15
Imod
On peut faire c=14 sans problème avec quelque chose de ce genre :
Pour faire mieux il faut trouver une autre idée .
Imod
L'idée est bonne mais améliorable en distinguant 3 sommets particuliers au lieu de 2 sommets particuliers.
Voici une solution, pour c=5 et n=16.
La situation n'est pas tout à fait symétrique, il y a les 1+5 points centraux, et parmi les 10 autres points, il y a 2 groupes :
Le point H en haut à droite (vert foncé) est relié à tous les points vert clair par un simple trait, puis à tous les points jaunes par un chemin de 2 traits.
Le point I en haut à droite est relié par des traits rouges à 5 points, et par des traits oranges à tous les autres points. Chaque trait orange commence à la fin d'un trait rouge, et chaque point est à l'extrémité d'un trait rouge ou d'un trait orange.
j'arrive aussi à 12 malheureusement :
je travaille "par symétrie" (pour me faciliter le décompte et la vérif ensuite )
mais cela crée de nombreux chemins redondants
par exemple ACF et AEF et bien d'autres
peut-être une disposition des points en croix (ou en L) serait intéressante ...
Petit conseil : partez d'un triangle et essayez de le compléter avec la première idée de Imod qui donnait
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :