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

Question 1 et 2 : Listes choisies (Marine et Antoine)

Question 3 :

Question 4 :

Liste d'adjacence

Quentin:{Batterie,Clavier,Judo,Tokyo,Londres,Dar es Salaam,Panna Cotta,Houmous}

Marine:{Piano,Krav Maga,Lire,Sydney,Copenhague,Tokyo,Pizza,Smoothie,Saint Honoré}

Antoine:{Piano,Aviron,Vienne,Tokyo,Lire,Dormir,Pâte,Bière}

Question 5 :

À partir de la liste d'adjacence, on peut calculer le degré de sortie des nœuds en additionnant le nombre de nœud avec lesquels ils ont un lien. Ainsi on peut également obtenir le degré d'entrée de tous les autres nœuds car comme on est dans un graphe ordonné, il suffit de compter le nombre de fois qu'un nœud apparait dans les listes et on obtient son degré d'entrée.

D-(Quentin) = 8 D+(Quentin)=0

D-(Marine) = 9 D+(Marine)=0

D-(Antoine) = 8 D+(Antoine)=0

D-(Batterie)=0 D+(Batterie)=1

D-(Clavier)=0 D+(Clavier)=1

D-(Judo)=0 D+(Judo)=1

D-(Tokyo)=0 D+(Tokyo)=3

D-(Londres)=0 D+(Londres)=1

D-(Dar es Salaam)=0 D+(Dar es Salaam)=1

D-(Panna Cotta)=0 D+(Panna Cotta)=1

D-(Houmous)=0 D+(Houmous)=1

D-(Piano)=0 D+(Piano)=2

D-(Krav Maga)=0 D+(Krav Maga)=1

D-(Lire)=0 D+(Lire)=2

D-(Sydney)=0 D+(Sydney)=1

D-(Copenhague)=0 D+(Copenhague)=1

D-(Pizza)=0 D+(Pizza)=1

D-(Smoothie)=0 D+(Smoothie)=1

D-(Saint Honoré)=0 D+(Saint Honoré)=1

D-(Aviron)=0 D+(Aviron)=1

D-(Dormir)=0 D+(Dormir)=1

D-(Vienne)=0 D+(Vienne)=1

D-(Pâte)=0 D+(Pâte)=1

D-(Bière)=0 D+(Bière)=1

Question 6 :

Oui c'est un graphe biparti car on retrouve dans le graphe des groupes de nœuds qui ne se lient pas entre eux : les éléments et les personnes. Le graphe est composé de trois étoiles autour des nœuds (Quentin, Marine, Antoine) et il n'y a aucun lien entre ces nœuds. De même il n'y a aucun lien entre les nœuds du groupe des éléments.

Question 7 :

On ne peut pas calculer un diamètre car le réseau est ordonné et donc il n'y a aucun chemin aller/retour entre n'importe quelle pair de nœud. On ne peut jamais aller vers un nœud et passer à un autre ou revenir au nœud précédent. Donc pas de diamètre calculable.

Question 8 et 9 :

Question 10 :


	N Tokyo	N Piano	N Lire	K(Quentin)=7	K(Marine)=6	K(Antoine)=5
N Tokyo	0	0	0	7	6	5
N Piano	0	0	2	0	6	5
N Lire	0	2	0	0	6	5
Un membre quelconque de K(Quentin)	1	0	0	6	0	0
Un membre quelconque de K(Marine)	1	1	1	0	5	0
Un membre quelconque de K(Antoine)	1	1	1	0	0	4

11 :

On peut calculer le degré grâce à la matrice en additionnant la somme de connexion par ligne :

D(Tokyo)=18

D(Piano)=et 13

D(Lire)=13

D(membre quelconque de K(Quentin)=7

D(membre quelconque de K(Marine)=8

D(membre quelconque de K(Antoine)=7

Question 12 :

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

Question 13 :

Le diamètre est la plus longue distance entre les composantes du réseau soit entre le nœud K(Quentin) et le nœud Piano ou Lire. Pour aller à ces nœuds, il faut passer par Tokyo (+1) puis par K(Marine) ou K(Antoine) (+1) puis par Lire ou Piano (+1) et on arrive au nœud (+1).

Δ(Réseau) = 4

Question 14 :

Vu que l'on est dans un réseau non orienté, tous les nœuds sont reliés entre eux aussi et donc le graphe est fortement connexe. En fait, il y a donc une seule composante connexe car on peut circuler partout entre les nœuds.

Réseau projeté II

Question 9 et 10 :

Question 11 :


Nœud/Nœud	Quentin	Marine	Antoine
Quentin	0	1	1
Marine	1	0	3
Antoine	1	3	0

Question 12

On peut trouver le degré de chaque nœud en additionnant les connexions par ligne dans la matrice:

D(Quentin)=2

D(Marine)=4

D(Antoine)=4

Question 13 :

Ce n'est pas un réseau biparti car tous les nœuds sont liés entre eux et il est impossible de dégager différents groupes de nœuds. Il y a un lien entre tous les membres.

Question 14 :

Le diamètre est la plus longue distance d'un nœud à l'autre soit ici

$\Delta$ = 1

Question 15 :

Ce réseau est fortement connexe sur une seule composante car il y a un chemin entre tous les nœuds.