Utilisateur:Solstag/Modélisation des Réseaux (M1, 2018)/Activité B
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 nœud.
Pour le nœud (Ale Abdo):
d- = 0, d+ = 10
Pour tous les autres "noms":
d- = 1, d+ = 0
Pour le nœud (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 nœuds.
C'est 2.
Le pair orienté de nœuds à 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 nœuds. 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 nœuds il existe au même temps un chemin de aller et un chemin de retour. C'est-à-dire: pour chaque pair des nœuds 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 nœuds individuels. On ne peut pas les regrouper en composantes fortement connexes. Il y a alors autant de composantes connexes que le nombre de nœuds.
.
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 nœuds de mon activité sont accessibles à travers (Ale Abdo).
- Tous les nœuds de l'activité précédente sont accessibles à travers (Marc), sauf pour la ligne avec (Marc et ses parents).
- Ces deux groupes de nœuds sont accessibles l'un à l'autre à travers le nœud (manger), présent dans mon réseau et dans celui précédent.
- Les nœuds (Marc et ses parents), (aller) et (cinéma) sont accessibles entre eux, mais pas aux autres.
On a alors deux composantes connexes.
.