Les graphes

1 / 10

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

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

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 trait reliant deux points
un point sur un graphe
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 être orientée d'un nœud vers un autre.
Une arête peut relier plus de deux nœuds.

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 est relié directement ou indirectement à chaque autre nœud.
Un graphe où toutes les arêtes se croisent.
Un graphe où chaque nœud n'est pas directement relié à 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 et 1
n'importe quel nombre
0, 1 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],3:[1],4:[1,2],5[]}
ADJ = {0:[1,2],1:[0,3,4],2:[0,4,5],3:[1],4:[1,2]}
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 ?

L'arête [2] n'a pas lieu d'être car elle ne relie pas deux nœuds.
Les arêtes [0,1] et [1,0] ne peuvent être écrites toutes les deux car elles sont redondantes.
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 ?

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

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

Joue à ce quiz et gagne facilement jusqu'à 80 Lumniz en te connectant !

Il n’y a pas de Lumniz à gagner car tu as déjà consommé cet élément. Ne t'inquiète pas, il y a plein d'autres contenus intéressants à explorer et toujours plus de Lumniz à gagner.

-> En savoir plus

Quiz Numérique et sciences informatiques10 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 Organisation des données

La cryptographie homomorphe Conception et systèmes embarqués La programmation informatique et les algorithmes 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 L'architecture des réseaux et les protocoles de communications Notions de web et d'interface homme-machine Les algorithmes de tri Notion de listes en informatique et application aux images numériques Culture algorithmique Structuration en réseau Principe de transmission de l'information Composants élémentaires d'un ordinateur Des humains et des langages Bugs Langage de plus haut niveau et compilation

Révisions Bac NSI Médiatropismes TikTok, l'ombre chinoise Les livres à lire au moins une fois dans sa vie ! Apocalypse : la Première Guerre mondiale La Grande Librairie - Concours de lecture « Si on lisait à voix haute »

Partager ce quiz

Copier le lien

facebook

twitter