UNIVERSITE INUKA

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

Question de cours

Question1[3 Pts]. R\'epondez par vrai ou faux

• a) Tout graphe connexe est complet (F)
• b) Dans le graphe de konisberg la rivi\`ere représentait les arêtes (F)
• c) Si un graphe n'est pas Hamiltonien elle est Eul\'erien. (F)

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

Question3[4Pts]. Soit la carte suivant

• Combien de couleur minimum nécésaire pour colorer ce graphe nombre de couleur vaut 3
• Donner un chemin simple de Madrid à Barcelona. Madrid-Oviedo-Valadolid-Barcelona
• ce graphe est-il connexe? (non)
• Coloration du graphe

Problème1 [5pts].

Aujourd'hui Nathalie est perplexe : que mettre pour cet entretien d'embauche ? Dans son armoire, elle a : 3 pulls, 3 jupes, 3 paires de chaussures à assortir. Elle ne peut pas mettre plusieurs pulls, plusieurs jupes ou plusieurs paires de chaussures et, par ailleurs, il y a des incompatibilités qui sont données dans le tableau suivant, où p1, p2, p3 désignent les trois pulls, j1, j2, j3, les trois jupes, c1, c2, c3 les trois paires de chaussures.

Les combinaisons sont:

• j1,c2,p2
• j2,p1,c3

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:

Après avoirchargé son camion à l'entrepôt noté A,un livreur doit livrer cinq clients notés B,C,D,E et F. Le graphe ci-dessus, modélise le réseau routier en tenant compte des sens de circulation et des temps de parcours en minutes.

• a) Donner un chemin Elementaire de A à F en passant par B,C,D,E Il n'existe pas ce chemin Eléméntaire
• b) Déterminer le plus court chemin de A à F. A-C-D-B-F:46
• c) Après avoir effectuéses livraisons, le livreur doit retourner l'entrepôt. Quel trajet lui permet de minimiser son temps de parcours pour le retour F-D-A:35 ?
• d)En ne tenant pas compte des arrêts n\'ecessaires pour effectuer les livraisons, le trajet du retour est-il plus rapide que celui de l'aller ? Oui, car 35 est plus petit que 42

Problème4[5Points]

A, B, C, D, E, F, G et H désignent huit poissons ; dans le tableau ci- dessous, une croix signifie que les poissons ne peuvent cohabiter dans un même aquarium :

• Construire le graphe G de la situation.
• Quel est le nombre minimum d'aquariums faut-il? 4 Aquariums
• Donner un regroupement par aquariums
  . G1: B,C
  G2: D,G,F
  G3: A,E
  G4: H