N.S.I. WorkSpace Notion,Terminale Graphe : Structure relationnelle de données

Graphe : Structure relationnelle de données

Categories:

Question 1b – Le résultat de la requête est :

Capture d’écran : HeidiSQL dans Laragon

Question 2 – La requête est la suivante :

Capture d’écran : HeidiSQL dans Laragon

Question 3a – L’attribut salle ne peut pas être une clé primaire pour la relation Ordinateur, car il existe au moins trois enregistrements dans la table Ordinateur pour lesquels la valeur de l’attribut salle est la même. Or une clé primaire est définie par un attribut pour lequel la valeur de chacun des enregistrements de la table est unique.

Question 3b – Le schéma relationnel de la table Imprimante est le suivant :

Imprimante (nom_imprimante : String, marque_imp : String, modele_imp : String, salle : String, nom_ordi : String)
Clé primaire (PK) | Clé étrangère (FK)

Question 4a – La requête SQL est la suivante :

INSERT INTO Videoprojecteur VALUES ("315", "NEC", "ME402X", false)

Question 4b – La requête SQL est la suivante :

SELECT Ordinateur.salle, Ordinateur.nom_ordi, Videoprojecteur.marque_video FROM Ordinateur INNER JOIN Videoprojecteur ON Ordinateur.salle = Videoprojecteur.salle WHERE tni = true ;

SELECT Ordinateur.salle, Ordinateur.nom_ordi, Videoprojecteur.marque_video FROM Ordinateur NATURAL JOIN Videoprojecteur WHERE tni = true ;

Algorithmes sur les graphes.

Contenus Capacités attendues Commentaires
Source
Algorithmes sur les graphes.
  • Parcourir un graphe en profondeur d’abord, en largeur d’abord.
  • Repérer la présence d’un cycle dans un graphe.
  • Chercher un chemin dans un graphe.

Nouveau réseau social : « Troncho’scope »

Ce nouveau réseau social ne compte aujourd’hui que neuf inscrits : Aude, Brice, Carla, Damien, Eric, Fiona, Gina, Hugo et Inès.

L’examen de leurs profils montre que :

  • Aude est amie avec Damien, Eric et Brice ;
  • Brice est ami avec Aude, Carla et Fiona ;
  • Carla est amie avec Brice ;
  • Damien est ami avec Aude et Eric ;
  • Eric est ami avec Aude, Damien, Gina et Hugo ;
  • Fiona est amie avec Inès, Hugo et Brice ;
  • Gina est amie avec Eric ;
  • Hugo est ami avec Eric et Fiona ;
  • Inès est amie avec Fiona.

Décrit de cette manière et à ce stade, il apparaît difficile de se faire une représentation claire des liens qui existent entre toutes les personnes inscrites. Alors qu’en sera-t-il dans un an sachant que tous les jours ce nouveau réseau social enregistre de nouveaux inscrits !

Afin de mieux se rendre compte des liens d’amitiés entre les membres de se réseau, on se propose d’en construire une représentation graphique, plus « visuelle », en appliquant le principe suivant :

  • chaque personne sera figurée par un cercle à l’intérieur duquel sera écrit son prénom ;
  • le lien « est ami.e avec… » sera figurée par un « trait » reliant les cercles des personnes concernées.

Construire une représentation graphique du réseau social « Troncho’scope »

Exemple de représentation possible
Les traits en vert signifient « est ami.e avec …

Ce type de représentation est appelé un « Graphe ».

Il existe d’autres situations qui peuvent être représentées par un graphe :

  • réseau de transports en commun d’une ville ;
  • réseau routier entre les villes ;
  • réseau informatique

Ce qu’il faut retenir (CQFR)…

Qu’il s’agisse d’un réseau social, d’un réseau routier ou encore d’un réseau informatique, il est possible de représenter ces situations sous la forme de graphes.

Un graphe est une structure relationnelle de données.

Un graphe est constitué de sommets et d’arêtes (ou arcs).

Une arête relie deux sommets adjacents.

Le degré d’un sommet est le nombre d’arêtes liés à ce sommet.

L’ordre d’un graphe est le nombre de sommets.

Une chaîne ou un chemin est une suite ordonnée de sommets consécutivement adjacents.

La distance entre deux sommets d’un graphe est le plus petit nombre d’arêtes d’une chaîne allant de l’un à l’autre.

L’excentricité d’un sommet est la distance maximale existant entre ce sommet et les autres sommets du graphe.

Le centre d’un graphe est un sommet d’excentricité minimale. Un graphe peut posséder plusieurs centres.

Le rayon d’un graphe correspond à l’excentricité d’un centre du graphe.

Le diamètre d’un graphe correspond à la plus grande distance entre deux sommets du graphe.

S’il existe un sens de parcours des arêtes, alors le graphe est dit orienté.

Le graphe est complet si chacun de ses sommets est relié à tous les autres.

Description d’un graphe

Un graphe peut être décrit par une matrice d’adjacence.

  • Cette matrice comporte autant de lignes et de colonnes que le graphe comporte de sommets.
  • La valeur notée à l’intersection d’une ligne et d’une colonne sera égale à zéro si les deux sommets ne sont pas adjacents.
  • Elle sera égale à 1 si les deux sommets sont adjacents.
Graphe n° 1 non orienté
ABCD
A0111
B1010
C1100
D1000
Matrice d’adjacences du graphe n°1 ci-dessus
Graphe n° 2 orienté
ABCD
A0101
B0010
C1000
D1000
Matrice d’adjacences du graphe n°2 ci-dessus

Un graphe peut être aussi décrit par des listes de successeurs, et des listes de prédécesseurs s’il est orienté.

Ainsi pour le graphe n°1 non orienté présenté plus haut, on aura les listes de successeurs suivantes :

  • A : B, C, D
  • B : A, C
  • C : B, A
  • D : A

Et pour le graphe n°2 orienté présenté plus haut, on aura :

  • Listes de successeurs
    • A : B, D
    • B : C
    • C : A
    • D : A
  • Listes de prédécesseurs
    • A : C, D
    • B : A
    • C : B
    • D : A

« Troncho’scope » : la suite…

Question 1 – Quel est l’ordre de ce graphe ?

Question 2 – Quel est le degré du sommet ‘Eric’ ?

Question 3 – Donner une chaîne dans laquelle figurent Aude et Inès.

Question 4 – Donner un cycle dans lequel figurent Eric et Fiona.

Question 5 – Écrire la matrice d’adjacence du graphe.

Question 6 – Écrire les listes de successeurs du graphe.

Question 7 – Cinq nouveaux membres ont rejoint le réseau social : Jean, Kurt, Léa, Marion et Noémie. Par ailleurs des relations précédentes se sont dénouées et de nouvelles se sont nouées entre les premiers membres. La matrice d’adjacence du graphe représentant le réseau social est la suivante :

ABCDEFGHIJKLMN
A01010000000100
B10100100000100
C01000000000010
D10001011010000
E00010001100000
F01000000100010
G00010001001001
H00011010100000
I00001101000011
J00010000000100
K00010010000001
L11000000010000
M00100100000001
N00000010101010
Nouvelle matrice d’adjacence du graphe représentant le réseau social ‘Tronch’scope’
Seule la première lettre du prénom a été indiquée en tête de lignes et de colonnes

A partir de cette matrice, actualiser la précédente représentation graphique du réseau social.