Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 19-02-2018 11:47:07

algo3
Invité

algorithme et arbre

salut
Etant donné un réseau informatique  sous forme d'un arbre, où chaque PC represente un noeud (2 PC donnés sont reliés par un chemin unique de cables). on relie le reseau à internet au niveau d'un noeud donné. tel que si il y a rupture au niveau de n'importe quel cable. un minimum de PC  seront déconnectés du web. je cherche un algo. ( non nécéssairement optimal) pour trouver ou il faudra connecté le reseau sur le web.

#2 20-02-2018 10:38:52

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : algorithme et arbre

Bonjour,

Pour que la rupture d'un câble déconnecte un minimum de machines, il faut que la liaison avec Internet soit établie au voisinage de la racine, et que dans la même région le degré de chaque noeud soit maximal.

Exemple: si la racine (N1) est reliée à quatre noeuds voisins (N2 ... N5), eux-même racines de 4 sous-graphes d'importance comparable, il y aura au pire déconnexion du quart des ordinateurs.

Le noeud en liaison directe à Internet le plus avantageux sous ce rapport est celui (ou l'un de ceux) pour lequel (ou lesquels) la plus petite distance aux noeuds les plus éloignés est maximale (ou proche du maximum).
Il est difficile d'être plus précis faute d'informations sur la structure du graphe étudié.

# Il me vient une une idée simple: supprimer toutes les extrémités des branches du graphe (noeuds de degré 1); le renouvellement de l'opération jusqu'à disparition quasi-totale des sommets conduira à une suite de matrices d'adjacence (M0, M1, ... Mn) présentant un nombre décroissant d'éléments non-nuls.
Les derniers noeuds épargnés par cet élagage devraient constituer des solutions intéressantes, sinon optimales.

Dernière modification par Wiwaxia (20-02-2018 10:58:23)

Hors ligne

#3 20-02-2018 12:34:14

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : algorithme et arbre

# Autre solution, non destructrice: travailler sur un graphe à sommets valués, en attribuant à chaque noeud une valeur entière, initialisée à 255 par exemple (une variable au format Byte devrait suffire pour cela).

Attribuer la valeur (0) à tous les noeuds en fin de chaîne (de degré un), puis la valeur (1) à tous leurs voisins immédiats, et ainsi de suite jusqu'à valuation de tous les sommets ... On mesure ainsi la distance de chacun d'eux aux frontières du graphe; cela permet de repérer le (ou les) noeud(s) les plus éloignés des bords - il peut y en avoir plusieurs - et donc les plus intéressants pour la question envisagée.

Hors ligne

#4 20-02-2018 20:14:52

algo3
Invité

Re : algorithme et arbre

salut.
merci pour votre aide  Wiwaxia. je vais essayer d'implementer ça sur python. et je vais voir ce que ça donne.

Pied de page des forums