Utilisateur:Solstag/Modélisation des Réseaux (M1, 2018)/Activité B

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche

Je considère mon réseau du week-end fait pour l'activité A.

.

0) Dans une feuille papier, dessine-le en tant que réseau orienté, où chaque triplet se traduit dans deux liens: un liant le première élément au deuxième, un liant le deuxième au troisième.

Fait, voir feuille papier.

.

1) Répondez: est-ce un réseau biparti ?

Oui. Par exemple, les "verbes" ne se connectent que avec les "noms", qui à son tour ne se connectent que avec les "verbes". Comme il n'y a pas de connexion entre verbes, ni de connexion entre noms, ça fait deux partitions.

D'ailleurs, dans ce graphe on pourrait aussi trouver d'autres partitions, même des tripartitions ou plus.

.

2) Calculez le degré de chaque noeud.

Pour le noeud (Ale Abdo):

d- = 0, d+ = 10

Pour tous les autres "noms":

d- = 1, d+ = 0

Pour le noeud (accompagner):

d- = 2, d+ = 2

Pour tous les autres "verbes":

d- = 1, d+ = 1

.

3) Trouvez la plus grande distance entre tous les pairs de noeuds.

C'est 2.

Le pair orienté de noeuds à plus grande distance sont (Ale Abdo) et l'un des "noms" autres que (Ale Abdo). Par exemple la distance de (Ale Abdo) à (rêve) est 2, car il faut passer par (manger).

Cependant, il faut noter qu'il y a plein de distances qui ne sont pas définis, car il n'y a pas de chemin possible entre les noeuds. Par exemple, la distance de (rêve) à (Ale Abdo) n'est pas définie, car le réseau est orienté et il n'y a pas de chemin dans cette direction, même s'il existe un chemin dans le sens envers, c'est-à-dire, de (Ale Abdo) à (rêve).

.

4) Considérez l'union de ton réseau avec celui de la personne immédiatement précédente dans la liste de l'activité A. Combien de composantes fortement connexes a-t-il ? Explique.

Pour moi il n'y a pas de personne précédente, alors je prends la dernière de la liste: Marcsamsam.

Observant que le réseau est orienté, je note que pour aucun pair de noeuds il existe au même temps un chemin de aller et un chemin de retour. C'est à dire: pour chaque pair des noeuds A et B, il n'y a jamais à la fois un chemin de A à B et un chemin de B à A. Du coup, les composantes fortement connexes du réseau sont les noeuds individuels. On ne peut pas les regrouper en composantes fortement connexes. Il y a alors autant de composantes connexes que le nombre de noeuds.

.

5) Dans le réseau de l'item 4, si on ignore l'orientation des liens, c'est-à-dire si on prend les liens comme non orientés, combien de composantes connexes a-t-il ? Explique.

Si on ignore l'orientation des liens, on voit que:

  • Tous les noeuds de mon activité sont accessibles à travers (Ale Abdo).
  • Tous les noeuds de l'activité précédente sont accessibles à travers (Marc), sauf pour la ligne avec (Marc et ses parents).
  • Ces deux groupes de noeuds sont accessibles l'un à l'autre à travers le noeud (manger), présent dans mon réseau et dans celui précédent.
  • Les noeuds (Marc et ses parents), (aller) et (cinéma) sont accessibles entre eux, mais pas aux autres.

On a alors deux composantes connexes.

.