Construction d'un graphe connexe

[mothinx]

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.

[fatal_error]

salut,

ya sûrement une astuce où une réflexion derrière qui permette de régler ca joliment.
En attendant, voici une solution informatique avec Prolog :-)

Tu représentes les relations des noeuds par une matrice d'adjacence M composée de 0 et de 1 de taille (33x33).
Donc on pose 33x33 variables dans le domaine [0..1]

On traduit tes hypothèses :
pour aller d'un noeud quelconque x a un noeud quelconque y, le chemin est de longueur au plus 4.
On calcule M^2^2=M^4.
M^4 est valide si tous ses coefficiens sont strictement compris entre 0 et 5.

La deuxième hypothèse :
Il y a au plus 4 arretes qui passent par un noeud. Autrement dit, chaque noeud est connecté a au plus 4 autres noeuds.
Il suffit alors de poser comme contrainte
pour une ligne, la somme des coefficients est inférieure ou égale a 4.

Je me suis basé sur un graphe non orienté, donc M est symétrique et c'est pas la peine de poser des contraintes sur les colonnes.
Après, si ton graphe est orienté, ca change pas bcp bcp.

A tester :-)

[Ben314]

Je ne connais pas grand chose à la théorie des graphes, mais la question
sous jacente à tont problème :
" Soient a et b deux entier (au moins égaux à 2). Quelle 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 du graphe quelconque soient toujours à une distance inférieure ou égal à b"
me semble un casse-tête trés interessant.
Je ne connais pas la réponse, mais je cherche...
(je me demande s'il ne vaudrait pas mieux mettre la question dans "divertissement"...)

Je me demande si ce serait utile de représenter les 33 points sur un cercle (i.e. calculer modulo 33: 0,1,...,32,0,1,...), de commencer par mettre à chaque sommet une arête vers le suivant (et le précédent) puis de mettre des "paserelles" bien senties aux bons endroits (type pour les sommets de numéro multiple de 3 je met une paserelle vers le sommet 8 cases plus à droite....)

En tout cas trés interessant (pour moi)

[Ben314]

Je pense avoir une solution pour la question de départ (33 sommets...)
Comme j'ai recopié ta question dans 'enigme' je met la réponse dans 'enigme'...