Remerciez-le!

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

Licence Sciences et Techniques (LST) MATHEMATIQUES ET APPLICATIONS MEMOIRE DE F

Licence Sciences et Techniques (LST) MATHEMATIQUES ET APPLICATIONS MEMOIRE DE FIN D’ETUDES Pour l’obtention du Diplôme de Licence Sciences et Techniques T Ti it tr re e Application de la coloration des graphes aux problèmes de coloration des cartes géographiques et gestion des examens Présenté par : Outmane Abdelmoughit Encadré par : Pr. El Hilali Alaoui Ahmed Pr. Kadri Nasser Soutenu Le 09 Juin 2016 devant le jury composé de: - - P Pr r. . K Ka ad dr ri i N Na as ss se er r (FSTF) - - P Pr r. . E El l H Hi il la al li i A Al la ao ou ui i A Ah hm me ed d ( (F FS ST TF F) ) - P Pr r. . F Fi ik kr ri i M Ma aj jd da a ( (E EN NC CG G d d’ ’A Ag ga ad di ir r) ) - Pr. E El l H Ha as ss sa an ni ia a M Me es ss sa ao ou ud d (Université privée de Fès) Stage effectué à FSTF Année Universitaire 2015 / 2016 UNIVERSITE SIDI MOHAMED BEN ABDELLAH FACULTE DES SCIENCES ET TECHNIQUES Département des Mathématiques FACULTE DES SCIENCES ET TECHNIQUES FES – SAISS  B.P. 2202 – Route d’Imouzzer – FES  212 (0)5 35 61 16 86 – Fax : 212 (0)5 35 60 82 14 Site web : http://www.fst-usmba.ac.ma 1 A mes très chers parents, Aucun mot ne pourra exprimer mon amour envers vous. A mes frères, Je vous remercie pour votre amour inconditionnel. A tous mes collègues de la FST Merci pour ces trois ans inoubliables Pour tout le soutien que vous m’avez offert, vous occuperez pour toujours une partie dans mon cœur. 2 Je tiens tout d’abord à remercier Dieu le tout puissant et miséricordieux, qui m’a donné la force et la patience d’accomplir ce modeste travail. En second lieu, je tiens à remercier mes encadrants Mr. Le professeur El Hilali Alaoui Ahmed, et Mr. Le professeur Kadri Nasser, pour leurs précieux conseils et leurs aides durant toute la période du projet. Mes vifs remerciements vont également aux membres du jury Mme. Le Professeur Fikri Majda et Mme. LE Professeur El Hassania Messaoud pour l’intérêt qu’ils ont porté à ce projet en acceptant de l’examiner et de l’enrichir par leurs propositions. Je passe aussi mes remerciements à monsieur Mustapha Sebaaoui, responsable du service scolarité. Enfin, je tiens également à remercier toutes les personnes qui ont participé de près ou de loin à la réalisation de ce travail. Merci…………. 3 Table de matières Introduction ……………………………………………………………………..5 Chapitre 1 : Rappel sur les graphes ………………………………….6 I. Première notions …………………………………………………………………..6 1. Définition d’un graphe ………………………………………………………………….6 2. Graphe simple ……………………………………………………………………………....7 3. Degré d’un sommet ……………………………………………………………………....8 4. Graphe orienté ……………………………………………………………………………..8 5. Graphe non orienté ……………………………………………………………………….8 II. Graphe planaire …………………………………………………………………...9 1. Définition ……………………………………………………………………………………..9 2. Exemple …………………………………………………………………………………….....9 3. Vocabulaire ………………………………………………………………………………...11 III. Matrice associée à un graphe ……………………………………………....12 1. Matrice d’incidence sommet-arc ………………………………………………….12 2. Matrice d’incidence sommet-sommet …………………………………………..13 Chapitre 2 : Coloration des graphes ……………………………….15 I. Coloration des sommets d’un graphe ……………………………………15 1. Définition …………………………………………………………………………………...15 2. Ensemble stable …………………………………………………………………………15 3. Nombre chromatique …………………………………………………………………15 4. Domaines d’applications …………………………………………………………….16 5. Algorithme de Welsh et Powell …………………………………………………...16  Sur les graphes ………………………………………………………………...16  Sur la matrice d’adjacence d’un graphe ……………………………..18 4 II. Coloration des arêtes d’un graphe ……………………………………….21 1. Définition …………………………………………………………………………………...21 2. L’indice chromatique d’un graphe …………………………………………….....21 3. L’algorithme de welsh-powell ……………………………………………………..21 Chapitre 3 : Coloration des cartes géographiques ………...24 I. Définition ………………………………………………………………………......24 II. Théorème des quatre couleurs ……………………………………………24 1. Enonce du théorème …………………………………………………………………...24 2. Historique ………………………………………………………………………………….24 III. Exemple : coloration de la carte d’Ouazzane ………………….......26 Chapitre 4 : Gestion des examens ………………………………….33 I. Introduction ………………………………………………………………….......33 II. Méthodes d’initialisation ……………………………………………….......34 III. Exemple : Organisation des examens de la session du printemps à la FST de Fès………………………………………………35 5 Introduction On peut dire que les premiers développements majeurs de la théorie des graphes datent du milieu du vingtième siècle. Ainsi, un des premiers ouvrages si ce n’est pas le premier, traitant de théorie des graphes «théorie der endlichen und unendlichen graphen» écrit par Konig remonte à 1936. Depuis cette époque, la théorie des graphes s’est largement développée et fait à présent partie du cursus standard en mathématiques de bon nombre d’universités. Ce projet concerne une partie de la théorie des graphes (principalement la coloration des graphes), et j’ai essayé dans ce travail d’appliquer cette théorie aux problèmes de coloration des cartes géographiques et gestion des examens. Pour réaliser cela, Je commence par un premier chapitre ‘’Rappel sur les graphes’’ qui contient les principales notions que l’on peut utiliser par la suite. Puis un deuxième chapitre très important ‘’La coloration des graphes‘’, je vais étudier la coloration des sommets et des arêtes d’un graphe par l’algorithme de Welsh-Powell.gffgfgfgfgfgfgfgfgfgfgfgfgfgfgfgfgfgfgfgffgfgfgfgfgfgfgfgfgfgfgg Les deux chapitres 3 et 4 ‘’La colorations des cartes géographiques ‘’ & ‘’Gestion des examens ‘’ sont des applications de la coloration des graphes, dans le chapitre 3 je vais traduire les étapes de l’algorithme de Welsh-Powell en langage C, et appliquer ce programme aux deux exemples : la coloration de la carte d’Ouzzane et l’organisation des examens de la session du printemps à la FSTF. 6 Chapitre 1 : Rappel sur les graphes I. Première notions 1. Définition d’un graphe On appelle un graphe un couple G=(X;U) tel que : - X un ensemble d’élément appelés sommets (nœuds) du graphe - U une famille d’éléments du produit cartésien X × X appelés arcs du graphe S’il est orienté, sinon on les appelle arêtes. Exemple 1: Un exemple de graphe à 8 sommets, nommés de a à h, comportant 10 arêtes. On note le graphe par G=(X ;U) L’ensemble des sommets est X= {a , b, c, d ,e, f, g, h } Et l’ensemble des arêtes U={ (a,d),(b,c), (b,d),(d,e), (e,c),(e,h), (h,d),(f,g), (d,g),(g,h) }  Deux sommets x et y sont adjacents si il existe l'arête (x,y) dans U. Les sommets x et y sont alors dits voisins. Par exemple a et d sont adjacents car (a,d) є U ,mais a et b ne sont pas adjacents car (a,b) ɇ U.  Une arête est incidente à un sommet x si x est l'une de ses extrémités. Par exemple (a,d) est incident à d. 7  On appelle ordre du graphe G=(X,U) le nombre de sommets du graphe ; L'ordre de G est donc le cardinal de X et noté |X|.  Les graphes sont utilisés dans de nombreux domaines. On peut donner quelques exemples :  les réseaux de communication : réseaux de routes représentés par une carte routière, réseaux de chemin de fer, de téléphone, de relais de télévision, réseaux électriques, réseaux des informations dans une organisation, etc... ;  l'étude des circuits électriques : Kirchhof, qui a étudié les réseaux électriques, peut être considéré comme un des précurseurs de cette théorie ;  la chimie, la sociologie et l'économie : la notion de clique est un exemple de l'implication de la théorie des graphes dans ces disciplines. 2. Graphe simple Un graphe G=(X ,U) est dit simple (ou strict) s’il ne s’agit pas d’un multi- graphe et si U est irréflexif , c’est-à-dire que quel que soit v є X , (v,v)ɇU (i.e.G ne contient pas de boucle) . Exemple 2 : Graphe simple NB : un multi-graphe G=(X,U) est un graphe pour lequel l’ensemble U des arcs est un multi-ensemble. Autrement dit, il peut exister plus d’un arc reliant deux sommets donnés. Par exemple le graphe suivant est un multi-graphe 8 Multi-graphe 3. Degré d’un sommet Le degré d'un sommet x de G est le nombre d'arêtes incidentes à x. Il est noté d(x).Pour un graphe simple le degré de x correspond également au nombre de sommets adjacents à x.  Dans l’exemple 1 : d(g)=3 car on a trois arêtes incidentes a g qui sont : (f,g) , (h,g) et (d,g). Remarque : Pour un graphe simple d'ordre n, le degré d'un sommet est un entier compris entre 0 et n-1. Un sommet de degré 0 est dit isolé : il n'est relié à aucun autre sommet. 4. Graphe orienté Soit G=(X,U) un graphe(resp. multi-graphe ), on dit que G est orienté si les couples (ui,uj) sont orientés, c’est-à-dire (ui,uj) est un couple ordonné, ou ui est le sommet initial, et uj le sommet terminal (ui le prédécesseur de uj, et uj le successeur de ui ). Le couple (ui,uj) est appelé un arc, est représenté graphiquement par ui uj. Le graphe de l’exemple 2 est un graphe orienté. 5. Graphe non orienté soit G=(X,U) un graphe (resp. multi-graphe ) si U est une relation symétrique sur X, on dira que G est un graphe (resp. multi-graphe ) non orienté. Autrement dit G est non orienté si : ∀ u1, u2 є U : (u1,u2)є U => (u2,u1) є U 9 Le graphe de l’exemple 1 est un graphe non orienté Les graphes non orientés sont en fait un cas particulier de graphes (orientés) uploads/Geographie/ application-de-la-coloration-d-outmane-abdelmoughit-3206.pdf