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


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

Question 3 :

Graphe du réseau

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 :

A partir de la liste d'adjacence, on peut calculer le degré de sortie des noeuds en additionnant le nombre de noeud avec lesquels ils ont un lien. Ainsi on peut également obtenir le degré d'entrée de tous les autres noeuds car comme on est dans un graphe ordonné, il suffit de compter le nombre de fois qu'un noeud 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 noeuds qui ne se lient pas entre eux : les éléments et les personnes. Le graphe est composé de trois étoiles autour des noeuds (Quentin, Marine, Antoine) et il n'y a aucun lien entre ces noeuds. De même il n'y a aucun lien entre les noeuds 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 noeud. On ne peut jamais aller vers un noeud et passer à un autre ou revenir au noeud précédent. Donc pas de diamètre calculable.

Question 8 et 9 :

Graphe du réseau projeté

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 noeuds sont liés entre eux.

Question 13 :

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

Δ(Réseau) = 4

Question 14 :

Vu que l'on est dans un réseau non orienté, tous les noeuds 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 noeuds.


Réseau projeté II

Question 9 et 10 :

Graphe du réseau projeté II

Question 11 :

Noeud/Noeud Quentin Marine Antoine
Quentin 0 1 1
Marine 1 0 3
Antoine 1 3 0


Question 12

On peut trouver le degré de chaque noeud 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 noeuds sont liés entre eux et il est impossible de dégager différents groupes de noeuds. Il y a un lien entre tous les membres.


Question 14 :

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

= 1


Question 15 :

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