Exercices (pc 7)

Exercice 1 Soit G = (S, F) un graphe ayant n sommets et m flèches. Soit I la matrice d’incidence de G. Quelle matrice obtient on en multipliant I par sa transposée ?

Exercice 2 Donnez, en application de l’algorithme de calcul de la fermeture transitive, un algorithme qui vérifie si un graphe n’admet pas de cycle.

Exercice 3 Montrer que dans un graphe planaire connexe, on a la formule

n − m + f = 2

entre le nombre n de sommets, le nombre m d’aretes et le nombre f de faces (formule d’Euler).