Utilisateur:Nathan slmn/Modélisation des Réseaux (M1 SIREN, 2022)/Activité B
Réseau
[modifier | modifier le wikicode]Cas concrets de mon réseau :
canard, bœuf, minimale, rock, piano, rugby, tennis, cyclisme
Deux collègues dont les réseaux de l'activité A ont des nœuds en commun avec le mien :
Léa -> Pepitos, Mandarines, Gin Tonic, Rock, Contemporaine, Piano, Djembé, Roller, Tennis, Course à pied
Hannah -> Œuf, Fromage, St Germain, Rock, Piano, Athlétisme, Tennis, Course à pied
┌───────────────────┐
│ Athlétisme │
└───────────────────┘
∧
┌────────────────────────────────-──────-─┐ │
│ │ │
│ ┌─────────┐┌───────┐ │ ┌──────────────────────────────────┐ ┌───────────────────┐
│ │cyclisme ││ rugby │ │ │ │ ──> │ St germain. │
│ └─────────┘└───────┘ │ │ │ └───────────────────┘
│ ∧ ∧ │ │ │
│ │ │ └───────────────────── │ │
│ │ │ │ Hannah │
│ ┌──────────┐ ┌──────────────────┐ ┌─────────────┐ │ │ ┌───────────────────┐
│ │ bœuf │ <── │ │ ──> │ minimale │ │ │ ──> │ Fromage │
│ └──────────┘ │ Nathan │ └─────────────┘ │ │ └───────────────────┘
│ ┌──────────┐ │ │ ┌─────────────┐ │ │ ┌───────────────────┐
│ │ canard │ <── │ │ ──> │ tennis │<────│ │ ──> │ oeuf │
│ └──────────┘ └──────────────────┘ └─────────────┘ └──────────────────────────────────┘ └───────────────────┘
│ │ │ _____________∧_______________│ │
│ │ │ │ │ │
│ ∨ ∨ ∨ │ ∨
│ ┌─────────┐┌───────┐ ┌────────────────────────────┐ ┌───────────────────┐
└─────────────────> │ rock ││ Piano │ <── │ │ ──> │ Course à pied │
└─────────┘└───────┘ │ │ └───────────────────┘
∧ │ │
└───────────────────── │ │
│ Léa │
┌───────┐ │ │ ┌───────────────────┐
│Roller │ <── │ │ ──> │ Mandarines │
└───────┘ │ │ └───────────────────┘
┌───────┐ │ │ ┌───────────────────┐
│Djembé │ <── │ │ ──> │ Pépitos │
└───────┘ └────────────────────────────┘ └───────────────────┘
│ │
│ │
∨ ∨
┌─────────────┐ ┌────────────────┐
│ Gin Tonic │ │ Contemporaine │
└─────────────┘ └────────────────┘
Question 1
[modifier | modifier le wikicode]- Il y a une seule composante connexe, c'est tout le graphe, car par construction toutes les personnes sont liées à [ Nathan ], et tous les autres nœuds sont liés à au moins une personne.
- Chaque nœud du graphe est une composante fortement connexe, car dans ce graphe il n'y a pas deux nœuds entre lesquels on puisse aller et revenir en prenant compte l'orientation des liens ; on ne peut que partir d'une personne et arriver à un nœud objet (non-personne), d'où on ne peut pas sortir.
Question 2
[modifier | modifier le wikicode]En ignorant l'orientation des liens :
- On ne trouve pas de triangles, car si on part d'un nœud personne [ A ] on ne peut qu'arriver à un nœud non-personne [ B ], et vice-versa. Donc le graphe est dans ce sens biparti : les personnes ne se connectent pas entre elles, et les nœuds objet ne se connectent pas entre eux. Un triangle exigerait donc une séquence du type
[ personne A ] – [ objet X ] – [ personne B ] – [ personne A ], ou l'équivalant en partant d'un objet, ce qui n'est pas possible. - Il n'y a pas de triangles (3 pas), mais on peut trouver un cycle à 4 pas :
[ Léa ] – [ tennis ] – [ Nathan ] – [ Piano ] – [ Léa ].
En prenant en compte l'orientation des liens :
- L'orientation des liens restreignant les possibilités, s'il n'y a pas de triangle non-orienté, il ne peut pas non plus y avoir de triangle orienté.
- Il n'y a pas de cycle dans ce graphe orienté. Comme on avait vu, chaque nœud est sa propre composante fortement connexe, et un cycle impliquerait un groupe de nœuds entre lesquels on peut passer librement.
Question 3
[modifier | modifier le wikicode]Les degrés du graphe :
| Nœud(s) | Degré non-orienté | Degré sortant | Degré entrant |
|---|---|---|---|
| Léa | 10 | 10 | 0 |
| Nathan | 8 | 8 | 0 |
| Hannah | 8 | 8 | 0 |
| Tennis | 3 | 0 | 3 |
| Rock | 3 | 0 | 3 |
| Piano | 3 | 0 | 3 |
| Course à pied | 2 | 0 | 2 |
| [ 15 autres nœuds ] | 1 | 0 | 1 |
La distribution de degrés :
| Degré | # Non-orienté | # Sortant | # Entrant |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 15 | 0 | 15 |
| 2 | 1 | 0 | 1 |
| 3 | 3 | 0 | 3 |
| 8 | 2 | 2 | 0 |
| 10 | 1 | 1 | 0 |
Question 4
[modifier | modifier le wikicode]Mon réseau simplifié :
┌─────────────────────────────────────────────┐ │ ∨ ┌───────┐ ┌─────────┐ ┌─────────┐ ┌──────┐ │Hannah │ ──> │ Tennis │ <── │ Nathan │ ──> │ Rock │ └───────┘ └─────────┘ └─────────┘ └──────┘ │ │ ∧ │ ∧ │ │ ──────────── │──┐. ∨ │ │ │ └── > ┌─────────┐ │ │ │ ┌ > │ piano │ │ ∨ │ │ └─────────┘ │ ┌──────────────┐ ┌─────────┐ │ │Course à pied │ <── │ Léa │───────────────── └──────────────┘ └─────────┘
1. La matrice d'adjacence :
| Nathan | Hannah | Léa | Tennis | Rock | Piano | Course à pied | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Nathan | 0 | 0 | 0 | 1 | 1 | 1 | 0 | ||||||||
| Hannah | 0 | 0 | 0 | 1 | 1 | 1 | 1 | ||||||||
| Léa | 0 | 0 | 0 | 1 | 1 | 1 | 1 | ||||||||
| Tennis | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||
| Rock | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||
| Piano | 0 | 0 | 0 | 0 | 0 | 0 | 0 | Course à pied | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2.1. Projections non-orientés :
- Sur les personnes :
[ Nathan ] - Tennis - [ Hannah ]
[ Nathan ] - Tennis - [ Léa ]
[ Nathan ] - piano - [ Hannah ]
[ Nathan ] - piano - [ Léa ]
[ Nathan ] - rock - [ Léa ]
[ Nathan ] - rock - [ Hannah ]
[ Léa ] - course à pied - [ Hannah ]
[ Léa ] - piano - [ Hannah ]
[ Léa ] - tennis - [ Hannah ]
[ Léa ] - rock - [ Hannah ]2.2 Diamètre non-orienté :
- Il n'y a qu'une seule composante connexe et la plus grande distance est 3.
3. Réseau fortement connexe :
Dans un réseau fortement connexe on peut partir et arriver entre n'importe quels deux nœuds. Cela implique que chaque nœud doit avoir au moins un lien entrant et un lien sortant.
Dans mon réseau, les personnes n'ont pas de lien entrant, il faudrait donc ajouter au moins 3 liens pour qu'on puise arriver à chacune des 3 personnes. A son tour, les objets aussi n'ont pas de lien sortant, même problématique. Voyons donc si on peut ajouter 3 liens partant des objets vers les personnes, d'une telle sorte qu'on puisse circuler dans le graphe.