Exercices (pc 7) Corrigé

Exercice 1 On a

II^{t} = D − A − A^{t}

où D est la matrice diagonale de coefficients D_{ii} = le degré du sommet i et A est la matrice d’adjacence.

Exercice 2 On a des cycles ssi la matrice

A^{+} = A + … + A^{n}

a un 1 sur la diagonale. On peut le tester en utilisant l’algorithme naïf avec les modifications nécéssaires ou l’algorithme de Warshall avec l’initialisation T = A.

Exercice 3 On raisonne par récurrence sur le nombre de faces. Si f = 1, le graphe est un arbre et le résultat est vrai puisque dans ce cas n = m + 1.

Si f > 1, on choisit une arete a sur un cycle de G. Comme un cycle sépare le plan en deux régions, l’arete a borde deux faces distinctes et on obtient le résultat par récurrence.