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

Donnez l'ordre du graphe

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

Nous avons un graphe non orienté avec des poids positifs sur les arêtes. Pouvons-nous utiliser l'algorithme de Dijkstra pour trouver les chemins les plus longs ? (*)

Quel type de graphe est représenté ?

Quel type de graphe est représenté ?

Pour un graphe G à n sommets, un arbre couvrant de poids minimum contient : 

L'algorithme de Dijkstra permet la recherche de plus courts chemins dans un graphe pondéré, orienté ou non. Pour qu'il fonctionne, le graphe doit avoir l'une des propriétés suivantes, laquelle ?

Un arbre avec 10 arêtes doit avoir 11 sommets.

Pouvons-nous trouver l'arbre couvrant de poids maximum (au lieu du minimum) en utilisant les algorithmes de Kruskal ou de Prim ?

Un graphe contenant des sommets isolés :