Manipulation des représentations - solutions

Retour à l’exercice

Question 1

• Matrices d’adjacence
  1. \[\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix}\]
  2. \[\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix}\]
  3. \[\begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}\]
• Listes de successeurs :

  1. sommet	a	b	c	d
     successeurs	b,c	a,c,d	a,b	b

  2. sommet	a	b	c	d
     successeurs	b		a,b	b

  3. sommet	a	b	c	d	e
     successeurs	c		e	a	d

• Listes de prédécesseurs :

  1. sommet	a	b	c	d
     prédécesseurs	b,c	a,c,d	a,b	b

  2. sommet	a	b	c	d
     prédécesseurs	c	a,c,d

  3. sommet	a	b	c	d	e
     prédécesseurs	d		a	e	c

Question 2

• Graphes :
  1. 
  2. 
  3. 
• Matrices d’adjacence :
  1. \[\begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}\]
  2. \[\begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}\]
  3. \[\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{pmatrix}\]

Question 3

• Graphes :
  1. 
  2. 
• Listes de successeurs :

  1. sommet	a	b	c
     successeurs	b,c	a	a

  2. sommet	a	b	c	d
     successeurs	d	a		b,c

• Listes de prédécesseurs :

  1. sommet	a	b	c
     prédécesseurs	b,c	a	a

  2. sommet	a	b	c	d
     prédécesseurs	b	d	d	a