Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

CCENS 1999 mathematiques classe prepa b/l

5 pages
ENSSESSION DE 1999COMPOSITION DE MATHEMATIQUESSujet commun : ENS Ulm-Cachan-FontenayDurØe : 4 heuresL ØnoncØ comporte 5 pagesCalculatrice autorisØe1/56666PROBLEMEILes trois parties peuvent Œtre traitØes indØpendamment.NOTATIONSETDEFINITIONSOn dØ…nit un graphe …ni G comme la donnØe d un couple (S;A) oø S est un ensemble …ni appelØ ensemble dessommets du graphe, et A une partie de l ensemble(2)S =f(s;t) = s2S; t2S; s =tgdes paires de sommets de S: L ensemble A est appelØ ensemble des arŒtes du graphe G:Par exemple, si G = (S;A) oø S = fa;b;c;d;eg et A = ffa;bg;fb;cg;fc;dg;fd;ag;fc;egg; alors G est le graphedont les sommets sont a;b;c;d;e et pour lequel il existe une arŒte entre a et b; b et c; c et d; d et a; c et e àl exclusion de toute autre. On pourra reprØsenter ce graphe par le schØma :Lorsque A = ;; on dit que le grapheFigure 1: ReprØsentation du graphe G(2)n a pas d’arŒtes et lorsque A =S ; on dit que G est un graphe complet.On appelle coloriage de G à k couleurs, k 2N ; toute application c : S 7!f1;::;kg (on suppose que l on disposede k couleurs di⁄Ørentes numØrotØes de 1 à k pour colorier les sommets du graphe et que c(s) donne le numØro dela couleur du sommet s): On dit que c est un coloriage propre si deux sommets reliØs par une arŒte n ont pas lamŒme couleur, c est- -dire si pour tous s et t dans S; c(s) =c(t) lorsque fs;tg2A:On notera P (k) le nombre de coloriage propres distincts à k couleurs de G et l’on appelera nombre ...
Voir plus Voir moins
ENS
SESSION DE 1999
COMPOSITIONDEMATHEMATIQUES
Sujet commun :ENS Ulm-Cachan-Fontenay
Durée :4 heures
Lénoncé comporte 5 pages
Calculatrice autorisée
1/5
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin