Utilisateur:Ewen Marguet/Modélisation des Réseaux (M1 SIREN, 2022)/Activité B
Réseau
[modifier | modifier le wikicode]1. Cas concrets de mon réseau:
Ewen -> Tacos, les sushis, Spritz, HipHop, Guitare, Piano, Basket, Haltérophilie, Natation
2. Deux collègues avec des noeuds similaires:
Sarah-> les sushis, la bière belge, HipHop, la Zumba, le Charleston, équitation, tennis, Piano
Alice -> omelettes, cheesecakes; vin blanc, danse contemporaine, valse, clarinette, guitare, Piano, Basket, handball3.
Questions
[modifier | modifier le wikicode]1. En ignorant l'orientation des liens, la photo ci-dessus est un graphe connexe avec une composante connexe. Il existe un chemin entre chaque paire de sommets.
MAIS, si on se place dans le cas d'un graphe orienté, il existe plusieurs composantes fortement connexes:
Natation, Basket, Haltérophilie, HipHop, Guitare, Tacos, Sushi, Piano, Spritz, Bière belge, Zumba, Charleston, Equitation, Tennis, clarinette, Danse contemporaine, valse, vin blanc, cheesecake, omelette et handball sont des composantes fortement connexes.2. 1. Ce réseau ne contient pas de triangle.
2. 2. La taille du plus petit cycle qu'il contient est de 4 :
Sarah -- Piano -- Ewen -- Sushi -- Sarah ( Soit A-B-C-D-A)
2. 3. Si on prenait en compte l'orientation, il n'y aurait pas de cycles puisque ce graph est composé d'une multitude de graph(sommets) fortement connexe sans cycle. Il n'y a donc pas de plus petit cycle. Il n'y a aucun degré entrant pour les personnes donc pas de cycle.3. 1. Distribution du nombre de degrés graphe orienté sous forme de tableau:
| Noeud | Cibles des liens |
|---|---|
| [Ewen] | ([Tacos], [Sushi], [Spritz], [hipHop], [Guitare], [Piano], [Basket], [haltérophilie], [Natation]) |
| [Sarah] | ([sushi], [Bière belge], [HipHop], [Zumba], [Charleston], [Equitation], [Tennis], [Piano]) |
| [Alice] | ([Omelette], [Cheesecake], [Vin blanc], [danse contemporaine], [valse], [clarinette], [guitare], [piano], [Basket], [Handball]) |
Le degré entrant des personnes est zéro, ainsi que le degré sortant de n'importe que élément. On note dans la liste et par le graphe dessiné que la plupart des éléments ont un degré entrant de 1, car apparaît une seule fois dans la liste d'une seule personne, tandis que quatre éléments ont un degré égal a 2, car partagé par deux personnes également une fois dans la liste de chacune. Un élément figure dans les trois listes. D'une telle façon qu'on peut écrire le tableau de degrés :
| Noeud | Entrée | Sortie |
|---|---|---|
| [Ewen] | 0 | 9 |
| [Sarah] | 0 | 8 |
| [Alice] | 0 | 10 |
| [Guitare] | 2 | 0 |
| [Hiphop] | 2 | 0 |
| [Basketball] | 2 | 0 |
| [Sushi] | 2 | 0 |
| [Piano] | 3 | 0 |
3. 2. Distribution du nombre de degrés graphe non orienté sous forme de tableau:
Dans le cas d'un graphe non orienté, il suffit de reprendre le tableau ci-dessus, et d'additionner entrant et sortant puisqu'il n'y a pas de flèche allant dans les deux sens (uniquement de la personne vers ses éléments). Pour tous les éléments absents, ils ont un degré de 1.
| Noeud | Degrés |
|---|---|
| [Ewen] | 9 |
| [Sarah] | 8 |
| [Alice] | 10 |
| [Guitare] | 2 |
| [Hiphop] | 2 |
| [Basketball] | 2 |
| [Sushi] | 2 |
| [Piano] | 3 |
4. 1.Les nœuds à degré total — entrant plus sortant — supérieur à 1 sont présents dans le tableau ci-dessus.
| Noeuds/Noeuds | [Ewen] | [Sarah] | [Alice] | [Guitare] | [HipHop] | [Basketball] | [Sushi] | [Piano] |
|---|---|---|---|---|---|---|---|---|
| [Ewen] | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| [Sarah] | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| [Alice] | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| [Guitare] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| [Hiphop] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| [Basketball] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| [Sushi] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| [Piano] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4. 2. Voici l'image du graphe simplifié non-orienté
4. 2. 1. L'image est ajouté sur le côté pour les nœuds en tant que personne. Je ne peux pas faire de graphe projeté sur les nœuds qui ne sont pas des personnes, puisque les éléments ne sont pas reliés entre eux.
4. 2. 2. Le graphe est connexe. C'est à dire, qu'il a une seule composante connexe. Cela signifie qu'il y a un chemin dans le graphe entre n'importe quel pair de nœuds (c'est logique puisqu'on se situe dans un graphe non orienté avec des degrés supérieur à 1 par rapport à la question 3). De plus, le diamètre est la plus grande distance entre deux nœuds. D'après notre image, le diamètre est de 1 puisque tous les noeuds sont liés entre eux
4. 3. Pour avoir un réseau fortement connexe, il faut relier les composantes fortement connexes. Il faut ajouter des degrés sortants à HipHop, Sushi, Piano, Guitare et Basket. Ainsi, le minimum de liens qu'il faut ajouter dans mon cas est de 5. Voici en photo une suggestion d'ajout qui rendrait le graphe fortement connexe.
