Mines Informatique MP 2003

Thème de l'épreuve Logique propositionnelle trivaluée. Coloration de graphes.
Principaux outils utilisés graphes généraux, tables de vérité, logique propositionnelle, itérateurs sur les listes, récurrences, algorithmes récursifs
Mots clefs lois de De Morgan, nombre chromatique, méthode de HÖrner

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE L'AÊRONAUTIQUE ET DE L'ESPACE, DES TECHNIQUES AVANCÉES, DES TELECOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT--ÊTOENNE, DES MINES DE NANCY DES TÉLÉCDMMUNIÇATIONS DE BRETAGNE, ÉCOLE POLYTECHNIQUE (Filière T.S.I.) CONCOURS D'ADMISSION 2003 ÉPREUVE D'INFORMATIQUE Filière MP (Durée de l'épreuve : 3 heures) Sujet mis àla disposition des concours Cycle International, ENSTIM et TPE--EIVP. Les candidats et les candidates sont priés de mentionner de façon apparente sur la première page de la copie : « INFORMATIQUE -- Filière MP » RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES . L'énoncé de cette épreuve, y compris cette page de garde, comporte 8 pages. 0 Si, au cours de l'épreuve, un candidat ou une candidate repère ce qui lui semble être une erreur d'énoncé, il ou elle le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il ou elle a décidé de prendre. - Tout résultat fourni dans l'énoncé peut être utilisé pour les questions ultérieures même s'il n'a pas été démontré. - Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents même lorsque l'énoncé ne le demande pas explicitement. . L'utilisation d'une calculatrice ou d'un ordinateur est interdite. COMPOSITION DE L'ÉPREUVE L'épreuve comporte deux parties indépendantes : 0 un exercice de logique des propositions, page 2, à résoudre en 45 mn environ ; - un problème d'algorithmique, pages 3 à 8, à résoudre en 135 mn environ. 1. Exercice de logique -- 45 mn environ Logique propositionnefie tri--valuée On désire étendre la logique propositionnelle bivaluée classique (notée par la suite 45) de sorte à prendre en compte, en plus de V (vrai) et F (faux), une troisième valeur de vérité, notée [ (pour indéterminé). ? La logique de Lukasiewicz, notée 15, est une telle logique tri-valuée dans laquelle le connecteur de négation ( --' ), le connecteur de conjonction ( A ), le connecteur de disjonction ( v ) et le connecteur d'implication ( => ) sont définis par les tables de vérités suivantes : On dit que deux propositions sont équivalentes dans une logique donnée ..[' si elles ont même table de vérité dans cette logique. D 1 -Indiquer une proposition P1 équivalente dans 45 à la proposition «x v y » et n'utilisant pas d'autres connecteurs que --1 et A. Les propositions P1 et « x v y » sont-elles équivalentes dans ..[3 '? E] 2 -- Indiquer une proposition P2 équivalente dans ..[ê à la proposition « x => y » et n'utilisant pas d'autres connecteurs que -1 et v. Les propositions P2 et « x =: y » sont-elles équivalentes dans 4% ? Cl 3 -- Établir (en détaillant son obtention) la table de vérité dans J3 de la proposition P3 suivante : ((x=>y) A ((--x)=>y)) =>y-- Cette proposition est--elle une tautologie dans ..[5 (la définition d'une tautologie dans la logique °['3 reste la même que dans la logique J£) ? D 4 -- On appelle littéral une variable pr0positionnelle ou sa négation. Dans 45, toute proposition logique admet une forme normale disjonctive (c'est--à--dire une disjonction de conjonctions de littéraux) qui lui est équivalente. Établir une proposition P4 sous forme normale disjonctive équivalente dans .,[5 àla proposition « (x v y) => 1 ». Les propositions P.; et « (x v y) => z » sont-elles équivalentes dans ..[â ? D 5 -- Peut--on faire un raisonnement par contraposition dans 45 (on justifiera la réponse) '? Cl 6 - On définit un ordre sur les valeurs F, I et V par : F < 1 < V. On considère une logique Jtri--valuée pour laquelle simultanément : . J'est une extension de ..[5 pour les quatre connecteurs usuels (--1, A, v, =) ; autrement dit, les restrictions aux valeurs V et F des tables de vérité de J donnent les tables de vérité de ..[ê ; le connecteur A est commutatif ; la proposition « x v y » est équivalente à P1 ; la proposition << x => y » est équivalente à P; ; pour toute valeur de y, la fonction x t----> x A y croît au sens large avec x ; - les propositions << --. (----. x) » et « x » sont équivalentes. Combien y a--t--il de telles logiques (on justifiera la réponse) '? 2. Problème d'algorithmique -- 135 mn environ Coloration d'un graphe Préliminaire concernant la programmation : il faudra écrire des fonctions ou des procédures à l'aide d'un langage de programmation qui pourra être soit Caml, soit Pascal, tout autre langage étant exclu. Indiquer en début de problème le langage de programmation choisi ; il est interdit de modifier ce choix au cours de l'épreuve. Certaines questions du problème sont formulées différemment selon le langage de programmation ; cela est indiqué chaque fois que c'est nécessaire. Par ailleurs, lorsqu'un candidat ou une candidate écrira une fonction ou une procédure en langage de programmation, il ou elle précisera si nécessaire le rôle des variables locales et pourra définir des fonctions ou procédures auxiliaires qu'il ou elle explicitera. Enfin, lorsque le candidat ou la candidate écrira une fonction ou une procédure, il ou elle pourra faire appel à une autre fonction ou procédure définie dans les questions précédentes. Définitions et notations On utilisera dans tout le problème les notations et définitions suivantes : - une paire est un ensemble composé de deux éléments a et b distincts et est notée {a, 17} (ce qui est égal à {b, al) ; 0 un graphe G est composé d'un ensemble S(G) d'éléments appelés sommets et d'une liste A(G) de paires de sommets ; les éléments de A(G) sont appelés arêtes et ne sont pas nécessairement tous distincts ; o le cardinal de S(G) est noté n(G) et on a toujours: S(G) : {O, 1, ..., n(G) -- 1} ; un graphe est donc entièrement décrit par le couple (n(G), A(G)) ; 0 deux sommets s et t de G sont dits voisins si {s, t} est une arête de G ; 0 un même identificateur écrit dans deux polices de caractères différentes désignera la même entité mais du point de vue mathématique pour une police (en italique) et du point de vue informatique pour "l'autre (en romain) ; par exemple, G sera la représentation informatique du graphe G. Une représentation graphique d'un graphe G consiste à associer à chaque sommet de G un cercle contenant le numéro du sommet et à tracer une ligne entre deux cercles représentant des sommets si les sommets correspondants forment une arête de G. Exemple introductif : un graphe (nommé Gex]) et une représentation de Gex] On considère le graphe Gex] dessiné à droite et dont les caractéristiques sont : n(Gex] ) = 5 A(Gex1) : {{O, 4}, {4, 3}, {O, 3},{1, 3}, {O, 3}, {3, 0}}. Il y a trois arêtes entre le sommet O et le sommet 3. Le sommet 0 a pour voisins les sommets 3 et 4. Le sommet 1 a pour voisin le sommet 3. Le sommet 2 n'a pas de voisin. Le sommet 3 a pour voisins les sommets O, 1 et 4. Le sommet 4 a pour voisins les sommets O et 3. Le graphe Gex] Indications pour la programmation Caml : On définit les types Arete et Graphe par : type Arete : {a : int; b : int};; type Graphe : {n : int; A: Arete list};; Ainsi, le graphe Gex] de l'exemple introductif est défini par : letGexl= {n=5; A= [{a=0;b=4}; {a=4; b=3}; {a=0; b=3}; {a=l;b=3}; {a=0;b=3l; {a= ;b=0}l};; Les variables de type Arete ou de type Graphe sont des enregistrements; un enregistrement contient des champs ; par exemple, une variable de type Arete contient les champs a et b. On peut accéder à un champ d'une variable de type enregistrement en faisant suivre le nom de cette variable d'un point puis du nom du champ considéré ; par exemple, on accède au champ n du graphe Gexl par Gexl . n (qui vaut 5). ' Pascal : Dans tout le problème, on supposera qu'on écrit les différentes fonctions dans un fichier contenant les ' définitions suivantes : ' ' ' COHSt MAX_SOMMETS = 100; MAX_ARETES = 1000; type Arete : RECORD a : integer; b : integer; end; type Graphe : RECORD n : integer; nb_aretes : integer; A : array[0..MAX_ARETES -- 1] of Arete; end; type Table : RECORD nb_donnees : integer; cases : array[0..MAX_SQMMETS -- 1] of integer; end; Les types Arete, Graphe et Table sont des types pour des enregistrements (RECORD). Un enregistrement contient des champs (quelquefois aussi appelés des membres); par exemple, une variable de type Arete contient les champs a et b ; on peut accéder à un champ d'une variable de type enregistrement en faisant suivre le nom de cette variable d'un point puis du nom du champ considéré, comme on le voit dans la définition de Gexl ci-dessous. Les variables de type enregistrement se manipulent comme toute autre variable : on peut définir des variables de type enregistrement, on peut affecter à une variable de type enregistrement la valeur d'une autre variable du même type, les variables de type enregistrement peuvent servir de paramètres à des fonctions ou procédures et peuvent être renvoyées par des fonctions ; en revanche, il est interdit de les comparer directement. Ainsi, le graphe Gex] de l'exemple introductif est défini par : Gexl.n := 5; Gexl.nb_aretes := 6; Gexl.A[0].a := O; Gexl.A[0].b : 4; Gexl.A[l].a := 4; Gexl.A[l].b = 3; Gexl.A[2].a ': O; Gexl.A[2].b = 3; Gexl.A[3].a .: l; Gex1.A[3].b ': 3; Gexl.A[4].a := O; Gexl.A[4].b : 3; Gexl.A[5].a :: 3; Gexl.A[5].b : 0; On supposera que les graphes traités n'ont jamais plus de MAX_SOMMETS sommets ou plus de MAX_ARETES arêtes. Remarques importantes (langage Pascal) : lorsqu'on aura affaire à une variable T de type Table, le tableau T . cases servira à contenir un ensemble de données entières et on convient que le champ T . nb_donnees devra toujours indiquer le nombre de données de cet ensemble (et non la longueur totale MAX__SOMOETS du tableau T. cases) ; les données contenues dans T. cases se trouveront donc toujours dans les cases indicées de 0 à T . nb_donnees -- 1. Par ailleurs, pour une variable G de type Graphe correspondant à un graphe G, G.n contiendra le nombre n(G) de sommets de G, G . nb_aretes contiendra le nombre d'arêtes de G et le tableau G . A contiendra les arêtes de G entre les indices 0 et G. nb_aretes --- l. I-- Détermination des voisins des sommets Cl 7-- Il s'agit dans cette question de programmer une fonction qui insère une donnée entière dans une suite triée d' entiers distincts a condition que cette nouvelle donnée ne figure pas déjà dans la suite. Caml . Écrire une fonction insere telle que, si L est une liste d'entiers distincts triée par ordre croissant et s un entier quelconque, insere L s renvoie - la liste d'entiers obtenue en insérant s dans L selon l'ordre croissant si la valeur s ne figurait pas dans L, -- la liste L si s figurait déjà dans L. Pascal : Écrire une fonction insere telle que, lorsque -- T est une variable de type Table telle que T . cases contient T . nb_donnees entiers triés par ordre croissant et -- s est un entier, insere (T, s) renvoie - un résultat de type Table obtenu en insérant s dans T. cases selon l'ordre croissant si la valeur s ne figurait pas dans T . cases (on n'oubliera pas d'actualiser T . nb_donnees), _ -- T si s figurait déjà dans T . cases. E] 8-- On s'intéresse àla complexité de la fonction insere. Caml: Indiquer, en fonction de la longueur de L, la complexité dans le pire des cas de l'algorithme utilisé pour la fonction insere de la question Cl 7. Pascal . Indiquer, en fonction de T . nb_donnees, la complexité dans le pire des cas de l'algorithme utilisé pour la fonction insere de la question [| 7. Cl 9 -- Il s'agit dans cette question d'écrire une fonction qui donne la liste triée des voisins d'un sommet donné dans un graphe donné. Caml : Ecrire en Caml une fonction voisins telle que voisins G s renvoie la liste triée par ordre croissant des voisins du sommets dans le graphe G. On utilisera pour cela la fonction insere. Pascal : Écrire en Pascal une fonction voisins telle que voisins (G, s) renvoie un résultat de type Table dont : -- le champ cases contient les voisins du sommets dans le graphe G triés par ordre croissant, -- le champ nb_donnees contient le nombre de ces voisins. On utilisera pour cela la fonction insere. II -- Un algorithme de bonne coloration d'un graphe On appelle coloration d'un graphe G toute application c de l'ensemble S des sommets de G dans l'ensemble des entiers naturels non nuls. Pour tout sommet s, l'entier c(s) s'appelle couleur des pour la coloration c. Une coloration c est une bonne coloration de G si pour toute arête {s, t} de G, on a c(s) # c(t) ; autrement dit, une coloration est une bonne coloration si les extrémités de toute arête sont de couleurs différentes. On considère l'algorithme de bonne coloration suivant. Les couleurs disponibles sont les entiers naturels non nuls ; la plus petite couleur est ainsi la couleur 1. On colorie les sommets les uns après les autres, dans l'ordre 0, 1, 2 n(G) ---- 1 ; lorsqu'on considère un sommet s, on lui attribue la plus petite couleur disponible, c'est-à--dire la plus petite couleur qui n'est pas déjà la couleur d'un voisin de s. D 10 -- Que donne cet algorithme pour le graphe ° ° Gex2 ci--contre ? Y a--t--il une autre bonnecoloration \ de G utilisant moins de couleurs ? Le graphe Gex2 D 11 -- Il s'agit d'écrire en langage de programmation l'algorithme de bonne coloration décrit plus haut. Pour déterminer cette bonne coloration, on utilisera n( G) cases à valeurs entières d'un tableau dont les indices O, 1, ..., n(G) -- 1 correspondront aux sommets de G; la case d'indice : contiendra après le déroulement de l'algorithme la.couleur du sommets. Caml : Écrire en Caml une fonction coloration telle que coloration G renvoie le tableau des couleurs attribuées aux sommets du graphe G par l'algorithme décrit ci-dessus. Pascal : On définit pour cette question un nouveau type par : type Couleurs : array[0..MAX_SOMMETS -- 1] of integer; Ecrire en Pascal une fonction coloration telle que coloration (G) renvoie le tableau des couleurs attribuées aux sommets du graphe G par l'algorithme décrit ci-dessus ; le résultat retourné par la fonction coloration sera de type Couleurs. III --- Définition du nombre chromatique de G Soit G un graphe et p un entier strictement positif. On appelle bonne p-coloration de G une bonne coloration n'utilisant que des couleurs appartenant à l'ensemble { l, p}. On introduit les notations suivantes : . BC(G, p) est l'ensemble des bonnes p-colorations de G ; . fc(G, p) est le cardinal de BC(G, p) ; - EC(G) = {p e N" tel que fc(G, p) == 0}. D 12 ---- Montrer l'existence d'un unique entier nbc(G) tel que : EC(G) : {p e N" tel que p 2 nbc(G)}. On dit que nbc(G) est le nombre chromatique du graphe G : c'est le nombre minimum de couleurs permettant de colorier les sommets de G de sorte que deux sommets voisins n'aient pas la même couleur. D 13 -- Soit G un graphe n'ayant aucune arête. Déterminer nbc(G) en fonction de n(G) et, pour tout p e IN", déterminer fc(G, p) en fonction de n(G) et p. ' D 14 -- Soit G un graphe tel que toute paire de sommets soit une arête. Déterminer nbc(G) en fonction de n(G) et, pour tout p e N', déterminer fc(G, p) en fonction de n(G) et p. 13 15 ---'On considère le graphe Gex] de l'exemple introductif. Déterminer nbc(Gexl ) et, pour tout p e N", déterminer fc(Gexl, p) en fonction de p. IV -- Les applications H et K On dit qu'un sommet d'un graphe est isolé s'il n'a aucun voisin. Par exemple, le sommet 2 est isolé dans le graphe Gex] . D 16 -- Étant donnés un graphe G et un sommet de G non isolé s, on note prem_voisin(G, s) le plus petit voisin de s dans G, c'est--à--dire le voisin de s qui a le plus petit numéro. Par exemple, prem_voisin(Gexl , O) est le sommet 3. Caml: Ecrire en Caml une fonction prem_voisin telle que prem_voisin G 5 renvoie prem_voisin(G, s). Cette fonction ne prévoira pas le cas où s est un sommet isolé de G. Pascal : Ecrire en Pascal une fonction prem_voisin telle que prem_voisin (G , s) renvoie prem_voisin(G, s). Cette fonction ne prévoira pas le cas où s est un sommet isolé de G. D 17 -- On considère un graphe G possédant au moins une arête. On note prem_ni(G) le plus petit sommet non isolé du graphe G, c'est--à--dire le sommet non isolé qui a le plus petit numéro. Par exemple, prem_ni(Gexl ) est le sommet O. Caml : Écrire une fonction prem_ni telle que prem_ni G renvoie prem_ni(G). Cette fonction ne prévoira pas le cas où G ne possède aucune arête. Pascal : Ecrire une fonction prem_ni telle que prem_ni (G) renvoie prem_ni(G). Cette fonction ne prévoira pas le cas où G ne possède aucune arête. Cl 18 -- Rappelons d'abord que dans la liste A(G) des arêtes d'un graphe G, il est possible qu'une même arête soit répétée. , Etant donné un graphe G possédant au moins une arête, on pose : sl : prem_ni(G) sz : prem_vaisin(G, prem_ni(G)). Par exemple, pour le graphe Gex] , s1 = 0 et s2 =" 3. On note H(G) le graphe obtenu à partir de G en supprimant toutes les arêtes entre 81 et 512. Par exemple, le graphe H(Gexl ), représenté ci--contre, est caractérisé par : n(H(Gexl )) = 5, A(H(Gexl)) : {{O, 4}, {4, 3}, {l, 3}}. Le graphe H(Gexl ) Caml : Écrire en Caml une fonction H telle que H G renvoie H(G) (qui sera de type Graphe). Cette fonction ne prévoira pas le cas où G ne possède aucune arête. Pascal : Écrire en Pascal une fonction H telle que H (G) renvoie H(G) (qui sera de type Graphe). Cette fonction ne prévoira pas le cas où G ne possède aucune arête. CI 19 -- On considère un graphe G possédant au moins une arête. On définit SI et sz comme dans la question précédente ; on peut remarquer la relation : sz > 51- On construit alors un graphe noté K(G) de la façon décrite ci-- dessous. 0 On construit H(G) ; 0 dans H(G), on superpose sl et s; ; plus précisément, -- on considère successivement chaque arête de la liste des arêtes de H(G) ; pour chacune d'entre elles, on renumérote ses extrémités : -- une extrémité de valeur strictement inférieure à s2 est inchangée ; -- une extrémité de valeur 52 prend la valeur sl ; - une extrémité de valeur strictement supérieure à s2 est décrémentée de 1 ; --- on diminue de 1 le nombre de sommets du graphe. Par exemple, K(Gexl ), représenté ci- ° contre, est décrit par : n(K(Gexl )) = 4, A(K(Gexl)) : {{O, 3}, {3, 0},{1, 0}}. ' @ Le graphe K(Gex1 ) ' Caml : Écrire en Caml une fonction K telle que K G renvoie K(G) (le résultat sera de type Graphe). Cette fonction ne prévoira pas le cas où G ne possède aucune arête. Pascal : Écrire en Pascal une fonction K telle que K (G) renvoie K(G) (le résultat sera de type Graphe). Cette fonction ne préVoira pas le cas où G ne possède aucune arête. V ---- Fonction fc(G, p) et polynôme chromatique Soit G un graphe possédant au moins une arête et soit p un entier non nul. D 20 -- Montrer l'inclusion : BC(G, p) c: BC(H(G), p). E] 21 -- Comparer les cardinaux de BC(K(G), p) et de BC(H(G), p) \ BC(G, p). D 22 -- Montrer l'égalité : fc(G, p) =fc(H(G), p) --fc(K(G), p). E] 23 -- En utilisant la formule obtenue dans la question D 22, décrire en termes simples un algorithme récursif _ de calcul de fc(G, p) ; ici, on ne demande pas d'utiliser un langage de programmation. D 24 -- Prouver que l'algorithme de la question [3 23 se termine. [] 25 -- Le graphe G étant fixé, montrer que la fonction qui associe à p la quantité fc(G, p) est la restriction à N' d'un polynôme en p de degré n(G). On appelle polynôme chromatique de G et on note Pc(G) ce polynôme. VI ---- Calcul du polynôme Pc(G, p) et de nbc(G) On ne considérera dans cette partie que des polynômes à une variable et à coefficients entiers. Caml : Un polynôme de degré d est représenté par un tableau à (d + 1) cases, la case d'indice i contenant le coefficient du monôme de degré 1". On pourra, pour connaître le degré d'un polynôme, utiliser la fonction de Caml vect_length qui, lorsqu'on invoque vect_length T, où T est un tableau, retourne le nombre de cases de ce tableau. Pascal : On définit pour cette dernière partie un nouveau type par : type Polynome : RECORD degre : integer; coeff : array[0..MAX_SOMMETS] of integer; end; On utilisera ce type pour représenter un polynôme dont le degré ne dépasse pas MAX_SOMMETS Le champ degre contiendra le degré du polynôme et, pour i S degre, coeff [i] contiendra le coefficient du monôme de degré i. E] 26 -- Dans cette question, on va s'intéresser à la différence de deux polynômes. On ne traitera pas le cas où simultanément les deux polynômes auraient même degré et même coefficient du monôme de plus haut degré. Caml : Écrire en Caml une fonction difference telle que, lorsque P et Q sont deux variables représentant des polynômes P et Q, difference P Q renvoie le polynôme P ---- Q représenté par un tableau d'entiers comme indiqué dans l'introduction de cette partie. Pascal : Écrire en Pascal une fonction difference telle que, lorsque P et Q sont deux variables de type Po lynome représentant des polynômes P et Q, di f ference (P , Q) renvoie le polynôme P --- Q, qui sera de type Po lynome. Cl 27 -- Cette question consiste à calculer le polynôme chromatique Pc(G). Caml : Écrire en Caml une fonction Pc telle que Pc G renvoie le polynôme Pc(G) représenté par le tableau de ses coefficients comme indiqué au début de cette partie. Pascal : Écrire en Pascal une fonction Pc telle que Pc (G) renvoie le polynôme Pc(G) sous la forme d'une variable de type Polynome. D 28 -- Dans cette question, il s'agit de calculer la valeur P(x) d'un polynôme P en une valeur entière x. On n'utilisera pas de fonction prédéfinie du langage qui calculerait les puissances d'un entier. Les calculs seront faits avec les quatre opérations arithmétiques ordinaires. De plus, la complexité de l'algorithme utilisé sera nécessairement du même ordre de grandeur que le degré du polynôme considéré. Caml : Écrire en Caml une fonction eval telle que eval P x renvoie P(x). Pascal : Ecrire en Pascal une fonction eval telle que eval (P , x) , où P est de type Po lynome et x de type integer, renvoie P(x). D 29 -- Écrire dans le langage de programmation choisi une fonction qui calcule le nombre chromatique nbc(G) d'un graphe G.

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Mines Informatique MP 2003 -- Corrigé Ce corrigé est proposé par Samuel Mimram (ENS Lyon) ; il a été relu par JeanBaptiste Rouquier (ENS Lyon) et Vincent Puyhaubert (ENS Cachan). Le sujet est constitué de deux problèmes indépendants. Le premier problème traite de la logique booléenne et d'une extension tri-valuée de cette logique. Il est relativement facile et ne requiert que des connaissances de première année : il est principalement fondé sur l'utilisation de tables de vérité et sur la notion d'équivalence entre propositions (deux propositions sont équivalentes si elles ont la même table de vérité). Le second problème aborde plusieurs aspects de la coloration des graphes, qui est un problème classique d'algorithmique. Il comporte un certain nombre de questions de programmation et des questions théoriques visant à faire manipuler les graphes. En plus de la définition d'un graphe, les notions de nombre chromatique (le plus petit nombre de couleurs nécessaires pour colorier un graphe) et de polynôme chromatique d'un graphe sont introduites. Un algorithme naïf de coloration est proposé ainsi que des transformations sur les graphes, qui permettent de trouver des algorithmes calculant le polynôme et le nombre chromatique d'un graphe quelconque. Ce sujet permet de réviser la logique booléene et constitue un bon exercice d'algorithmique permettant de voir (ou de revoir) et d'utiliser des fonctions avancées de Caml Light. Indications 1. Logique propositionnelle tri-valuée 1 Utiliser l'identité : ¬(x y) ¬x ¬y. 5 Formuler le raisonnement par contraposition en termes de propositions logiques. 6 Raisonner sur les tables de vérité et montrer que le problème se ramène à ne trouver les valeurs que de quelques cases de la table de vérité du connecteur . 2. Coloration d'un graphe 9 Parcourir pour tout sommet s la liste des arêtes. Pour toute arête de la forme (s, b) rajouter l'élément b dans une liste initialement vide. 10 Remarquer que deux sommets de même parité ne sont pas voisins pour trouver une meilleure coloration que celle donnée par l'algorithme. 11 Colorier au fur et à mesure les sommets, de 0 jusqu'à n - 1. À chaque étape, calculer dans une variable auxiliaire la liste triée des couleurs déja utilisées par les voisins du sommet à colorier. 12 Montrer que EC(G) est non vide, puis que : p EC(G) q N q > p = q EC(G) 14 Montrer qu'une coloration du graphe est bonne si et seulement si les couleurs des sommets sont deux à deux distinctes. 15 Considérer le triangle formé par les sommets 0, 3 et 4, puis le sommet 1, puis le sommet 2. 17 prem_ni(G) est le minimum des sommets qui sont extrémité d'une arête. 18 Écrire une fonction qui, à une liste d'arêtes l et deux sommets s1 et s2 , enlève toutes les arêtes de l reliant les sommets s1 et s2 . 19 Utiliser la fonction map de Caml pour renommer les sommets de la liste d'arêtes de H(G). 20 Montrer que deux sommets voisins dans H(G) le sont aussi dans G. 21 Montrer que les colorations c de BC(H(G), p) r BC(G, p) sont les bonnes colorations de H(G) vérifiant c(s1 ) = c(s2 ). 22 Utiliser les deux questions précédentes. 24 Raisonner par récurrence sur le nombre d'arêtes des graphes. 25 Raisonner de même qu'à la question 24. 27 S'inspirer de l'algorithme de la question 23. 28 Utiliser la relation de récurrence xi+1 = xi × x (avec x0 = 1). 29 Écrire un programme qui trouve le plus petit entier i tel que Pc(G)(i) 6= 0. 1. Logique propositionnelle tri-valuée 1 On sait d'après les lois de De Morgan que ¬(x y) ¬x ¬y et que ¬¬x x (on note l'équivalence entre propositions). On en déduit : ¬(¬x ¬y) (¬¬x) (¬¬y) x y La proposition P1 = ¬(¬x ¬y) convient. Montrons que les propositions « ¬(¬x¬y) » et « xy » sont équivalentes dans L3 . On constate sur les tables de vérité que L3 est une extension de L2 (les restrictions des tables de vérité de L3 aux valeurs V et F donnent les tables de vérité de L2 ). En outre, le connecteur est commutatif dans L3 car sa table de vérité est symétrique. Pour montrer que les propositions « ¬(¬x ¬y) » et « x y » sont équivalentes, il suffit donc de montrer qu'elles ont les mêmes valeurs pour (x, y) {(V, I); (F, I); (I, I)}. Et en effet, on a bien : ¬(¬V ¬I) = ¬(F I) = ¬F = V = V I ¬(¬F ¬I) = ¬(V I) = ¬I = I = F I ¬(¬I ¬I) = ¬(I I) = ¬I = I = I I Les propositions « x y » et P1 = ¬(¬x ¬y) sont équivalentes dans L3 . On pouvait aussi se contenter de calculer entièrement la table de vérité de « ¬(¬x ¬y) » dans L3 et constater qu'elle est identique à celle de « x y ». Cependant, il vaut souvent mieux ­ surtout dans une épreuve de trois heures ­ s'arrêter pour réfléchir quelques minutes que se lancer dans des calculs longs, fastidieux et sources d'erreurs. 2 En comparant les tables de vérité, on vérifie aisément qu'en logique propositionnelle classique, on a : x y ¬x y. La proposition P2 = ¬x y convient. Dans la logique L3 , avec x = y = I, on a : (¬I I) = I 6= V = (I I) Ces propositions ne sont plus équivalentes dans L3 . 3 Notons P la proposition « x y » et Q la propostition « (¬x) y ». La proposition P3 = « ((x y) ((¬x) y)) y » s'écrit alors « (P Q) y ». Calculons sa table de vérité dans L3 : x V V V F F F I I I y V F I V F I V F I P V F I V V V V I V Q V V V V F I V I V (P Q) V F I V F I V I V P3 V V V V V V V I I Cette proposition n'est pas une tautologie dans la logique L3 car il existe des valuations de x et y pour lesquelles elle ne s'évalue pas à « vrai ». 4 Établissons une forme normale disjonctive de la proposition « (x y) z » dans L2 . D'après les questions 1 et 2, on a : (x y) z ¬(¬x ¬y) z ¬¬(¬x ¬y) z (x y) z (¬x ¬y) z La proposition P4 = « (¬x ¬y) z » convient. Les propositions P4 et « (x y) z » ne sont pas équivalentes dans L3 car on a par exemple, avec x = F, y = I et z = I : ((¬F ¬I) I) = ((V I) I) = (I I) = I et ((F I) I) = (I I) = V 5 La justification de la validité du raisonnement par contraposition en logique classique est l'équivalence des propositions « ¬y ¬x » et « x y ». Si l'on construit la table de vérité dans L3 de la proposition « ¬y ¬x », on constate qu'elle est identique à celle de l'implication. Le raisonnement par contraposition est donc encore valide dans L3 . 6 Déterminons le nombre de logiques L possibles vérifiant : 1. L est une extension de L2 pour ¬, , et ; 2. est commutatif ; 3. x y P1 ; 4. x y P2 ; 5. pour toute valeur de y, la fonction x 7 x y croît au sens large ; 6. ¬(¬x) x. Il n'y a pas unicité des propositions P1 et P2 , solutions des questions 1 et 2 (la proposition P2 = « ¬x ¬¬y » convenait aussi, par exemple). Cependant, la démonstration qui suit est indépendante des propositions choisies.