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

Réseau original

1. Je choisis comme participant Elsa0305 et Antoine Thomann

2/3.

4. Listes d'adjacence:

Marine : [Krav-Maga, Saint-Honoré, Smoothie, Pizza, Sydney, Copenhague, Lire, Tokyo, Piano]

Elsa: [Piano, Coktails, Wellington, Honolulu, Papeete, Sport, Gâteaux, Ukulélé, Pizza]

Antoine: [Tokyo, Dormir, Aviron, Pâtes, Bière, Madrid, Vienne, Lire, Piano]

Pour les autres nœuds, la liste d'adjacence est vide car les autres nœuds n'ont pas de voisins de sortie.

5. Pour obtenir le degré de sortie de chaque nœud, il suffit de sommer le nombre d'éléments présents dans la liste d'adjacence de chaque nœud.

  Ainsi nous trouvons : d+(Marine) = 9, d+(Elsa) = 9, d+(Antoine)= 9
                        pour tous les autres noeuds, d+ (x) = 0

Concernant le degré d'entrée de chaque nœud, ce dernier est égal au nombre de fois qu'il apparaît dans toutes les listes d'adjacence. Le graphe étant orienté, de l'individu vers l'élément, nous trouvons les résultats suivants:

                       d-(Marine) = 0, d-(Elsa) = 0, d-(Antoine) = 0
                        pour tous les autres noeuds, d-(x) = 1 sauf d-(piano) = 3, d-(pizza) = 2, d-(lire)=2, d-(Tokyo)=2

6. C'est un réseau biparti car nous avons des groupes de nœuds non liés entre eux. En effet, les nœuds "individus" ne sont pas liés entre eux, de même que les nœuds "éléments".

7. Nous ne pouvons pas calculer le diamètre de ce graphe dans la mesure où il n'y a pas de chemins entre tous les nœuds. Il n'y a pas de chemin à réaliser, au-delà de l'unique lien entre un individu et un élément. On peut en conclure que la plus grande distance entre deux nœuds - un individu et son élément - est toujours un. La plus grande distance qu'on peut parcourir dans le réseau est de longueur 1. Par exemple pour aller de l'individu [Elsa] à l'élément [Piano]. Nous pouvons aussi en déduire que ce réseau n'est pas fortement connexe. Nous ne pouvons pas par exemple aller de l'individu [Elsa] à l'individu [Antoine], ou de l'élément [Smoothie] à l'élément [Madrid].

Réseau projeté

8/9. J'ai réalisé deux graphes, une version simplifiée réalisée seulement avec les éléments communs entre les individus et une version complète réalisée avec tous les éléments. La suite de l'exercice sera réalisée avec les deux versions.

Pour la version simplifiée, la présence de 2 prénoms sur un même lien revient à représenter graphiquement 2 liens. Il s'agit ici juste d'une simplificaiton graphique.

Pour la version complète, je définis 3 K-graphes d'éléments (K-Elsa, K-Antoine et K-Marine). Chacun de ces 3 K-graphes d'éléments ne sont pas connectés entre eux car les éléments dans ces graphes ne concernent qu'un seul individu. Néanmoins ces K-graphes d'éléments peuvent être connectés à d'autres éléments, partagés par plusieurs individus comme l'élément "piano" par exemple.

10.

Avec la version simplifiée:

Matrice d'adjacence
	Lire	Tokyo	Pizza	Piano
Lire	0	2	1	2
Tokyo	2	0	1	2
Pizza	1	1	0	2
Piano	2	2	2	0

Avec la vesion complète:

Matrice d'adjacence
	Lire	Tokyo	Pizza	Piano	K-Elsa (N=7)	K-Antoine (N=6)	K-Marine (N=5)
Lire	0	2	1	2	0	6	5
Tokyo	2	0	1	2	0	6	5
Pizza	1	1	0	2	7	0	5
Piano	2	2	2	0	7	6	5
Un membre quelconque de K-Elsa	0	0	1	1	6	0	0
Un membre quelconque de K-Antoine	1	1	0	1	0	5	0
Un membre quelconque de K-Marine	1	1	1	1	0	0	4

11. Comme ce graphe est non orienté, il n’y a pas de différenciation à réaliser entre degré de sortie et degré d'entrée (sauf pour les membres des K-graphes). Dès lors, le degré de chaque nœud s'obtient en sommant les lignes ou les colonnes de la matrice d'adjacence.

