Introduction à la théorie des graphes - Apprendre en ligne

1 CAHIERS DE LACRMI ntroduction lath orie des graphesDidier M llerCAHIER NO6 COMMISSIONROMANDE DEMATH MATIQUET able des mati resAvant-propos1 But de ce fascicule ..1 Corrig s des exercices ..2 Logiciels pour les graphes ..2 Pour aller plus loin ..21 graphes non orient res d finitions .. sentation graphique .. types de graphes .. d utilisation d un graphe pour r soudre un probl me .. d intervalles .. partiel et sous- graphe .. s .. d un sommet .. d un graphe .. nes et cycles .. eul riens .. hamiltoniens .. d un couplage maximum .. planaires .. sentations non graphiques d un graphe .. d adjacences .. d adjacences .. Arbres .. Codage de Pr fer .. Arbres couvrants .. Arbre couvrant de poids minimum .. Coloration.

2 Encadrement du nombre chromatique .. Algorithme de coloration de Welsh et Powell .. graphes parfaits .. Coloration des sommets d un graphe planaire .. Coloration des ar tes d un graphe .. graphes triangul s ..262 graphes orient orient s .. d un sommet d un digraphe .. et circuits .. fortement connexe .. sentations non graphiques des digraphes .. d adjacences .. d adjacences .. sans circuit .. de comparabilit ..34 CAHIERS DE LACRMNo6 de Dijkstra .. seau PERT (Project Evaluation and Review Technique) ..37 Bibliographie40 Lexique41 Index46ii No6 CAHIERS DE LACRMA vant-proposLa mise en oeuvre du RRM a n cessit certains ajustements des programmes de math ma-tiques enseign s dans les gymnases de Suisse romande. La Commission Romande de Ma-th matique (CRM) tient proposer des moyens d enseignement conformes aux exigencesdu r glement de maturit.

3 Aussi ses membres s emploient-ils depuis plusieurs ann es lamise jour de sa collection Ouvrages collectifs qui couvrent en priorit les besoins duprogramme de niveau notions g n ralement tudi es dans les cours de math matiques de niveau ren-forc ont t volontairement retir es des ouvrages de outre, l Introduction desoptions sp cifiques a ouvert de nouveaux horizons quant aux sujets de math matiquesabord s. Soucieuse de tenir compte de cette volution, la CRM proposait en 2004 les deuxpremiers ouvrages d une nouvelle collection, les Cahiers dela cahier, le sixi me de la s rie, parle des graphes , un sujet inhabituel dans les cours tra-ditionnels de math matiques et qui s int gre parfaitementbien dans une Option Sp cifiqueou dans une Option Compl CRM est heureuse de pr senter aujourd hui un ouvrage sortant des sentiers battus : Introduction la th orie des graphes de Didier M llerLes ouvrages publi s ces derni res ann es par la CRM sont marqu s par le souci d tre ac-cessibles la lecture individuelle des l ves.

4 J esp re qu il en ira de m me pour cet ouvrageet que vous aurez grand plaisir vous plonger dans ce monde fascinant des mes remerciements Didier M ller pour s tre lanc dans l aventure de la publicationd un cahier, ainsi qu aux membres de la CRM qui ont consacr de leur temps une lecturefinale HochuliPr sident de la CRMD cembre 2011 But de ce fasciculeLe but de ce fascicule est d initier les lyc ens la th orie des n ai pas pour ambition de faire une th orie compl te, maisde montrer comment lesgraphes peuvent tre une m thode de r solution de probl mesint cours se veut accessible aux l ves de lyc e, car il ne demande pratiquement pas deconnaissances pr alables. Il est d coup en deux parties principales : les graphes non orien-t s et les graphes orient la th orie des graphes utilise un jargon bien particulier, le d but du cours comportebeaucoup de d finitions.

5 C est un peu r barbatif, mais indispensable pour la suite. Un indexet un lexique en fin de fascicule aideront l l ve assimilerces exercices sont essentiellement de deux types : Des exercices th oriques sur les graphes , qui sont souventdes d monstrations assezsimples, g n ralement par induction, ou par l absurde ; il ya aussi des exercices der flexion qui permettent de se rendre compte si on a bien compris un concept ou non. Des exercices pratiques o il peut tre avantageux d utiliser des graphes pour mod liseret r soudre un probl DE LACRMNo6 1 Corrig s des exercicesPar manque de place dans ce fascicule, les corrig s des exercices sont disponibles gratuite-ment sur le site L internautetrouvera galement sur ce sitequelques applets pour illustrer certains pour les graphesLe logiciel gratuitGrin (pour Windows) permet entre autres de : dessiner des graphes produire la matrice d adjacences d apr s le dessin colorer des graphes trouver le plus court chemin dans un graphe trouver les cycles eul riens et hamiltoniensBref, ce logiciel est un compl ment id al ce cours !

