Graphes planaires

Description

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 ...

Informations

• Publié par: mtoledan
• Publié le: 30 septembre 2011
• Nombre de lectures: 43
• Langue: Français

Extrait

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,s’ilssaventparfaitementfairepasserunevoie ferr´eeau-dessusd’uncanal,nesaventpasfairepasserunevoieferre´eau-dessus d’une autre, ni un canal au-dessus d’un autre! Peut-onlesaider,etleurproposeruntrac´e?(Onpourraplacerlesvilles commeonlede´sire) Nousinvitonslelecteura`nepaschercherunesolutiontroplongtemps,nous verronsplusloinqu’iln’yenapas!Unautreproble`medumeˆmetype,assez ce´le`bre,estlesuivant: Probl`eme2renu’de´toˆcnurussonismaisro,tuee´seD.venoatilngSantelles sontplace´esrespectivementdesarriv´eesge´n´eralesdegaz,d’e´lectricite´,etd’eau. Comment faire pour alimenter les trois maisons en ces trois fluides sans que deux conduites ne se croisent?

Sil’onessaiedeplacerlesdiff´erentesconduites,ons’aper¸coitqu’ilestpos- sible,sanstropdedifficult´es,deplacerles8premi`eres.Enrevanche,ilsemble absolumentimpossibledeplacerladernie`resanscroiserl’unedespr´ec´edentes. Surlafigureci-dessus,meˆmeen“contournant”lebloc,ladernie`reconduite, repr´esent´eeenpointille´s,croiseraitn´ecessairementl’unedespre´c´edentes.

1 Graphesplanaires Danstoutcetexte,nousneconsid´ereronsquedesgraphessimples,c’est-a`- diredesgraphessans“boucle”(areˆtejoignantunsommeta`lui-mˆeme),etsans areˆtemultiple(deuxsommetsreli´esparplusieuresareˆtes).

1

1.1De´finitions Lesdeuxproble`mespr´ec´edentsnousconduisenta`introduireplusformelle- mentlanotiondegrapheplanaire:ils’agitdede´terminerdesconditionsdans lesquelles nous pourrons affirmer que tel ou tel graphe EST planaire, ou N’EST PASpanaire.Ontrouveraunepr´esentationle´g`erementdiff´erentedecequisuit dans [2]. D´efinitiondessmbletsesommeehodrgpaneestn’luntGoiStonteVe´e’lt-n sembledesareˆtesE. –Unerepre´sentationplanairedugrapheGestladonn´ee,dansleplan,d’un ensembledepointsdemˆemecardinalqueV,reli´esdeuxa`deuxpardes courbes continues du plan lorsque les sommets correspondant du graphe sontreli´es,ettelsquecescourbesnesecroisentpas. –UngrapheGestditplanairesietseulementsiiladmetunerepre´sentation planaire. Exemplentse´eprendioatS:o’linocnsid`erelecubecomemnurgpaehu,ener perspectiveclassique(`agauche)neserapasplanaire.Cecipourraitnousinciter `apenserquelegraphecorrespondantnel’estpasnonplus.Iln’enestrien, 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`eme2n’estpasplanaire.Il not´eK 3,3 . C’est le graphe reliant a`chaquesommetd’undeuxi`eme

De´finitiongSiooneGru´ietmalemaxiepphrange.irnalaFecafenUnutseGed dupland´elimite´eparunensembled’areˆtesdeG,etquin’encontientaucune. Ledegr´edeF,note´deg(F),estlenombred’arˆetesdeGquibordentF.

Exemplereprnsla:Dacubu,eonguarhpdeuspnoianalese´tatnde´eedntepirecr´ avonsexactement6faces,num´erote´esde1a`6.Toutessontborde´espar4arˆetes dugrapheexactement,c’est-`a-direqu’ellessonttouesdedegre´4.

1.2Unepremie`reproprie´t´e Propri´et´e1.1SoitGun graphe planaire etalomenedbrrˆ’aedteseG. Alors P deg(F) = 2a Fface

D´emonstrationntdeele:uesqvi´eemi’nelrpxeeti´prroretpes´epetteC nimoinsquelefaitqu’unearˆ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,soituntotalde6∙4 = 24, et nous avons bien 24/122=s.teˆear

2 Laformule d’Euler 2.1 Unoutil technique De´finition (i)Un chemin de longueurrdu graphe G est une suite (S 0 , . . . ,S r ) de som- mets telle que pour toutidans[0 ;r−1]naStiixeleustarneteˆelire i `a S i+1 . S 0 ,nimehcuseSteel´etappinedorig r rtxeedt´mi´en.miheuc (ii)delemmsouttoupcoerteilerpsteˆtueapheestdUngrleroqseutiocnnxe´e par un chemin. (iii)Le chemin (S 0 , . . . ,S r ´eelpptaes)mehcuo(tiucricnufieriefnie´mri’s)e´vl S 0 = S r . (iv)Un arbre est un graphe connexe sans circuit. Lemme 2.1Tout graphe connexe peut s’obtenir en ajoutant un certain nombre d’arˆetes`aunarbre(ayantmˆemenombredesommets). D´emonstrationaPcase.Leraphsdugtiucricederbmonerlsuceenrrcu´errn= 0estimme´diat,puisqu’ungrapheconnexesanscircuitestunarbre.Supposons donclere´sultat´etablipourtouslesgraphesconnexesayantauplusncircuits (naisfisormrd´entie.´x)eesnetu SoitGungrapheconnexeposse´dantexactementn.Consid´circuits1+renos 0 legrapheGobtenuenenlevant`aGexactementuneareˆtedel’undescircuits. 0 AlorsGestencoreungrapheconnexe,posse´dantcettefoisauplusncircuits. Eneffet,lefaitqu’ilaitstrictementmoinsdecircuitsqueGestimme´diat: nousavonsenlev´euneareˆted’uncircuit,etcefaisantlecircuitenquestionn’est 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. Sicecheminnepassepasparl’arˆetequel’onenle`ve,ilestencoredans 0 0 Getdonclesdeuxsommetsresterelie´sdansG.Sicecheminpassepar l’arˆeteenquestion,ilsuffitde“faireletour”:sil’onappelleS 1 et S 2 les deux sommetsrelie´sparl’arˆetequl’onoˆte,nousavionsuncircuitdelaforme: (S 1 ,S 2 ,S 3 , . . . ,S r ,S 1 )(o`urteatunentieesapeue´drp,)rqsiuteetˆearitfinncio 0 e´t´echoisieappartenenta`uncircuit.DanslechemindeSa`S,ilsuffitalorsde

3