Théorie de Graphes Quiz

Quelle est la définition d'un graphe orienté ?

• • Un graphe où chaque sommet est relié à tous les autres sommets.

• • Un graphe où les arêtes ont une direction spécifique

• • Un graphe qui ne contient aucun cycle

• • Un graphe qui contient une chaîne

Quelle est la définition du degré d'un sommet dans un graphe non orienté ?

• • Le nombre d'arêtes incidentes à un sommet

• • Le nombre des sommets voisins d'un sommet

• • Le nombre de chemins menant à ce sommet

Le degré d'un sommet dans un graphe non orienté est égal au nombre d'__________ incidentes à ce sommet

Qu'est-ce qu'un graphe complet ?

• • Un graphe où chaque sommet est relié à tous les autres sommets

• Un graphe contenant un circuit

• • Un graphe sans arêtes

• • Un graphe avec un seul sommet

Le problème de coloriage de graphe consiste à déterminer le nombre minimal de ________ nécessaires pour colorier un graphe de telle sorte que deux sommets adjacents ne possèdent pas la même couleur.

Quelle était la conclusion tirée par les équipes à la fin de l'histoire ?

• a) Les Graphes Gloutons étaient les seuls à avoir réussi à cause de leur approche directe

• b) Les Pouvoirs de Welsh étaient les seuls à avoir réussi grâce à leur méthodologie sophistiquée

• c) Les deux équipes pouvaient réussir en utilisant des approches différentes mais efficaces

Dessinez un graphe qui contient un cycle

Dans un graphe orienté, quel terme désigne le nombre d'arêtes sortantes à un sommet ?

• Le degré du sommet

• Le demi-degré extérieur du sommet

• Le demi-degré intérieur du sommet

• La connectivité du sommet

• La densité du sommet

Dans un graphe orienté, quel terme désigne le nombre d'arêtes entrants à un sommet ?

• Le degré du sommet

• Le demi-degré extérieur du sommet

• Le demi-degré intérieur du sommet

• La connectivité du sommet

• La densité du sommet

Qu'est ce qu'un cycle dans le graphe orienté

• Chemin

• Chaîne

• Circuit

• Tour