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 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).

En déduire que, dans un graphe planaire, m = O(n).

Exercice 3 Ecrire une fonction int[][] Incidence(Matrice A) qui calcule la matrice d’incidence d’un graphe à partir de sa matrice d’adjacence.

Exercice 4 Ecrire une fonction static Vecteur chemin0(Matrice A) qui

rend la première ligne de A^{∗} sous forme d’un objet de la classe

class Vecteur {
  int[] c;
  int d;
  Vecteur(int x) {
    c=new int[x];
     d=x;
}
Exercice 5 Ecrire une fonction static Liste[] ListeSucc(Matrice A)

qui renvoie la représentation par liste de successeurs.