6 Il a t crit par VitaliPetchenkineetest disponible l adresse web : (la page officiellede ce programme a disparu du web).Mathematicapermet aussi de travailler avec les graphes . Voir [5] dans aller plus loinPour en savoir beaucoup plus sur les graphes , voici quelqueslivres que j ai utilis s, class sdu plus simple au plus complet : Alain Hertz propose une initiation aux graphes sous forme d nigmes polici res [3]. Celaillustre bien comment les graphes peuvent tre utiles pour mod liser des probl mes. Th orie des graphes [1] donne une base solide, tout en restant accessible au plusgrandnombre. Tr s agr able lire. Un regret : pas d exercices. Les graphes par l exemple[2] est comme [1] accessible des lyc ens, mais il contienten plus des exercices corrig s. Introduction to graph theory[6] est tr s complet, mais d un niveau universitaire et enanglais.

7 graphes et algorithmes[4] est un ind modable, de niveau universitaire et malheureuse-ment tr s M ller2 No6 CAHIERS DE LACRM1 graphes non orient Premi res d finitionsUngraphefiniG=(V,E)est d fini par l ensemble finiV={v1,v2,..,vn}dont les l -ments sont appel ssommets(Verticesen anglais), et par l ensemble finiE={e1,e2,..,em}dont les l ments sont appel sar tes(Edgesen anglais).Une ar teede l ensembleEest d finie par une paire non ordonn e de sommets, appel sles extr mit s dee. Si l ar teerelie les sommetsaetb, on dira que ces sommets sontadjacents, ouincidentsavece, ou bien que l ar teeest incidente avec les appelleordred un graphe le nombre de sommetsnde ce sentation graphiqueLes graphes tirent leur nom du fait qu on peut les repr senter par des dessins. chaquesommet deG, on fait correspondre un point distinct du plan et on relie les points corres-pondant aux extr mit s de chaque ar te.

8 Il existe donc une infinit de repr sentations d ungraphe. Les ar tes ne sont pas forc ment on peut dessiner un grapheGdans le plan sans qu aucune ar te n en coupe une autre (lesar tes ne sont pas forc ment rectilignes), on dit queGestplanaire. Le grapheGci-dessusest repr sentation non planaire dugrapheG(des ar tes se croisent)15432 Une repr sentation planaire types de graphesUn graphe estsimplesi au plus une ar te relie deux sommets et s il n y a pas de boucle surun sommet. On peut imaginer des graphes avec une ar te qui relie un sommet lui-m me(une boucle), ou plusieurs ar tes reliant les deux m mes sommets. On appelera ces DE LACRMNo6 3Un graphe estconnexes il est possible, partir de n importe quel sommet, de rejoindretous les autres en suivant les ar tes. Un graphe non connexe se d compose encomposantesconnexes.

9 Sur le graphe ci-dessous, les composantes connexes sont{1,2,3,4}et{5,6}.213645 graphe non connexeV={1,2,3,4,5,6}E= {1,3},{1,4},{2,3},{3,4},{5,6} Un graphe estcompletsi chaque sommet du graphe est reli directement tous les completK5V={1,2,3,4,5}E= {1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5 },{3,4},{3,5},{4,5} Un graphe estbipartisi ses sommets peuvent tre divis s en deux ensemblesXetY,de sorte que toutes les ar tes du graphe relient un sommet dansX un sommet dansY(dans l exemple ci-dessous, on aX={1,3,5}etY={2,4}, ou vice versa).12345 graphe bipartiV={1,2,3,4,5}E= {1,2},{1,4},{2,5},{3,4},{4,5} d utilisation d un graphe pour r soudre un probl meOn a six wagons trier. Dans la gare de triage, les wagons entrent dans l ordre 2, 5, 3, 6,1, 4 et doivent sortir dans l ordre croissant.

10 Deux wagonsietjpeuvent tre mis sur lam me voie si et seulement s ils entrent dans l ordre dans lequel ils doivent un graphe illustrant la situation, en indiquant ceque repr sentent les sommets etles ar tes de votre graphe . Quel sera le nombre minimal de voies n cessaires au tri ?SolutionOn repr sente les wagons par les sommets. Une ar te reliedeux sommetsietjsi les wagonsietjne peuvent pas tre sur la m me voie. On obtient le graphe voit que 1, 3 et 5 ne peuvent pas tre sur la m me faut donc trois voies au No6 CAHIERS DE LACRME xercice 1 Trois professeursP1,P2,P3devront donner lundi prochain un certain nombre d heures decours trois classesC1,C2,C3:P1doit donner 2 heures de cours C1et 1 heure C2;P2doit donner 1 heure de cours C1, 1 heure C2et 1 heure C3;P3doit donner 1 heure de cours C1, 1 heure C2et 2 heures repr senter cette situation par un graphe ?