Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cc graphe 1819 s1 correction

Faculté de Sciences L INFO Année Contrôle Continu Semestre Code de l ? enseignement Intitulé de l ? enseignement Théorie de graphes Nom de l ? enseignant Dr Ahmed-Diouf DIRIEH DIBAD Exercice Distribution de courriers pts Soit le graphe suivant représentant le plan d ? une ville pour la distribution des courriers Existe-t-il un itinéraire permettant au facteur de passer une fois et une seule par chaque rue Justifiez votre réponse Proposer un itinéraire possible Le facteur peut-il partir de n ? importe quel sommet Correction Tous les sommets de degré pair donc par Euler il existe un cycle eulérien ABCFHLKHGFEGKJEDJIDBIA Oui Exercice Tourisme locale pts Voici la carte de localités avec leurs frontières Deux localités se touchant par un seul point ne sont pas considérés comme ayant une frontière commune Dessiner un graphe modélisant la situation décrite Peut-on visiter toutes les localités en franchissant une et une seule fois chacune des localités Proposer un parcours possible s ? il existe Correction A c b d f B a c d e C a b d D a e b c E h g d b F a g G h e f H e g Deux sommets de degré impair donc il existe une cha? ne eulérienne Exercice Tournoi de football pts Un tournoi de football amateur organisé pendant un week-end réunit équipes Les contraintes de temps permettent à chaque équipe de rencontrer au plus cinq des autres équipes Est-il possible de faire jouer à chaque équipe exactement matches Est-il possible de faire jouer à chaque équipe exactement matches Correction Existe-t-il un graphe avec sommets et dont la liste des degrés est la suivant ?? ? degré et c ? est un entier impair Or ? degré ? relations ?? Solution Impossible Existe-t-il un graphe avec sommets et dont la liste des degrés est la suivant ?? ? degré et c ? est un entier pair ? degré ?? Il existe un graphe avec relations Exercice Municipalité et Conseillers pts Le conseil municipal d ? une ville comprend commissions Tout conseiller municipal fait partie de commissions exactement Deux commissions quelconques ont exactement un conseiller en commun Combien y a-t-il de membres dans le conseil municipal Correction Modélisation Les commissions sont les sommets et un conseiller faisant partie d'exactement commissions est représenté par une arête reliant les sommets qui les représentent Règle A Tout conseiller municipal fait partie de commissions exactement a C ? est un graphe complet a sommets il y a arêtes donc conseillers Règle B Deux commissions quelconques on exactement un conseiller commun a Chaque commission a exactement conseillers membres Exercice Lemme de main pts Montrer que dans un graphe le nombre de sommets impairs est toujours pair Correction Soit I Ensemble des sommets de degré impairs P Ensemble des sommets de degré pair S Ensemble des sommets ? degré des sommets S ? degré des sommets de I ? degré des sommets de P i Par le lemme de main ? degré des sommets est pair