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 noeuds, la liste d'adjacence est vide car les autres noeuds n'ont pas de voisins de sortie.

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

  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 noeud, 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 noeuds non liés entre eux. En effet, les noeuds "individus" ne sont pas liés entre eux, de même que les noeuds "é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 noeuds. 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 noeuds - 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 noeud 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é
Noeud	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 noeuds 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 noeuds dans deux groupes sans aboutir à un lien entre des noeuds 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 noeuds. La plus grande distance entre deux noeuds est toujours un - la distance étant définie par la longueur d'un plus court chemin entre les deux noeuds. Dès lors, le chemin le plus court entre deux noeuds 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 noeuds - la distance entre deux noeuds étant définie par la longueur d'un plus court chemin entre ces deux noeuds. Comme ce graphe est non-orienté et connexe, il y a alors une distance pour toutes les paires de noeuds. 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 noeuds 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 noeud, 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é
Noeud	Degré
Elsa	3
Antoine	4
Marine	5

19. Ce réseau n'est pas biparti car nous avons des groupes de noeuds 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 noeuds ([Marine], [Antoine] et [Elsa]) dans deux groupes sans aboutir à un lien entre des noeuds d'un même groupe.

20. Le diamètre du réseau est la plus grande distance qu'on peut trouver entre deux noeuds. Comme ce graphe est non-orienté et connexe, il y a alors une distance pour toutes les paires de noeuds. Néanmoins nous remarquons que la plus grande distance entre deux noeuds est toujours un - la distance étant définie par la longueur d'un plus court chemin entre les deux noeuds. Dès lors, le chemin le plus court entre deux noeuds est 1 car tous les noeuds 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 noeuds distincts. La réponse est donc 1.