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

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


Réseau[modifier | modifier le wikicode]

Je vois que, comme moi, Ewen joue la guitare, et Anna pratique le Yoga – et aimerais apprendre la guitare. Le réseaux est alors composé des liens :

[ Anna ] -> [ Yoga ], [ Piano ], [ Guitare ], [ Salsa ], [ Shurjpar ], [ Amatriciana ], [ Tolma ], [ Ghapama ]
[ Ewen ] -> [ Tacos ], [ Sushi ], [ Spritz ], [ HipHop ], [ Guitare ], [ Piano ], [ Basket ], [ Haltérophilie ], [ Natation ]
[ Solstag ] -> [ Forró ], [ Samba de Gafieira ], [ Papaye ], [ Avocat (gros) ], [ Jaboticaba ], [ Cuisine levantine ], [ Guitare ], [ Yoga ], [ Vélo ]
                                   ┌───────────────────────────────────────────┐
                                   │                                           │
                                   │                               ┌────────┐  │  ┌───────────────────┐
                                   │                               │ Papaye │  │  │ Samba de Gafieira │
                                   │                               └────────┘  │  └───────────────────┘
                                   │                                 ∧         │    ∧
  ┌────────────────────────────────┼────────┐                        │         │    │
  │                                ∨        │                        │         │    │
  │                   ┌─────────┐┌───────┐  │  ┌─────────────┐     ┌──────────────────────────────────┐     ┌───────────────────┐┌──────┐
  │                   │  Tolma  ││ Yoga  │  │  │ Jaboticaba  │ <── │                                  │ ──> │   Avocat (gros)   ││ Vélo │
  │                   └─────────┘└───────┘  │  └─────────────┘     │                                  │     └───────────────────┘└──────┘
  │                     ∧          ∧        │                      │                                  │                            ∧
  │                     │          │        └───────────────────── │                                  │ ───────────────────────────┘
  │                     │          │                               │             Solstag              │
  │  ┌──────────┐     ┌──────────────────┐     ┌─────────────┐     │                                  │     ┌───────────────────┐
  │  │  Salsa   │ <── │                  │ ──> │ Amatriciana │     │                                  │ ──> │ Cuisine levantine │
  │  └──────────┘     │       Anna       │     └─────────────┘     │                                  │     └───────────────────┘
  │  ┌──────────┐     │                  │     ┌─────────────┐     │                                  │     ┌───────────────────┐
  │  │ Shurjpar │ <── │                  │ ──> │   Ghapama   │     │                                  │ ──> │       Forró       │
  │  └──────────┘     └──────────────────┘     └─────────────┘     └──────────────────────────────────┘     └───────────────────┘
  │                     │          │
  │                     │          │
  │                     ∨          ∨
  │                   ┌─────────┐┌───────┐     ┌────────────────────────────┐     ┌───────────────────┐
  └─────────────────> │ Guitare ││ Piano │ <── │                            │ ──> │      Basket       │
                      └─────────┘└───────┘     │                            │     └───────────────────┘
                        ∧                      │                            │
                        └───────────────────── │                            │
                                               │            Ewen            │
                                 ┌───────┐     │                            │     ┌───────────────────┐
                                 │ Sushi │ <── │                            │ ──> │   Haltérophilie   │
                                 └───────┘     │                            │     └───────────────────┘
                                 ┌───────┐     │                            │     ┌───────────────────┐
                                 │ Tacos │ <── │                            │ ──> │      HipHop       │
                                 └───────┘     └────────────────────────────┘     └───────────────────┘
                                                 │                   │
                                                 │                   │
                                                 ∨                   ∨
                                               ┌─────────────┐     ┌────────┐
                                               │  Natation   │     │ Spritz │
                                               └─────────────┘     └────────┘

Question 1[modifier | modifier le wikicode]

  • Il y a une seule composante connexe, c'est tout le graphe, car par construction toutes les personnes sont liées à [ Solstag ], et tous les autres nœuds sont liés à au moins une personne.
  • Chaque nœud du graphe est une composante fortement connexe, car dans ce graphe il n'y a pas deux nœuds entre lesquels on puisse aller et revenir en prenant compte l'orientation des liens ; on ne peut que partir d'une personne et arriver à un nœud objet (non-personne), d'où on ne peut pas sortir.

Question 2[modifier | modifier le wikicode]

En ignorant l'orientation des liens :

  1. On ne trouve pas de triangles, car si on part d'un nœud personne [ A ] on ne peut qu'arriver à un nœud non-personne [ B ], et vice-versa. Donc le graphe est dans ce sens biparti : les personnes ne se connectent pas entre elles, et les nœuds objet ne se connectent pas entre eux. Un triangle exigerait donc une séquence du type [ personne A ] – [ objet X ] – [ personne B ] – [ personne A ], ou l'équivalant en partant d'un objet, ce qui n'est pas possible.
  2. Il n'y a pas de triangles (3 pas), mais on peut trouver un cycle à 4 pas : [ Anna ] – [ Guitare ] ­– [ Ewen ] – [ Piano ] – [ Anna ] .

