Graphes Et Optimisation - Exercices

تحية طيبة إلى كل أعضاء و زوّار جوهرة سوفت في المنتدى التعليمي




Ici , on va collecter quelques exercices d'applications en ceux qui concerne la matière :


Graphes et Optimisation

Exercice N°1

Dans une partie de jeu d'échec , le joueur a effectué les déplacements suivants pour son clavier : b1 , a3 , b5 , c3 , d5

Représenter les déplacements du son cavalier par un graphe orienté

Exercice N°2

Construire un graphe orienté dont les sommets les entiers entre 1 et 12 et dont les arcs représentent la relation : être diviseur de

Donner les extrémités initiales et terminales de chacun des arcs du graphe

Exercice N°3

Un tournoi d'échecs oppose 6 personnes . Chaque joueur doit affronter tous les autres

1- Construisez un graphe représentant toutes les parties possibles

2- Quel type de graphe obtenez vous

3- Si chaque joueur ne joue qu'un match par jour , combien de jours faudra-t-il pour terminer le tournoi

4- Aidez-vous du graphe pour proposer un calendrier des matchs

Exercice N°4

Trois professeurs P1 , P2 , P3 doivent donner ce lundi un certain nbre d'heure de cours à trois classes C1 , C2 , C3


- P1 doit donner 2 heures de cours à C1 et une heure à C2

- P2 doit donner une heure de cours à C1, une heure à C2 et une heure à C3


- P3 doit donner 2 heure de cours à C1 , une heure à C2 et deux heures à C3



Comment Représenter cette situation par un graphe

Quel Type de graphe obtenez vous

Combien faudra-t-il de plages horaires au minimum

Aidez vous du graphe pour proposer un horaire du lundi pour ces professeurs


ـــــــــــــــــــــــــــــــــــــــــــــ ــــــــــــــــــ

Fin de la première Série

Attendez le TD N°2

TD N°2

Exercice N°1
(exercice de D.S)

On souhaite prélever 4 litres de liquides dans un tonneau. Pour cela , nous avons à notre disposition deux récipients non gradués, l'un de 5 litres , l'autre de 3 litres .

Comment doit-on faire ?

Représenter cette situation par un graphe.

Exercice 2

Les données suivantes représentent l'intervention de 5 arbitres dans un tournoi , 6 rencontres sont programmées par la journée.

A1 : M1 , M2
A2 : M3 , M4 , M2
A3 : M5 , M4 , M6
A4 : M1 , M3
A5 : M5 , M6

Représenter la programmation du déroulement des rencontres de la 1ère journée , sachant que 2 sommets sont reliés par une arrête si les rencontres correspondantes peuvent se dérouler au même temps.

Exercice 3

Sur un échiquier 3*3 , les deux cavaliers noirs sont placés sur les cases a1 et c1 , les deux cavaliers blancs occupant les cases a3 et c2.

Aidez-vous d'un graphe pour déterminer les mouvements qui permettent aux cavaliers blancs de prendre les places des cavaliers noirs , et vice versa , sachant que le cavalier ne peut faire qu'un mouvement en L.


Le Shéma


ـــــــــــــــــــــــــــــــــــــــــــــ ــــــــــــــــــــــــــ

Fin de la deuxième Série

Attendez le TD N°3

TD N°3

Exercice n°1 :

Le tableau ci-dessous donne les liaisons possibles entre les pays assurées par différents aéroports.



1 - Représenter les différents liaisons par un graphe
2- Déterminer les destinations des vols partant de chaque pays

Exercice n°2 :

Peut - on tracer le graphe correspondant au tableau suivant ? Pourquoi ?




encore

Exercice n°3 :

1. Une suite décroissante (au sens large) d'entiers est graphique s'il existe un graphe simple dont les degrés des sommets correspondant à cette suite (par exemple , le triangle à trois sommets correspond à la suite 2,2,2). Les suites suivantes sont-elles graphiques ? Trouver les stables et les cliques possibles de chaque graphe :

a- 3,3,2,1,1
b- 3,3,1,1
c- 3,3,2,2
d- 4,2,1,1,1,1
e- 5,3,2,1,1,1
f- 5,4,3,1,1,1,1

2. Trouvez deux graphes distincts correspondant à la suite (3,2,2,2,1).



encore

Exercice n°4 :



1- Ce graphe est il planaire ? Si oui déterminer une représentation topologique planaire et déterminer le nombre des faces

2- Déterminez le nombre chromatique de ce graphe



encore