Graphes orientés II

Précédent / Suivant / Table des matières

Travaux Dirigés N°6

Graphes orientés II

EL METHNI M.

Exercice I :

Dans un groupe de 36 personnes, numérotées de 0 à 35, le jeu d’influence est modélisé par une relation binaire R : xRy la personne numéro x influence la personne numéro y.
Cette relation est représentée par la matrice carrée suivante, où une × à la ligne numéro i et à la colonne numéro j signifie que la personne numéro i influence la personne numéro j.
Une personne numéro i₀ exerce une influence de degré k sur la personne numéro i_k s’il existe un chemin (de transition) i₀i₁i₂…i_k tel que pour j=0, …, k-1 s_j R s_j₊₁.
La personne numéro 1 exerce-t-elle une influence (d’un degré k à déterminer) sur la personne numéro 18 ? Si oui quel est ce chemin ?

R	0										1										2										3
R	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5

Exercice II :

Soit G=(S,A) un graphe orienté d’ordre n, et M sa matrice d’adjacence. Notons I la matrice unité d’ordre n.

1) On suppose que G ne contient pas de circuit (de longueur >0). Que peut-on dire de la longueur du plus long chemin de G ?
2) On suppose que G ne contient pas de circuit (de longueur >0).
     a) Montrer que M est nilpotente ( k tel que M^k =0)
     b) Pourquoi peut-on affirmer que Mⁿ =0 ?
     a) Si la longueur du plus long chemin de G est l quel est l’indice de nilpotence de M ? (le plus petit k tel que M^k =0)
3) Montrer que si M est nilpotente alors G ne contient pas de circuit (de longueur >0).
4) Montrer que si G ne contient pas de circuit (de longueur >0) alors I-M est inversible et si on note (I-M)^-1= (a_ij) alors a_ij est le nombre total des chaînes de toutes les longueurs de s_i à s_j.

Exercice III :

Soit G=(S,A) un graphe orienté avec S={s₁, s₂, s₃, …, s_n}.
Pour tout chemin c=[x₀a₁x₁a₂ x₂a₃x₃ … x_p_-1a_px_p] les sommets x₁, x₂, x₃, …, x_p (appartenant à S) sont appelés sommets intermédiaires de c. Pour tout entier naturel k on considère la relation binaire R_k définie sur S par : Si k≠0 s_i R_k s_j si et seulement si il existe dans G un chemin élémentaire de s_i à s_j dont tous les intermédiaires sont dans {s₁, s₂, s₃, …, s_k}. Si k=0 s_i R₀ s_j si et seulement si (s_i,s_j)A

1) Soit M la matrice booléenne du graphe G. Donner la matrice M⁺ de la fermeture transitive de G. Rappeler le coût du calcul de M⁺.

2) Que représente R_n? Quelle est sa matrice booléenne ?
3) Soit A une matrice carrée booléenne d’ordre n. On considère la suite matricielle (A_k) définie par : . Montrer que A_n=A+ A²+ A²+ … + Aⁿ4) Appliquer l’algorithme de Warshall au graphe suivant :

Pour k=1 à n

Pour i=1 à n

Pour j=1 à n

m_ij= m_ij+ m_ik m_kj

5) Que devient la ligne d’indice i si ? En déduire une version améliorée de l’algorithme de Warshall.