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

Réseau original

1.2.3.

https://upload.wikimedia.org/wikipedia/commons/f/f1/Graphe_du_r%C3%A9seau.jpg

4. Liste d’adjacence

Sommets	Successeurs
VICTOR :	[Piano, Basket-ball, Karaté, Écrire, Cinéma, Raclette, Fondue, Risotto, Alaska, États-Unis, Jordanie, Lire, Sushis, Théâtre]
THIBAUD :	[Guitare, Lire, Istanbul, Kaboul, Sushis, Lasagnes, Écrire, Piano]
ZÉLIE :	[Chanter, Scoutisme, Buenos Aires, Montréal, Théâtre, Raclette, Piano]

5.

• Pour obtenir le degré de sortie d’un nœud, il faut additionner le nombre d’éléments figurant dans la liste d’adjacence de ce même nœud.
• Pour obtenir le degré d’entrée de chaque nœud, il faut compter le nombre de fois que ce nœud apparaît comme successeur dans la liste d’adjacence.

Ainsi, on obtient : d-(VICTOR) = 0 d+(VICTOR) = 14 d-(THIBAUD) = 0 d+(THIBAUD) = 8 d-(ZÉLIE) = 0 d+(ZÉLIE) = 7 Pour tout autre nœud X, on a d+(X) = 0, car notre graphe est orienté des individus vers les éléments.

d-(Piano) = 3 d-(Lire) = 2 d-(Écrire) = 2 d-(Raclette) = 2 d-(Théâtre) = 2 Pour tout autre nœud X, on a d-(X) = 1, correspondant à l’unique individu lié à cet élément.

6.

Nous sommes face à un graphe biparti, voire N-parti, car il y a des groupes de nœuds qui ne se lient pas entre eux. En effet, au niveau des individus, le graphe se compose de trois étoiles qui ne sont pas directement liées.

7.

Le diamètre ne peut pas être calculé, car il n’y a aucun aller-retour possible entre chaque paire de nœuds présents dans le graphe. Il est possible de se diriger vers un nœud, mais impossible de passer ensuite à un nouveau nœud ou de revenir au nœud précédent.

Réseau projeté

8.9.

https://upload.wikimedia.org/wikipedia/commons/8/85/Graphe_du_r%C3%A9seau_projet%C3%A9.jpg

10. Matrice d’adjacences

	Lire	Sushis	Piano	Théâtre	Raclette	Écrire
Lire	0	2	2	1	1	2
Sushis	2	0	2	1	1	2
Piano	2	2	0	2	1	2
Théâtre	1	1	2	0	2	1
Raclette	1	1	1	2	0	1
Écrire	2	2	2	1	1	0

Notre graphe n’étant pas un graphe simple (ex : sur une même arête, on peut avoir deux individus), la matrice d’adjacence n’est pas uniquement remplie avec des 0 ou 1.

11.

C’est un graphe non orienté, donc il n’y a pas de distinction entre degré de sortie et degré d’entrée. Ainsi, le degré de chaque nœud est obtenu en additionnant les lignes ou colonnes de la matrice d’adjacences.

On obtient donc : d(Lire) = 8 d(Sushis) = 8 d(Piano) = 9 d(Théâtre) = 7 d(Raclette) = 6 d(Écrire) = 8

12.

Ce n’est pas un réseau biparti, car tous les nœuds sont liés entre eux.

13.

Le diamètre est la plus grande distance entre deux sommets du réseau. Le diamètre de notre réseau est le suivant : ∆(Réseau) = 5

14.

Il y a un lien entre toutes les paires de nœuds distincts. Le graphe est alors connexe et il n’existe pas de sous-graphes connexes disjoints, car notre graphe est connexe dans sa globalité. En théorie, on pourrait donc dire qu’on a 1 seule composante connexe.

Réseau projeté II

9.10.

https://commons.wikimedia.org/wiki/File:R%C3%A9seau_Projet%C3%A9_II_(sur_les_individus).jpg

11. Matrice d’adjacence

	Victor	Thibaud	Zélie
Victor	0	4	3
Thibaud	4	0	1
Zélie	3	1	0

12.

Comme précédemment, nous sommes toujours face à un graphe non-orienté, il n’y a donc pas de distinction entre degré d’entrée et degré de sortie. Ainsi, le degré de chaque noeud est obtenu en additionnant les lignes ou colonnes de la matrice d’adjacence. On obtient alors : d(Victor) = 7, d(Thibaud) = 5 et d(Zélie) = 4

13.

Ce n’est pas un réseau biparti, car les groupes de noeuds sont liés entre eux. La forme triangulaire du graphe nous indique qu’il est complet.

14.

Pour rappel, le diamètre est la plus grande distance entre deux sommets du réseau. Dans notre graphe non-orienté, comme tous les noeuds sont liés entre eux, le diamètre du réseau est : ∆(Réseau) = 1

15.

Comme précédemment, notre graphe est connexe dans sa globalité. En effet, il n’existe pas de sous-graphes disjoints.