UNIVERSITE INUKA

VERIFICATION D'ACTIVITE ET RESOLUTION DE PROBLÈME DE MATHS (VARPM)

Question de cours

Question1[3 Points]. Répondez par vrai ou faux

• a) La ville de konisberg est un graphe Eulérien (F)
• b) a ville de konisberg possède un chemin Eulérien (F)
• c) Il existe des graphes qui possèdent un chemin Hamiltonien et Eulerien. (V)

Question2[3 Points]. Répondez par vrai ou faux

• (a) Le graphe est non-connexe. F
• (b) On peut colorer ce graphe avec 3 couleurs (F)
• (c) Le degré du graphe est 26 (V)
• (d) Le plus cours chemin de A à G du graphe est 34 (F)

Question3[4Points]. Soit la carte suivant

• Préciser le nombre chromatique du graphe d'Haiti nombre de couleur vaut 3
• Ce graphe est-il connexe par voie terrestre?. non
• Préciser un chemin simple de Nord au sud. NORD-ARTIBONITE-OUEST-NIPPES-SUD

Problème2 [5pts].

Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d’activités d’un quartier. Une arête reliant deux de ces sommets indique l'existence d'une voie d’accès principale entre deux lieux correspondants

Pour sa campagne électorale, un candidat souhaite parcourir toutes les voies d'acc\`es principales de ce quartier sans emprunter plusieurs fos la même voie.

• a) Montrer qu'un tel parcours est possible. deux degrés exactement impaires entre A et B, Parcours: B-D-P-B-A-C-E-H-G-F-D-G-C-P-A
• b) Un tel parcours est-il possible pour ce candidat en partant de sa permanence électorale située en P? Non
• c) Un candidat aux élections municipales se trouve dans sa permanence située en zone P quand on lui rappelle qu'il a un rendez-vous avec le responsable de l'hôpital situé en zone H . Suposons que le candidat veut arriver le plus rapide possible, trouver le plus court chemin pour se rendre de P à H. P-B-D-G-H
• d) Combien de temps faut-il prévoir pour éffectuer ce trajet ? 29

Problème3[5Points]

Soit le graphe suivant:

• Donner un chemin simple de D \`a F D-G-C-A-F
• Donner un chemin Elémentaire de G \` a B. G-C-A-F-B
• Un automobiliste doit se rendre de A à C . En utilisant un algorithme, d\'eterminer le trajet le plus rapide pour aller de A à C. A-F-E-B-G-C:42
.
• Le retour sera-t-il plus rapide que l'aller ? C-A:38

Problème4[5Points]

Le directeur d'un petit zoo veut réorganiser l'habitat de telle sorte que les animaux cohabitent dans des enclos plus vastes. Malheureusement, il n'est pas possible de laisser tous les animaux ensemble dans un seul enclos, car certains sont les prédateurs des autres ! Le tableau ci-contre indique, parmi les dix races d'animaux que possède le zoo, lesquelles sont les prédateurs ou les proies des autres.
* Signifie l'imcompatibilité de deux animaux(Exemple: a et b ne peuvent pas se trouver dans un même enclos )

• Combien d'enclos le directeur du zoo doit-il prévoir 3 enclos ?
• Donner une répartition des animaux par enclos Enclo1:h,j,e,b; Enclo2:i,c,a,d,g; Enclo3: f

Problème1 [5pts].

• Certains travaux ne peuvent être réalisés en même temps. Réprésenter ces contraintes par un graphe.
• On supose que le temps nécésaire pour chaque travail est le même(une séquence de 20min). Déterminer le temps minimum pour réaliser ces travaux.
• Proposer une organisation pour r\'ealiser les six travaux.

Organisation d:

• Travaux2,Travaux4
• Travaux1, Travaux3
• Travaux6
• Travaux5.