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

Réseau original

3. Dessinez dans une feuille papier le graphe que vous avez trouvé

4. Décrivez le réseau en tant que liste d'adjacence.

  Elsa: [Piano, Ukulélé, Cuisine, Sport, Papeete, Honolulu, Wellington, Cocktails, Pizza]
  Lana: [Piano, Chinois, Cuisine, Musique, Lisbonne, Moscou, Raclette, Pizza]
  Thomas: [Piano, Football, Cuisine, Saïgon, Lisbonne, Tokyo, Riz, Poulet grillé, Pizza]
  Tous les autres nœuds : []

5. Calculez le degré (d'entrée et sortie) de chaque nœud, en expliquant comment on peut l'obtenir à partir de la liste d'adjacence.

  d-(Elsa) = 0             d+(Elsa)= 9 
  d-(Lana) = 0             d+(Lana)= 8
  d-(Thomas) = 0           d+(Thomas) = 9 
  d-(Piano) = 3            d+(Piano) = 0
  d-(Ukulélé) = 1          d+(Ukulélé)= 0
  d-(Cuisine) = 3          d+(Cuisine) = 0
  d-(Sport) = 1            d+(Sport) = 0
  d-(Papeete) = 1          d+(Papeete) = 0
  d-(Honolulu) = 1         d+(Honolulu) = 0
  d-(Wellington) = 1       d+(Wellington) = 0
  d-(Cocktails) = 1        d+(Cocktails) = 0
  d-(Chinois) = 1          d+(Chinois) = 0
  d-(Musique) = 1          d+(Musique) = 0
  d-(Lisbonne) = 2         d+(Lisbonne) = 0
  d-(Moscou) = 1           d+(Moscou) = 0
  d-(Raclette) = 1         d+(Raclette) = 0
  d-(Football) = 1         d+(Football) = 0
  d-(Saigon) = 1           d+(Saigon) = 0
  d-(Tokyo) = 1            d+(Tokyo) = 0
  d-(Riz) = 1              d+(Riz) = 0
  d-(Poulet grillé) = 1    d+(Poulet grillé) = 0

  À partir de la liste d’adjacence, on regarde combien de fois chaque élément est présent dans chacune des listes pour le degré négatif. Pour le degré positif, on regarde combien il y a d'éléments pour chaque liste d’un individu.

6. Est-ce un réseau biparti ? Pourquoi ?

  C'est un réseau biparti car les individus ne sont pas connectés entre eux, seulement avec les éléments. De même, les éléments ne sont pas connectés entre eux, mais seulement avec les individus. L'ensemble des sommets peut donc être décomposé en deux sous-ensembles, ce qui montre bien que c’est un réseau biparti. 

7. Peut-on calculer un diamètre pour ce réseau ? Pourquoi ?

  Ce réseau n'est pas fortement connexe, c’est-à-dire qu'il n’y a pas de chemin entre tous les nœuds. Ainsi, nous ne pouvons pas calculer de diamètre pour ce réseau.  

Réseau projeté

9. Dessinez dans une feuille papier le graphe que vous avez trouvé. Version simplifiée :

Version complète :

10. Décrivez ce réseau en tant que matrice d'adjacence. Pour la version simplifiée (il y a une erreur, pour la ligne Lisbonne et la colonne Cuisine c'est 2 et non 3) :

Pour la version complète :

	Cuisine	Pizza	Piano	Lisbonne	K-Elsa (=6)	K-Lana (=4)	K-Thomas (=5)
Cuisine	0	3	3	2	6	4	5
Pizza	3	0	3	2	6	4	5
Piano	3	3	0	2	6	4	5
Lisbonne	2	2	2	0	0	4	5
Un membre quelconque d’Elsa	1	1	1	0	5	0	0
Un membre quelconque de Lana	1	1	1	1	0	3	0
Un membre quelconque de Thomas	1	1	1	1	0	0	4

11. Calculez le degré de chaque nœud, en expliquant comment on peut l'obtenir à partir de la matrice d'adjacence.

   d(Piano) = 8 
   d(Cuisine) = 9 
   d(Pizza) = 8 
   d(Lisbonne) = 6

   À partir de la matrice, on ajoute chaque colonne de celle-ci pour trouver le degré de chaque nœud correspondant. 

12. Est-ce un réseau biparti ? Pourquoi ?

   Non car tous les nœuds sont reliés entre eux, on ne peut donc pas les décomposer en deux sous-ensembles. Ce n'est donc pas un réseau biparti. 

13. Trouvez le diamètre du réseau

   Le diamètre du réseau est 2 car c'est la distance la plus grande entre deux nœuds. 

14. Combien de composantes connexes dans ce réseau ? Pourquoi ?

   Il y a 1 composante connexe dans ce graphe, car tous les éléments sont reliés entre eux. C'est donc un graphe connexe.

Réseau projeté 2

9. Réseau projeté :

10. Décrivez ce réseau en tant que matrice d’adjacence

	Elsa	Lana	Thomas
Elsa	0	3	3
Lana	3	0	4
Thomas	3	4	0

12. Calculez le degré de chaque nœud

 Elsa : 6
 Lana : 7
 Thomas : 7

 On peut trouver ce résultat en additionnant les colonnes ou les lignes de la matrice d’adjacence. 

13. Est-ce un réseau biparti ?

 Ce n'est pas un réseau biparti, car tous les nœuds sont reliés entre eux, on ne peut donc pas séparer ce réseau en deux groupes. 

14. Trouver le diamètre du réseau

 Le diamètre d’un réseau est la distance entre les deux nœuds les plus éloignés du réseau. Ici, le diamètre est donc de 1.

15. Nombre de composantes connexes

 Ce réseau est composé d’une seule composante connexe. En effet, il y a un chemin entre tous les nœuds.