Les graphes

1 / 10

Laquelle de ces définitions d'un graphe est juste ?

Un ensemble de points reliés entre eux ou non.
La représentation d'une fonction mathématique.
Un ensemble de points tous reliés entre eux.

Mauvaise réponse !

Un graphe est un ensemble de points qui peuvent être reliés entre eux mais il n'est pas obligatoire qu'ils le soient tous. En effet, un point seul et non connecté peut exister dans un graphe. La fonction mathématique représentée sur des axes (x,y) est un type de graphe.

Qu'est-ce qu'un nœud dans un graphe ?

un point sur un graphe
un trait reliant deux points
un points relié à au moins deux autres points par un trait

Mauvaise réponse !

Le nœud est l'un des points constituant le graphe. Il peut être relié à un, plusieurs ou même à aucun autre point. Le trait reliant les nœuds est appelé une arête ou un arc.

Laquelle de ces variantes de définition n'existe pas ?

Deux nœuds peuvent être reliés plusieurs fois par plusieurs arêtes.
Une arête peut relier plus de deux nœuds.
Une arête peut être orientée d'un nœud vers un autre.

Mauvaise réponse !

On ne peut pas relier trois nœuds ou plus avec une même arête, une arête reliant au plus deux nœuds. D'autres variantes existent permettant de relier un nœud à lui-même, de pondérer les arêtes.. On parlera ici de graphe non simple.

Qu'est-ce qu'un graphe connexe ?

Un graphe où chaque nœud n'est pas directement relié à chaque autre nœud.
Un graphe où toutes les arêtes se croisent.
Un graphe où chaque nœud est relié directement ou indirectement à chaque autre nœud.

Mauvaise réponse !

Un graphe ne dépend pas de son dessin mais uniquement des points les reliant ensemble. La connexité se définit bien par l'existence d'un chemin entre chaque nœud relié au minimum indirectement.

Quelles valeurs peut contenir une matrice d'adjacence ?

0, 1 et -1
n'importe quel nombre
0 et 1

Mauvaise réponse !

Une matrice d'adjacence ne peut être composée que de 0 et de 1. Si la case "ij" vaut 0, les nœuds "i "et "j" ne sont pas reliés, alors que si la case vaut 1, ils sont reliés. Pour des arêtes orientées, on ne va pas utiliser -1, mais, si l'arête va de "i" à "j", on peut mettre M(ij) = 1 et M(ji) = 0.

Combien de listes faut-il pour définir un graphe via des listes simples (hors dictionnaire d'adjacence) ?

Mauvaise réponse !

Il faut deux listes pour définir un graphe avec des listes simples. Une liste donnant les noms des sommets et une liste contenant des listes de sommets liés (Ex : S = [1,2,3], A = [[1,2],[1,3]] est un graphe avec trois nœud où le nœud 1 est relié au 2 et au 3).

Lequel de ces dictionnaires d'adjacence est bien défini pour un graphe simple ?

ADJ = {0:[1,2],1:[0,3,4],2:[0,4,5],3:[1],4:[1,2]}
ADJ = {0:[1,2],1:[0,3,4],2:[0,4],3:[1],4:[1,2],5[]}
ADJ = {0:[1,2],1:[0,3,],2:[0,4],3:[1],4:[1,2]}

Mauvaise réponse !

En effet, dans les cas des graphe mal représentés, on a un cas où un nœud est décrit comme relié à un nœud non existant. Dans l'autre, un nœud est relié à un autre sans que cela ne soit réciproque, ce qui est impossible.

Pourquoi les listes S = [0,1,2,3] A = [[0,1],[1,3],[1,0],[2],[1,2,3]] ne définissent pas un graphe ?

Les arêtes [0,1] et [1,0] ne peuvent être écrites toutes les deux car elles sont redondantes.
L'arête [2] n'a pas lieu d'être car elle ne relie pas deux nœuds.
L'arête [1,2,3] n'existe pas car une arête ne peut relier plus de 2 nœuds.

Mauvaise réponse !

Effectivement, il est possible que deux nœuds soient reliés plusieurs fois par différentes arêtes, ou qu'un nœud soit relié à lui-même par une arête. Mais une arête ne peut pas relier 3 nœuds ensemble.

Lequel de ces systèmes ne peut pas être modélisé par un graphe simple ?

Les connexions entre des villes et des routes.
Le nombre de connexions par jour à un terminal par un groupe de personnes.
Des personnes et leurs relations sur un réseau social

Mauvaise réponse !

La modélisation de villes ou de réseaux sociaux sont de bon exemples de l'utilisation des graphes. Mais on ne peut pas utiliser les graphes simples pour représenter le nombre de connexions à un terminal. Il faut utiliser des variantes pour modéliser les connexions à un terminal.

Quelle application n'est pas possible par la modélisation en graphe pondéré de villes (nœuds) reliés par des routes (arêtes) ?

connaître la distance à parcourir
connaître le nombre de ville à traverser pour en rejoindre une autre
connaître le temps de trajet

Mauvaise réponse !

Le temps de trajet est imprévisible car soumis aux aléas (vitesse, embouteillage...). Mais en pondérant les arrêtes par la distance de la route qu'elle représente, on peut calculer une distance. Grâce au chemin entre deux nœuds, on peut compter les nœuds représentant les villes traversées.

Bravo ! Ton score est deTon score est deBien joué, ton score est de 0/10

Retente ta chance, tu peux faire mieux.

Retente ta chance pour améliorer ton score !

Voir les quiz associés

Quiz Voie générale10 questions

Les graphes

Les graphes constituent un outil important en sciences. Ils représentent physiquement les liens entre des points pour étudier les chemins (ensemble de liens et points à traverser pour aller de A à B). En informatique, les graphes sont utilisés pour décrire les liens entre différents serveurs afin d'optimiser le temps et l'énergie mobilisés dans le transfert d'information.

Culture algorithmique Une introduction aux graphes Stocker les images ou les sons

La cryptographie homomorphe La cryptographie Le calcul scientifique et la simulation numérique Conception et systèmes embarqués Transmission de données : les photons en renfort des électrons La programmation informatique et les algorithmes : Cédric Gouy La cryptographie ou comment coder des messages : Renaud Sirdey Géopolitique des câbles sous-marins Stocker nos données numériques sur ADN La pollution numérique Cyberdéfense, nouvelle arme géopolitique Une introduction aux graphes Interrogation d’une base de données relationnelle Qu’est-ce qu’une base de données relationnelle ? La méthode « diviser pour régner » Arbres binaires de recherche Une histoire de l’architecture des ordinateurs La liberté d'expression L'architecture des réseaux et les protocoles de communications Notions de web et d'interface homme-machine

Révisions Bac NSI Médiatropismes Les livres à lire au moins une fois dans sa vie ! Apocalypse : la Première Guerre mondiale La Grande Librairie - Concours de lecture à voix haute Les cours Lumni - Lycée

Partager ce quiz

Copier le lien

facebook

twitter