Nous obtenons alors le résultat suivant, si nous ne considérons que la version simplifiée du graphe:

   Ainsi, d(lire) = 5
          d(Tokyo) = 5
          d(pizza) = 4
          d(piano) = 6

Si nous considérons la version complète du graphe nous obtenons les résultats suivants :

Degré
Nœud	Degré
Lire	16
Tokyo	16
Pizza	16
Piano	24
Un membre quelconque de K-Elsa	8
Un membre quelconque de K-Antoine	8
Un membre quelconque de K-Marine	8

Précisons que comme la matrice d'adjadence était compacte (en regroupant plusieurs éléments sous le nom de K-Elsa par exemple), il faut sommer les lignes et non pas les colonnes pour les membres d'un K-graphe pour obtenir le bon degré, même si le graphe est non-orienté.

12. Ce n’est pas un réseau biparti car nous avons des groupes de nœuds liés entre eux. En effet, le graphe contient des "triangles" et donc des sous-graphes complets Par exemple, [Tokyo], [Lire] et [Piano] sont reliés entre eux. Dès lors, il n'est pas possible de répartir ces trois nœuds dans deux groupes sans aboutir à un lien entre des nœuds d'un même groupe. L'existence de ce contre-exemple suffit à prouver que le graphe n'est pas un réseau biparti.

13.

Si nous prenons la version simplifiée du graphe :

Nous pouvons calculer un diamètre dans le mesure où il existe un chemin entre toutes les paires de nœuds. La plus grande distance entre deux nœuds est toujours un - la distance étant définie par la longueur d'un plus court chemin entre les deux nœuds. Dès lors, le chemin le plus court entre deux nœuds est 1

Si nous prenons la version complète du graphe :

Le diamètre du réseau est la plus grande distance qu'on peut trouver entre deux nœuds - la distance entre deux nœuds étant définie par la longueur d'un plus court chemin entre ces deux nœuds. Comme ce graphe est non-orienté et connexe, il y a alors une distance pour toutes les paires de nœuds. Nous pouvons ainsi trouver un diamètre. Visuellement, nous voyons que le chemin le plus court est par exemple atteint entre [Coktails] et [Madrid]. Nous effectuons 2 sauts: de [Coktails] à [Piano] puis de [Piano] à [Madrid]. Le diamètre du réseau est alors 2.

14. Dans ce graphe, il existe une chaîne entre n'importe quelle paire de nœuds distincts. Ainsi, ce graphe est connexe. Il n'y a alors pas plusieurs sous-graphes connexes disjoints dans la mesure où le graphe est connexe dans sa totalité. Le graphe a alors une seule composante connexe. La réponse est alors 1.

Réseau projeté II

15 et 16.

17.

Matrice d'adjacence
	Elsa	Antoine	Marine
Elsa	0	1	2
Antoine	1	0	3
Marine	2	3	0

18. Pour obtenir le degré de chaque nœud, il suffit de faire la somme de la ligne ou de la colonne dans la matrice d'adjacence. En effet, comme nous sommes dans le cas d'un graphe non-orienté, la matrice est symétrique. Nous pouvons donc soit additionner les lignes soit additionner les colonnes car il n'y a pas de différenciation à réaliser entre degré de sortie et degré d'entrée.

Degré
Nœud	Degré
Elsa	3
Antoine	4
Marine	5

19. Ce réseau n'est pas biparti car nous avons des groupes de nœuds liés entre eux. Le graphe prend en effet la forme d'un triangle et est donc complet. Par exemple, [Marine], [Antoine], [Elsa] sont reliés ensemble via les liens Tokyo, Piano et Pizza. Dès lors, on ne peut pas répartir ces trois nœuds ([Marine], [Antoine] et [Elsa]) dans deux groupes sans aboutir à un lien entre des nœuds d'un même groupe.

20. Le diamètre du réseau est la plus grande distance qu'on peut trouver entre deux nœuds. Comme ce graphe est non-orienté et connexe, il y a alors une distance pour toutes les paires de nœuds. Néanmoins nous remarquons que la plus grande distance entre deux nœuds est toujours un - la distance étant définie par la longueur d'un plus court chemin entre les deux nœuds. Dès lors, le chemin le plus court entre deux nœuds est 1 car tous les nœuds sont reliés entre eux.

21. Ce graphe est connexe. Une fois de plus, il n'y a alors pas plusieurs sous-graphes connexes disjoints dans la mesure où le graphe est connexe dans sa totalité. Il y a donc une seule composante connexe. AInsi, il existe une chaîne entre n'importe quelle paire de nœuds distincts. La réponse est donc 1.