En prenant en compte l'orientation des liens :

  1. L'orientation des liens restreignant les possibilités, s'il n'y avait pas de triangle non-orienté, il ne pourra pas avoir de triangle orienté non plus.
  2. Il n'y a pas de cycle dans ce graphe orienté. Comme on avait vu, chaque nœud est sa propre composante fortement connexe, et un cycle impliquerait un groupe de nœuds entre lesquels on peut passer librement.

Question 3[modifier | modifier le wikicode]

Les degrés du graphe :

Degrés
Nœud(s) Degré non-orienté Degré sortant Degré entrant
Solstag 9 9 0
Anna 8 8 0
Ewen 9 9 0
Yoga 2 0 2
Guitare 3 0 3
Piano 2 0 2
[ 19 autres nœuds ] 1 0 1

La distribution de degrés :

Quantité de nœuds par degré
Degré # Non-orienté # Sortant # Entrant
0 0 0 0
1 19 0 19
2 2 0 2
3 1 0 1
8 1 1 0
9 2 2 0
Distributions de degré
Non-orientée Sortante Entrante

Question 4[modifier | modifier le wikicode]

Mon réseau simplifié :

  ┌─────────────────────────────────────────────┐
  │                                             ∨
┌───────┐     ┌─────────┐     ┌─────────┐     ┌──────┐
│ Anna  │ ──> │ Guitare │ <── │ Solstag │ ──> │ Yoga │
└───────┘     └─────────┘     └─────────┘     └──────┘
  │             ∧
  │             │
  ∨             │
┌───────┐     ┌─────────┐
│ Piano │ <── │  Ewen   │
└───────┘     └─────────┘

1. La matrice d'adjacence :

A(i,j)
Solstag Anna Ewen Yoga Guitare Piano
Solstag 0 0 0 1 1 0
Anna 0 0 0 1 1 1
Ewen 0 0 0 0 1 1
Yoga 0 0 0 0 0 0
Guitare 0 0 0 0 0 0
Piano 0 0 0 0 0 0

2.1. Projections non-orientés :

  • Sur les personnes :
[ Solstag ] - Guitare - [ Ewen ]
[ Solstag] - Yoga - [ Anna ]
[ Ewen ] - Guitare - [ Anna ]
[ Ewen ] - Piano - [ Anna ]
  • Sur les objets :
[ Yoga ] - Anna - [ Guitare ]
[ Yoga ] - Anna - [ Piano ]
[ Yoga ] - Solstag - [ Guitare ]
[ Guitare ] - Anna - [ Piano ]
[ Guitare ] - Ewen - [ Piano ]

2.2 Diamètre non-orienté :

  • Il n'y a qu'une seule composante connexe et la plus grande distance est 3 et on la trouve pour aller de [ Piano ] à [ Solstag ] ou de [ Ewen ] à [ Yoga ].

3. Réseau fortement connexe :

Dans un réseau fortement connexe on peut partir et arriver entre n'importe quels deux nœuds. Cela implique que chaque nœud doit avoir au moins un lien entrant et un lien sortant.

Dans mon réseau, les personnes n'ont pas de lien entrant, il faudrait donc ajouter au moins 3 liens pour qu'on puise arriver à chacune des 3 personnes. A son tour, les objets aussi n'ont pas de lien sortant, même problématique. Voyons donc si on peut ajouter 3 liens partant des objets vers les personnes, d'une telle sorte qu'on puisse circuler dans le graphe. Si on rajoute au graphe les liens :

[ Guitare ] -> [ Solstag ]
[ Piano ] -> [ Ewen ]
[ Yoga ] -> [ Ana ]
  ┌─────────────────────────────────────────────────────────────────────────────────┐
  │                                                                                 │
  │                                                                                 │
  │    ┌────────────────────────────────────────────────────────────┐               │
  │    │                                                            │               │
  │    │                                                            │               │
  │    │                 ┌─────────────┐                            │               │
  │    │                 │             │                            │               │
  │    │                 │             │                            │               │
  │    │    ┌────────────┼─────────────┼────────────┐               │               │
  │    │    │            ∨             │            ∨               │               │
  │    │  ┌──────┐     ┌───────┐     ┌──────┐     ┌─────────┐     ┌─────────┐     ┌──────┐
  └────┼> │ Anna │ ──> │ Piano │ ──> │ Ewen │ ──> │ Guitare │ ──> │ Solstag │ ──> │ Yoga │
       │  └──────┘     └───────┘     └──────┘     └─────────┘     └─────────┘     └──────┘
       │    │                                       ∧                               ∧
       │    └───────────────────────────────────────┼───────────────────────────────┘
       │                                            │
       │                                            │
       └────────────────────────────────────────────┘

On voit que ça suffit pour qu'on puisse passer entre tous les nœuds du graphe, lui rendant fortement connexe !