On considère un réseau de transport avec le flot suivant , où désigne la source et le puits : 

S'agit-il effectivement d’un flot ?

Quelle est la plus grande valeur du nombre chromatique d’un graphe à    sommets ?

Lors de son execution, l'algorithme de Prim garantit

Si G admet une coloration à 3 couleurs, alors G est 3-coloriable.

Pour l'algorithme de Prim, l'algorithme peut choisir n'importe quel nœud comme premier nœud de l'arbre, mais il trouvera le même arbre couvrant tant que les arêtes du graphe n'ont pas le même poids.

Exécutez l'algorithme de Kruskal sur le graphe ci-après. Dans votre réponse, listez l'ordre dans lequel les arêtes sont ajoutées à l'arbre couvrant de poids minimal.

Listez les arêtes dans ce format : E1, E2, E3,...

Soit le graphe d'ordre 12 et de taille 9 présenté dans la figure suivante. Combien de composantes connexes possède ce graphe ?

Considérant le graphe G présenté ci-après :

Donnez l'ordre du graphe

Quelles affirmations concernant le graphe suivant sont vraies ?