Étant donné un graphe  non dirigé et connexe d'ordre , combien de sommets et d'arêtes contient un arbre couvrant de G ?

Indiquez les nombres sous ce format : nombre de sommets, nombre d'arêtes

Exemple : x, y

L'algorithme de Kruskal trouve toujours un arbre couvrant minimal dans un graphe.

Concernant l'algorithme de Bellman-Ford, lequel des énoncés suivants est correct ?

Pour l'algorithme de Dijkstra, l'algorithme produira le même arbre, quel que soit le nœud choisi comme nœud de départ, à condition qu'aucun des arcs du graphe n'ait le même poids.

Dans un arbre avec sommets, le nombre d'arêtes est :

Si l'on essaye de construire un graphe orienté sans cycle à n sommets ayant le plus long chemin possible, quelle sera la longueur maximum de ce chemin ?

S'agit-il d'un arbre ?

Pour un graphe  avec  nœuds, une étudiante exécute l'algorithme de Bellman-Ford pour itérations. Elle effectue ensuite une itération supplémentaire et remarque que le chemin le plus court entre deux nœuds a diminué. 

Qu'est-ce que cette observation suggère à propos du graphe ?

Quel est le plus court chemin de 0 à 2 ?

Le chemin le plus court d'un nœud source vers tous les autres nœuds dans un graphe restera inchangé si :