salut

dans le plan ou dans l'espace ?

Dans le plan pour parler de croisement, c'est quand même plus simple

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.

 Cliquez pour afficher

Pour n=4 un carré convient, donc c=2 pour n4.
Pour n=8 on dispose les neurones aux sommets d'un cube et les liaisons sur les arêtes, donc c=3 suffit pour n8
Pour n=16 on place les neurones aux sommets d'un hypercube 4D et les liaisons sur les arêtes  donc c=4 suffit.
Je conjecture que

@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

Salut Imod.
Tu as raison et j'ai tort.

Il manquait un petit bonjour à tous

J'ai c=4 pour n=8 :

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.

@Ty59847 : Les connexions ne doivent pas se croiser .

Imod

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.

Le cas non planaire est plus simple mais moins visuel :

Imod

Une autre illustration qui illustre mieux les symétries du problème :

Imod

Les figures d'Imod montre aussi un graphe sans croisement pour neuf points.
Peut-on avoir plus de neuf points dans un tel graphe ?

n=9 mais c=8 , rien de sensationnel

Imod

Disons que j'aimerais voir un graphe planaire avec plus de neuf neurones.
Je n'en trouve pas

Il suffit de remplacer l'octogone précédent par un polygone ayant plus de côtés .

Imod

En effet.

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, B_i les points du premier cercle,  et B_ij les points du 2nd cercle : pour i fixé, i=1 par exemple, le point B₁ est relié aux points B_1k par un segment. Les B_1k sont les enfants de B₁.
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 B₁ soit relié à un enfant de chacun des B_i, 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 ...

 Cliquez pour afficher

prions pour ne pas avoir fait d'erreur !!

Comment passes-tu de A à D ?

Imod

Oups , j'ai vu ( les lignes noires n'étaient pas visibles sur mon image ) .

Imod

Bien vu

Imod

Felicitations carpediem, je ne connais pas mieux que

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'ai réussi à gagner un point dans le cas planaire :

Peut-on encore améliorer ?

Imod

Oui, tu devrais pouvoir descendre jusqu'à , bon courage

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

Je suis arrivé à c=11 avec quelque chose dans ce genre , plus qu'un fil  à grignoter

Imod

en  tout cas joli !!

Je crois que j'ai réussi à attraper c=11 en changeant légèrement la construction précédente :

Imod

Je voulais dire c=10 bien sûr

Imod