th graphes (2) .pdf


Nom original: th graphes (2).pdfTitre: serie 2 2 Auteur: Administrateur

Ce document au format PDF 1.3 a été généré par FreePDF XP 3.24 - http://shbox.de / GPL Ghostscript 8.60, et a été envoyé sur fichier-pdf.fr le 07/02/2011 à 23:14, depuis l'adresse IP 196.217.x.x. La présente page de téléchargement du fichier a été vue 2086 fois.
Taille du document: 136 Ko (2 pages).
Confidentialité: fichier public


Aperçu du document


Département de Mathématiques
Resp. Prof. : M. HAJAR
Chargé Prof. : A . LAMRANI

Année Universitaire: 2009/2010
LST-info. S4
Module: I 1106
Université My Ismail
Fac. Des Sci. et Tech. Errachidia

Théorie des graphes
Série de Travaux
Travaux Dirigé
Dirigés : 2
Connexité - Tri topologique
Exercice 1
Donner les composantes connexes des graphes suivants:

Puis représenter les graphes réduits associé.

Exercice 2
Effectuez un tri topologique du graphe suivant :

Arbres –Arbres couvrant
Exercice 3
Designer les arbres, Arborescences et forets parmi les graphes suivantes :

Exercice 4
Donner trois arbres couvrant du graphe suivant :

Exercice 5
On considère le graphe avec arêtes valuées suivant :

1- Donner un arbre couvrant de poids 19.
2- Donner deux arbres couvrants de poids 14.
3- Donner l’arbre couvrant de poids minimum.

Plus court chemin
Exercice 6
Appliquer l’algorithme de DIJKSTRA sur le graphe suivant :

pour trouver l’arborescence des plus courts chemins enracinée en r.

Coloration
Exercice 7
Dessiner cinq graphes dont le degré est 5 et le nombre chromatique est respectivement 2, 3, 4, 5 et 6.

Exercice 8
On veut colorier la carte suivante :

de telle manière que deux régions frontalières parmis A, B, C, D et E aient des couleurs différentes.
Combien de couleurs au minimum faudra-t-il prévoir ?

Exercice 9
Sur une plaquette rectangulaire on veut réaliser le schéma électrique suivant:

Les positions des entrées et des sorties sont prédéfinies.
Déterminer le nombre minimum de couches de circuits imprimés que l’on doit utiliser.


th graphes (2).pdf - page 1/2


th graphes (2).pdf - page 2/2



Télécharger le fichier (PDF)


th graphes (2).pdf (PDF, 136 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


th graphes 2
poly algo
graphesentrainement
theorie de graphe
l1 seg probabilitEs et statistiques descriptives stat serie corrigee n 2 distribution statistique a deux caracteres
graphe bac eco gestion

Sur le même sujet..