QCM : Introduction à la théorie des graphes — 12 questions

Explication

La définition précise d’un graphe, donnée dans la source, indique qu’il s’agit d’une structure composée d’un ensemble de sommets et d’un ensemble d’arêtes ou arcs qui relient ces sommets. Les autres options ne correspondent pas à cette description, notamment parce qu’elles excluent la relation entre éléments ou proposent des structures sans liens.

Explication

Leonhard Euler est crédité d’avoir formulé la question sur la traversée des ponts de Königsberg, ce qui a conduit à la naissance de la théorie des graphes. Les autres mathématiciens mentionnés ont apporté d’autres contributions, mais pas à cette problématique spécifique.

Explication

La question posée par Euler concernant la traversée des ponts de Königsberg a été à l’origine de la formalisation du concept de chemin eulérien, ce qui a conduit à la naissance de la théorie des graphes. Cette problématique pratique a donc été la cause principale de cette avancée mathématique.

Explication

Le degré d’un sommet dans un graphe non-orienté correspond au nombre d’arêtes qui touchent ce sommet, c’est-à-dire celles qui lui sont incidentes. La source précise cette définition, ce qui en fait une caractéristique essentielle pour analyser la connectivité du sommet dans le réseau.

Explication

Un graphe orienté est conçu pour représenter des relations où le sens ou la direction est important, comme les flux ou dépendances, ce qui est essentiel dans la modélisation de systèmes directionnels.

Explication

Un circuit est un chemin dont le premier et le dernier sommet sont identiques, formant une boucle fermée, tandis qu’un chemin ne possède pas cette contrainte. La définition précise indique que la différence essentielle est la fermeture en boucle pour le circuit.

Explication

Euler a posé la question sur les ponts de Königsberg à la fin du XVIIIe siècle, ce qui a marqué le début de la théorie des graphes. La mention dans le texte indique que cette problématique a été formulée dans cette période, correspondant à la fin du XVIIIe siècle.

Explication

Euler a posé la question de savoir s'il était possible de traverser chaque pont une seule fois, en revenant éventuellement à son point de départ, ce qui a marqué le début de la théorie des graphes. La réponse est donc la deuxième option, qui correspond précisément à cette problématique.

Explication

L’utilisation de la notion de composantes connexes dans un réseau de transport consiste à repérer les zones isolées ou non connectées, ce qui est essentiel pour améliorer la cohérence et l’efficience du réseau. Les autres options ne correspondent pas directement à l’application de cette notion dans le contexte de modélisation par graphes.

Explication

Un graphe fortement connexe est défini par le fait que pour chaque paire de sommets (x, y), il existe un chemin orienté de x vers y et un autre de y vers x, ce qui garantit une accessibilité bidirectionnelle entre tous les sommets.

Explication

Le texte explique que le tri topologique consiste à ordonner les sommets d’un graphe orienté selon une relation d’ordre partiel, propriété propre aux graphes acycliques, et que cette procédure est associée à Euler dans le contexte de la théorie des graphes. Euler est donc crédité d’avoir formulé ou proposé cette méthode d’organisation dans ce cadre.

Explication

Euler a posé la question de traverser chaque pont de Königsberg une seule fois, ce qui a conduit à la formalisation du problème du chemin eulérien, fondement de la théorie des graphes.