serie01 GRA .pdf


Nom original: serie01_GRA.pdf
Auteur: boukala

Ce document au format PDF 1.4 a été généré par Writer / LibreOffice 3.3, et a été envoyé sur fichier-pdf.fr le 21/11/2011 à 17:02, depuis l'adresse IP 41.200.x.x. La présente page de téléchargement du fichier a été vue 5917 fois.
Taille du document: 41 Ko (1 page).
Confidentialité: fichier public


Aperçu du document


Département d'Informatique
Module Théorie des graphes
3ème Année Licence Informatique

Serie d'exercices N°1
(Notions Fondamentales des graphes)



Toute information détenue par une personne est répercutée
dans la minute qui suit à ses connaissances (et uniquement à
elles)

Quel est le temps maximal entre le moment où une des 15 fans
apprend une chose nouvelle sur leur idole, et celui où le groupe
entier est au courant ?
Exercice 5 organisation d’un examen

Exercice 1
Donner la représentation matricielle du graphe suivant, Trouvez les
degrés extérieurs et intérieurs de chacun des sommets.

On veut organiser un examen comportant, outre les matières
communes, 6 matières d’options :
Français (F), Anglais (A), Mécanique (M), Dessin industriel (D),
Internet(I), Sport (S) ; les profils des
candidats à options multiples sont :
F,A,M
D,S
I,S
I,M
1 - Quel est le nombre maximum d’épreuves qu’on peut mettre en
parallèle ?
2 - Une épreuve occupe une demi-journée ; quel est le temps
minimal nécessaire pour ces options ?
Exercice 6

Exercice 2
a. Montrer qu'un graphe simple a un nombre pair de sommets de
degré impair.
b. Montrer qu'un graphe simple admet deux sommets de même
degré
Exercice 3
On s'intéresse aux graphes 3-réguliers. Construisez de tels graphes
ayant 4 sommets, 5 sommets, 6 sommets, 7 sommets. Qu'en
déduisez-vous ? Prouvez-le !
Exercice 4
Un groupe de 15 fans d’un chanteur célèbre, possède les deux
particularités suivantes :


Chaque personne connaît au moins 7 autres

On a 6 wagons à trier. Dans la gare de triage, les wagons entrent
dans l'ordre 2, 5, 3, 6, 1, 4 et doivent sortir dans l'ordre croissant,
Deux wagons i et j peuvent être mis sur la même voie de triage si et
seulement s'ils entrent dans l'ordre dans lequel ils doivent sortir.
Dessiner le graphe illustrant la situation, en indiquant ce que
représentent les sommets et les arêtes du graphe.
Quel sera le nombre minimal de voies de triage nécessaires ?


Aperçu du document serie01_GRA.pdf - page 1/1




Télécharger le fichier (PDF)




Sur le même sujet..





Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00078456.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.