^{PDFprof.com Search Engine}

Exercices d'examen sur les graphes (niveau L3) avec corrigés

Comment savoir si un graphe est régulier ?
Un graphe est dit régulier s'il est simple et si tous ses sommets ont le même degré. On s'intéresse dans cet exercice aux graphes réguliers dont les sommets sont de degré 3. Que dire du nombre de sommets d'un tel graphe? Démontrer que, pour tout p≥ 2 p ≥ 2, il existe un graphe régulier d'ordre 2p 2 p dont les sommets sont de degré 3.
Comment calculer la longueur d’un graphe non orienté connexe ?
Soit G un graphe non orienté connexe qui possède au moins un circuit simple de longueur non nulle. On désigne par f(G) la longueur du plus petit circuit simple de longueur non nulle de G. Prouver que f(G) 2 diam(G) + 1. b) Trouver un exemple réalisant l’égalité f(G) = 2 diam(G) + 1.
Comment calculer l’implication d’un graphe ?
Soit G = (V; E) un graphe non orienté connexe non vide. Soit k = maxx2V deg(x). Prouver l’implication k(k 1)rad(G) Exercice 18. Soit G = (V; E) un graphe simple non orienté non vide. Soit k = minx2V deg(x). possède un chemin simple de longueur k. possède un circuit simple de longueur au moins k + 1 si k vaut au moins 2. Exercice 19.
Comment calculer la représentation planaire d’un graphe ?
On considère une représentation planaire d’un graphe ayant exactement 300 faces, toutes triangulaires. Déterminer les nombres A d’arêtes et S de sommets de ce graphe. Comparer la somme des degrés des nœuds de ce graphe avec celle de son dual.

Comment savoir si un graphe est régulier ?