Graphes planaires

Publié par

Graphes planairesCommen¸cons par ´enoncer deux probl`emes pratiques :Probl`eme 1 Dans un pays donn´e, on d´esire r´eorganiser les voies de commu-nications de facon¸ `a relier entre elles les 11 plus grandes villes. Elles doiventˆetre reli´ees deux a` deux soit par un canal, soit par un chemin de fer.Or les ing´enieurs du pays, s’ils savent parfaitement faire passer une voieferr´ee au-dessus d’un canal, ne savent pas faire passer une voie ferr´ee au-dessusd’une autre, ni un canal au-dessus d’un autre!Peut-on les aider, et leur proposer un trac´e? (On pourra placer les villescomme on le d´esire)Nous invitons le lecteur a` ne pas chercher une solution trop longtemps, nousverrons plus loin qu’il n’y en a pas! Un autre probl`eme du mˆeme type, assezc´el`ebre, est le suivant :Probl`eme 2 Sur un cˆot´e d’une rue, trois maisons sont align´ees. Devant ellessont plac´ees respectivement des arriv´ees g´en´erales de gaz, d’´electricit´e, et d’eau.Comment faire pour alimenter les trois maisons en ces trois fluides sans quedeux conduites ne se croisent?ElectriciteGaz EauSi l’on essaie de placer les diff´erentes conduites, on s’aper¸coit qu’il est pos-sible, sans trop de difficult´es, de placer les 8 premi`eres. En revanche, il sembleabsolument impossible de placer la derni`ere sans croiser l’une des pr´ec´edentes.Sur la figure ci-dessus, mˆeme en “contournant” le bloc, la derni`ere conduite,repr´esent´ee en pointill´es, croiserait n´ecessairement l’une des ...
Publié le : vendredi 30 septembre 2011
Lecture(s) : 40
Nombre de pages : 7
Voir plus Voir moins
Graphes planaires
Commen¸conspar´enoncerdeuxproble`mespratiques: Probl`eme1sunpDanno´nyads´dse,enoor´eerirrlsenigadseiovse-ummoce nicationsdefac¸on`arelierentreellesles11plus grandes villes. Elles doivent ˆetrerelie´esdeux`adeuxsoitparuncanal,soitparunchemindefer. Orlesing´enieursdupays,silssaventparfaitementfairepasserunevoie ferr´eeau-dessusduncanal,nesaventpasfairepasserunevoieferre´eau-dessus d’une autre, ni un canal au-dessus d’un autre! Peut-onlesaider,etleurproposeruntrac´e?(Onpourraplacerlesvilles commeonlede´sire) Nousinvitonslelecteura`nepaschercherunesolutiontroplongtemps,nous verronsplusloinquilnyenapas!Unautreproble`medumeˆmetype,assez ce´le`bre,estlesuivant: Probl`eme2renude´toˆcnurussonismaisro,tuee´seD.venoatilngSantelles sontplace´esrespectivementdesarriv´eesge´n´eralesdegaz,de´lectricite´,etdeau. Comment faire pour alimenter les trois maisons en ces trois fluides sans que deux conduites ne se croisent?
Silonessaiedeplacerlesdi´erentesconduites,onsaper¸coitquilestpos-sible,sanstropdedicult´es,deplacerles8premi`eres.Enrevanche,ilsemble absolumentimpossibledeplacerladernie`resanscroiserlunedespr´ec´edentes. Surlagureci-dessus,meˆmeencontournantlebloc,ladernie`reconduite, repr´esent´eeenpointille´s,croiseraitn´ecessairementlunedespre´c´edentes.
1 Graphesplanaires Danstoutcetexte,nousneconsid´ereronsquedesgraphessimples,cest-a`-diredesgraphessansboucle(areˆtejoignantunsommeta`lui-mˆeme),etsans areˆtemultiple(deuxsommetsreli´esparplusieuresareˆtes).
1
1.1De´nitions Lesdeuxproble`mespr´ec´edentsnousconduisenta`introduireplusformelle-mentlanotiondegrapheplanaire:ilsagitdede´terminerdesconditionsdans lesquelles nous pourrons affirmer que tel ou tel graphe EST planaire, ou N’EST PASpanaire.Ontrouveraunepr´esentationle´g`erementdi´erentedecequisuit dans [2]. D´enitiondessmbletsesommeehodrgpaneestnluntGoiStonteVe´elt-n sembledesareˆtesE. Unerepre´sentationplanairedugrapheGestladonn´ee,dansleplan,dun ensembledepointsdemˆemecardinalqueV,reli´esdeuxa`deuxpardes courbes continues du plan lorsque les sommets correspondant du graphe sontreli´es,ettelsquecescourbesnesecroisentpas. UngrapheGestditplanairesietseulementsiiladmetunerepre´sentation planaire. Exemplentse´eprendioatS:olinocnsid`erelecubecomemnurgpaehu,ener perspectiveclassique(`agauche)neserapasplanaire.Cecipourraitnousinciter `apenserquelegraphecorrespondantnelestpasnonplus.Ilnenestrien, commelemontrerlarepre´sentationdedroitedumˆemegraphe,planairecette fois.
En revanche, le graphe correspondant au estappel´egraphebipartitecomplet3×3, et chaque sommet d’un ensemble de 3 sommets ensemble de 3 sommets.
probl`eme2nestpasplanaire.Il not´eK3,3. C’est le graphe reliant a`chaquesommetdundeuxi`eme
De´nitiongSiooneGru´ietmalemaxiepphrange.irnalaFecafenUnutseGed dupland´elimite´eparunensembledareˆtesdeG,etquinencontientaucune. Ledegr´edeF,note´deg(F),estlenombredarˆetesdeGquibordentF.
Exemplereprnsla:Dacubu,eonguarhpdeuspnoianalese´tatnde´eedntepirecr´ avonsexactement6faces,num´erote´esde1a`6.Toutessontborde´espar4arˆetes dugrapheexactement,cest-`a-direquellessonttouesdedegre´4.
1.2Unepremie`reproprie´t´e Propri´et´e1.1SoitGun graphe planaire etalomenedbrrˆaedteseG. Alors P deg(F) = 2a Fface
D´emonstrationntdeele:uesqvi´eeminelrpxeeti´prroretpes´epetteC nimoinsquelefaitquunearˆetedonne´edugrapheGbordeexactement Ellecontribuepour1audegre´dechacune.
2
ni plus 2 faces.
P Lorsque l’on calcule la sommedegee´ttcaxnemet),onauradonccompF( F face deuxfoischaqueareˆtedugraphe. Exempleepr´trerdenoecasnaianolpatitseneduhedureapgrlsnadsruojuoT: cube,les6facessonttoutesdedegr´e4,soituntotalde64 = 24, et nous avons bien 24/122=s.teˆear
2 Laformule d’Euler 2.1 Unoutil technique De´nition (i)Un chemin de longueurrdu graphe G est une suite (S0, . . . ,Sr) de som-mets telle que pour toutidans[0 ;r1]naStiixeleustarneteˆelirei`a Si+1. S0,nimehcuseSteel´etappinedorigrrtxeedt´mi´en.miheuc (ii)delemmsouttoupcoerteilerpsteˆtueapheestdUngrleroqseutiocnnxe´e par un chemin. (iii)Le chemin (S0, . . . ,Sr´eelpptaes)mehcuo(tiucricnueriefnie´mris)e´vl S0= Sr. (iv)Un arbre est un graphe connexe sans circuit. Lemme 2.1Tout graphe connexe peut s’obtenir en ajoutant un certain nombre darˆetes`aunarbre(ayantmˆemenombredesommets). D´emonstrationaPcase.Leraphsdugtiucricederbmonerlsuceenrrcu´errn= 0estimme´diat,puisquungrapheconnexesanscircuitestunarbre.Supposons donclere´sultat´etablipourtouslesgraphesconnexesayantauplusncircuits (naissormrd´entie.´x)eesnetu SoitGungrapheconnexeposse´dantexactementn.Consid´circuits1+renos 0 legrapheGobtenuenenlevant`aGexactementuneareˆtedelundescircuits. 0 AlorsGestencoreungrapheconnexe,posse´dantcettefoisauplusncircuits. Eneet,lefaitquilaitstrictementmoinsdecircuitsqueGestimme´diat: nousavonsenlev´euneareˆteduncircuit,etcefaisantlecircuitenquestionnest 0 0 pas dans G. Comme Gest un sous-graphe de G (i.e. est inclus dans G), tout 0 0 circuit de Gest un circuit de G, et donc Ga strictement moins de circuits que G. 0 N.B.peut avoir strictement moins queAttention : Gneetcriucti,saclraˆr enlev´eepeutappartenira`plusieurscircuitsdeG. 0 0 D’autre part, Gest encore connexe. Pour voir cela, soient S et Sdeux 0 sommets.CommeGestconnexe,ilexistedansGunchemindeS`aS. Sicecheminnepassepasparlarˆetequelonenle`ve,ilestencoredans 0 0 Getdonclesdeuxsommetsresterelie´sdansG.Sicecheminpassepar larˆeteenquestion,ilsutdefaireletour:silonappelleS1et S2les deux sommetsrelie´sparlarˆetequlonoˆte,nousavionsuncircuitdelaforme: (S1,S2,S3, . . . ,Sr,S1)(o`urteatunentieesapeue´drp,)rqsiuteetˆearitnncio 0 e´t´echoisieappartenenta`uncircuit.DanslechemindeSa`S,ilsutalorsde
3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.