Université de Picardie Jules Verne AU 2018-2019
M2 3EA RoVA Systèmes Robotiques Hétérogènes et Coopératifs
TD 1 : Théorie des Graphes
Exercice I : Connectivité d'un graphe orienté
Pour les trois graphes orientés suivants:
1. Déterminer s'il s'agit d'un graphe faiblement connexe ou fortement connexe,
2. Déterminer le degré entrant de chaque sommet.
Exercice II : Graphes et matrices
Déterminer la matrice des degrés, la matrice d'adjacence, la matrice d'incidence
et la matrice laplacienne des (di)graphes suivants:
1. G = S5
2. G = C6
3. G = P3
4. G = K4
5. D = C5 (cycle orienté),
6. D = P5 (chaîne orientée ou chemin),
7. Les deux digraphes D montrés ci-dessous:
Attention: Pour les digraphes considérer la notion de degré entrant.
Fabio Morbidi
Université de Picardie Jules Verne AU 2018-2019
M2 3EA RoVA Systèmes Robotiques Hétérogènes et Coopératifs
Exercice III : Étude des propriétés d'un graphe [Matlab]
1. Écrire une fonction Matlab qui prend en entrée un graphe non orienté arbitraire
(à vous de choisir la représentation la plus adaptée) et qui fournit en sortie la
valeur propre et le vecteur propre de Fiedler de sa matrice laplacienne,
2. Écrire une fonction Matlab qui prend en entrée un graphe orienté ou non orienté
arbitraire et qui fournit en sortie la matrice d'incidence du graphe,
3. Écrire une fonction Matlab qui prend en entrée un graphe non orienté arbitraire et
qui fournit en sortie le nombre de cycles dans le graphe, une variable booléenne qui
vaut 1 si le graphe est connexe et 0 sinon, et un vecteur qui contient le degré des
sommets du graphe,
4. Créer une fonction Matlab qui permet d'étudier comment la valeur propre la plus
forte de la matrice laplacienne du graphe G = Cn varie pour n qui tend vers l'infini.
Exercice IV : Operations sur les graphes
Etant donnés deux graphs G1 = (V1, E1) et G2 = (V2, E2), l'union et l'intersection de G1 et G2
sont définies respectivement:
G1 ∪ G2 = (V1 ∪ V2, E1 ∪ E2),
G1 ∩ G2 = (V1 ∩ V2, E1 ∩ E2).
1. Déterminer l'union et l'intersection de G1 = K3 et G2 = K3 et de G1 = P3 et G2 = C4,
2. Existe-t-il une relation entre le spectre de la matrice laplacienne de G1 (ou de G2)
et celui de la matrice laplacienne de G1 ∪ G2 et G1 ∩ G2 ?
Exercice V : Graphes aléatoires [Matlab]
Les graphes aléatoires peuvent être utilisés pour la modélisation d'un système en réseaux
où le nombre de sommets (les agents) et/ou d'arêtes (les canaux de communication) n'est
pas fixe mais suit un processus aléatoire.
Il existe plusieurs modèles de graphes aléatoires dans la littérature. Un des modèles les
plus simples et étudiés est le graphe aléatoire uniforme, souvent noté G(n,p). Dans un
graphe aléatoire uniforme G(n,p), chacune des n(n–1)/2 arêtes est présente avec
probabilité p et absente avec probabilité 1 - p, cela indépendamment du statut des autres
arêtes. Le cas p = 0.5 a été étudié par le fameux mathématicien Paul Erdös dès 1947.
Écrire une fonction Matlab qui prend en entrée le paramètres p et n d'un graphe aléatoire
uniforme et qui utilise les outils graphiques de Matlab pour en dessiner une réalisation.
Fabio Morbidi
