Problème de graphe

par **Ben314** » 21 Nov 2009, 23:24

Je me permet de reprendre ici une question posée par "mothinx" dans la rubrique "scolaire>superieur" et qui me parait mieux adapté ici (ou dans olympiades)

Bonjour à tous,

Cela fait pas mal de temps que j'ai quitté les bancs de la fac, et au boulot un collégue m'a posé un probléme pour la construction d'un réseau télécoms.

Soit 33 noeuds (ou sommet), il faut les relier au maximum avec 4 arrêtes par noeuds et que le passage d'un noeud x à un noeud y ne dépasse pas 4 bonds.
Il faut trouver une représentation de ce réseau.

Une idée car pour moi le théoreme des graphe est trèsss loin !

merci à vous.

Evidement, le problème sous jacent est :
"Etant donné deux entiers A et D (pas trop petits !!), quel est le nombre maximal de sommet que peut avoir un graphe tel que de chaque sommet partent au maximum A arêtes et que 2 points quelconques du graphe soient toujours à une distance (sur le graphe) inférieure ou égal à D ?"

Si quelqu'un a ne serait-ce que la moitié du début d'une idée, je suis preneur...

par **nodgim** » 22 Nov 2009, 11:06

J'ai une solution avec 33 points. J'ai effectivement besoin de toutes les liaisons pour que ça marche, ce qui laisse penser que c'est bien un maximum.
C'est une configuration avec 1 point central et les 32 autres répartis sur 4 cercles concentriques. Le 32 n'a rien à voir avec la puissance 5ème de 2.
Je ne dévoile pas tout de suite la solution, mais les indications fournies sont déja une bonne piste. En principe, on trouve d'abord 29 points et les 4 pts supplémentaires se rajoutent à la fin.
Bonne recherche.

par **Ben314** » 22 Nov 2009, 11:12

La solution que j'ai trouvé semble pourtant permettre d'augmenter n : je vous la soumet :
L'idée est de commencer par faire un graphe dont les sommets sont les entiers relatifs:
Pour tout sommet de la forme :
N=3K => on met des arrêtes vers N-1 , N+1 et N+8
N=3K+1 => on met des arrêtes vers N-1 , N+1 , N-15 et N+15
N=3K+2 => on met des arrêtes vers N-1 , N+1 , N-8
sauf erreur de tout N on peut aller en moins de 4 arrêtes à tout les N+K avec -21<=K<=+21... (sauf si je m'est gourré)
Cela doit permettre de placer 42 sommets sur un cercle (on raisonne modulo 42 qui est bien un multiple de 3).
En plus, il me reste du "rab" en arrêtes...

par **nodgim** » 22 Nov 2009, 13:51

Il me semble que les 3k+1 ont 5 liaisons...

par **nodgim** » 22 Nov 2009, 14:29

ça marche bien en effet, en plus comme c'est périodique, la vérification est simple.
Bravo.

par **Ben314** » 22 Nov 2009, 16:47

oui, mais j'ai suis allé plus ou moins au pif.
Je ne sais pas si cela va en direction du max. ni comment faire pour le cas général (a et b)...
(tout ca juste pour dire que je considère le problème comme pas complètement résolu...)

par **nodgim** » 22 Nov 2009, 19:11

Non, en effet, car comme tu l'as dit, toutes les liaisons n'ont pas été utilisées. Voilà un problème ouvert.
On peut donner un max. absolu: 4*3*3*3=108.

par **Ben314** » 22 Nov 2009, 20:38

Oui, mais clairement trop grand...

par **nodgim** » 23 Nov 2009, 06:57

Attention, après une vérification supplémentaire, il semblerait qu'il faille 5 étapes pour arriver de 2 à 24.

par **Ben314** » 23 Nov 2009, 08:44

Je me suis effectivement gourré...
On peut joindre N à N+K avec K entre -18 et +18 (compris) cela ne permet q'un cercle de 36 points (c'est encore supérieur à 33 : OUF)

Je continue à y réfléchir....

par **nodgim** » 23 Nov 2009, 18:11

Aïe! j'espère me tromper, mais il me semble qu'il y a un problème pour passer de 3 à 15 cette fois, il faut 5 bonds.

par **Ben314** » 23 Nov 2009, 18:50

Il me semble que (ce coup ci) ca marche : partant de 3 je fait
-1 (=>2)
-1 (=>1)
+15 (=>16 car 1=3K+1)
-1 (=>15)

(c'est la même chose que de 0 à 12)
J'ai fait un petit programme, mais la première fois (avec le K de -21 à 21) j'ai mal lu l'affichage.... :petard:

par **nodgim** » 23 Nov 2009, 19:21

Oui, Ok, j'ai vu mon erreur.

par **Ben314** » 23 Nov 2009, 19:26

J'ai un peu complété les arêtes :

Pour tout sommet de la forme :
N=3K => on met des arrêtes vers N-1 , N+1 , N+8 et N+20
N=3K+1 => on met des arrêtes vers N-1 , N+1 , N-15 et N+15
N=3K+2 => on met des arrêtes vers N-1 , N+1 , N-8 et N-20

sauf erreur de tout N on peut aller en moins de 4 arrêtes à tout les N+K avec -23<=K<=+23...

d'ou (sur le cercle), 45 point (il faut (??) un multiple de 3)

par **nodgim** » 03 Déc 2009, 06:34

Un autre graphe à 39 points:
1:10 13 16 19
2:11 14 17 19
3:12 15 18 19
4,5, et 6: idem, en remplaçant 19 par 20
7,8 et 9: idem, en remplaçant 19 par 21
10:1 4 7 22
11:2 5 8 22
12:3 6 9 22
13,14 et 15: idem, en remplaçant 22 par 23
16,17 et 18: idem, en remplaçant 22 par 24
19:1 2 3 25
20:4 5 6 26
21:7 8 9 27
22:10 11 12 28
23:13 14 15 29
24:16 17 18 30
25:19 31 32 35
26:20 31 32 35
27:21 31 32 35
28:22 33 34 36
29:23 33 34 36
30:24 33 34 36
31:25 26 27 37
32:25 26 27 39
33:28 29 30 39
34:28 29 30 37
35:25 26 27 38
36:28 29 30 38
37:31 34
38:35 36
39:32 33

par **Ben314** » 03 Déc 2009, 21:54

Tu y est allé "au pif" (+/-) ?
Tu as fait un programme ?

par **nodgim** » 04 Déc 2009, 18:10

Ni au pif, ni programme :ptdr:
Par tatonnement, en dégradant un graphe "en éventail" (qui part d'un point raccordé à 4 autres pts, eux mêmes raccordés à 3 pts...). Juste pour voir si cette méthode pouvait améliorer le score.
Mais pour l'instant, c'est bien ta méthode et ses 45 pts qui donnent le meilleur résultat.

Problème de graphe

Problème de graphe

Qui est en ligne