Aller au contenu

Utilisateur:Emma Bourdit/Modélisation des Réseaux (M1 SIREN, 2020)/Activité B

Une page de Wikiversité, la communauté pédagogique libre.
  • RESEAU ORIGINAL

1. Emilia et Victor

3.

Réseau avec liens orientés

4. Emilia: {chanter, piano, guitare, volleyball, art, cinéma, Venise, Barcelone, Mexico City, pâtes brocoli} Victor: {ne joue pas d'instrument, piano, basket, karaté, théâtre, cinéma, Alaska, Jordanie, risotto, fromage,} Emma: {ne joue pas d'instrument, guitare, art, fromage, illustrations, montage, Chine, Japon}

5.

Pour les noeuds prénom (encadrés) :

d-(Emilia) = 0, d+(Emilia) = 12,

d-(Victor) = 0, d+(Victor) = 10,

d-(Emma) = 0, d+(Emma) = 8,

Il suffit d'additionner le nombre de noeuds contenus dans la liste correspondante pour avoir le degré de sortie

Pour tous les noeuds communs (en rouge) :

d-(guitare) = 2, d+(guitare) = 0, N-(guitare) = {Emilia, Emma}, N+(guitare) = rien

d-(l'art) = 2, d+(l'art) = 0, N-(l'art) = {Emilia, Emma}, N+(l'art) = rien

d-(cinéma) = 2, d+(cinéma) = 0, N-(cinéma) = {Emilia, Victor}, N+(cinéma) = rien

d-(piano) = 2, d+(piano) = 0, N-(piano) = {Emilia, Victor}, N+(piano) = rien

d-(ne joue pas d'instrument) = 2, d+(ne joue pas d'instrument) = 0, N-(ne joue pas d'instrument) = {Victor, Emma}, N+(ne joue pas d'instrument) = rien

d-(fromage) = 2, d+(fromage) = 0, N-(fromage) = {Victor, Emma}, N+(fromage) = rien

Il suffit d'additionner le nombre de fois où apparait le noeuds dans les listes pour avoir le degré d'entrée

Pour tous les autres noeuds :

d-() = 1, d+() = 0

Il suffit d'additionner le nombre de fois où apparait le noeuds dans les listes pour avoir le degré d'entrée

6. Dans un graphe biparti il y a des liens entre groupes mais pas au sein des groupes, ici c'est la cas. Chaque graphe biparti peut être projeté dans chacune de ses bipartitions. Les trois noeuds prénoms forment une bipartition et les autres noeuds forment la seconde bipartition. Il s'agit bien d'un graphe biparti.

7. Le diamètre est la plus grande distance entre tous les noeuds d’une composante. Ici on ne peut pas le calculer car il n'y a pas de chemin possible qui dépasse un noeud.

Correction : Il s'agit d'un graphe très peu connecté. Il n'y a pas de diamètre pour ce réseau car il n'y a pas de chemin entre tous les nœuds. On peut noter que le chemin le plus long est de longueur 1.


  • RESEAU PROJETE

9.

Nouveau réseau projection

10.

Matrice d'adjacence du nouveau réseau

11.

d(guitare) = 6

d(piano) = 6

d(cinema) = 6

d(fromage) = 6

d(l'art) = 6

d(ne joue pas d'instrument) = 6

Il suffit d'additionner le nombre de liens répertoriés sur la ligne correspondant au noeud pour en connaître le degré. 

12. Ce n'est pas un réseau biparti puisqu'il y a des liens entre tous les noeuds.

13. Le diamètre est de 5.

14. Il n'y a qu'une composante connexe. Puisque tous les noeuds sont reliés entre eux.


  • RESEAU PROJETE II

10.

Réseau projeté II


11.

Matrice d'adjacence
EMILIA VICTOR EMMA
EMILIA 0 2 2
VICTOR 2 0 2
EMMA 2 2 0

12.

Pour connaître le degré d'un noeud, il suffit d'additionner le nombre de liens répertoriés sur la ligne lui correspondant. Il est également possible d'additionner la colonne du noeud correspondant puisque la matrice est symétrique car le graphe est non orienté.

Ainsi pour chacun des noeuds (Emilia, Victor et Emma) le degré est de 2.

13. Ce n'est pas un réseau biparti puisque tous les noeuds sont liés entre eux.

14. Le diamètre est la plus grande distance entre deux nœuds. On peut voir sur le dessin que la plus grande distance serait de passer par le noeud restant (par exemple de Emma à Emilia en passant par Victor). Le diamètre est donc de 2.

15. Une composante est un sous réseau ou il y a des chemins entre tous les noeuds. Tous les noeuds sont liés, il n'y a donc qu'une seule composante connexe.