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

Réseau

Correction de mon activité

[ Cléa ] -> [ crepes ], [ gin ], [ rock ], [ macarena ], [ techno ], [ trompette ], [ piano ], [ course de fond ]
[ Hannah ] -> [ oeufs ], [ fromage ], [ st germain ], [ rock ], [ piano ], [ athlétisme ], [ tennis ], [ course de fond ]
[ Sarah ] -> [ sushis ], [ biere ], [ hip hop ], [ hip hop ], [ zumba ], [ charleston ], [ equitation ], [ tennis ], [ piano ]

Question 1

• Il y a une seule composante connexe, c'est tout le graphe, car par construction toutes les personnes sont liées à [ Cléa ], 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

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 : [ Cléa] – [ course de fond] ­– [ Hannah ] – [ rock] – [ Cléa] .

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

Noeuds	Entrant	Sortant	Non-orienté
Sarah	0	8	8
Hannah	0	8	8
Cléa	0	8	8
Piano	3	0	3
Course de fond	2	0	2
Tennis	2	0	2
Rock	2	0	2
15 autres noeuds	1	0	1

Degré	E	S	NO
0	0	0	0
1	15	0	15
2	3	0	3
3	1	0	1
8	0	3	3

Question 4

Mon réseau simplifié :

1. La matrice d'adjacence

Noeuds	Sarah	Hannah	Cléa	Piano	Course de fond	Tennis	Rock
Sarah	0	0	0	1	0	1	0
Hannah	0	0	0	0	1	1	1
Cléa	0	0	0	1	1	0	1
Piano	1	0	1	0	0	0	0
Course de fond	0	1	1	0	0	0	0
Tennis	1	1	0	0	0	0	0
Rock	0	1	1	0	0	0	0

2.1 Projections non-orientés :

• Sur les personnes :

[ Cléa ] - rock - [ Hannah ]
[ Cléa] - Piano - [ Sarah ]
[ Sarah ] - Tennis - [ Hannah ]
[ Hannah ] - Course de fond - [ Cléa ]
[ Hannah ] - Piano - [ Cléa ]
[ Hannah ] - Piano - [ Sarah ]

• Sur les objets :

[ Rock ] - Cléa - [ Piano ]
[ Piano ] - Cléa - [ Course de fond ]
[ Course de fond ] - Hannah - [ Tennis ]
[ Course de fond ] - Cléa - [ Rock ]
[ Rock ] - Hannah - [ Tennis ]
[ Piano ] - Sarah - [ Tennis ]

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 [ Course de fond ] à [ Sarah] ou de [ Tennis] à [ Cléa].

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 + 1 lien vers un objet, d'une telle sorte qu'on puisse circuler dans le graphe. Si on rajoute au graphe les liens :

[ Piano ] -> [ Sarah ]
[ Rock ] -> [ Hannah ]
[ Course de fond ] -> [ Cléa ]
[ Tennis ] -> [ Sarah ]

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