; TeX output 2004.04.29:0543荠7o]{o]jN cmbx12SEMINARANK4UNDIGUNG)ݍ XQ cmr12ImSommersemster2004wrerdeicheinSeminaranbieten>6yubSerݍendlichedynamischeSysteme. EndlicrhedynamischeSystemesinddurchAbbildungeng cmmi12fQ:URXF!", cmsy10!XeinerendlicrhenMengeX~insicrhbSeschrieben.ManistamVVerhaltenderinteriertenAbbildungenfG22cmmi8n :/8X !Xinrteressiert,demy*@ cmti12dynamischen]VerhaltendesSystems. VVoraussagendarSyubSerIsindsindscrhonindeneinfachstenFyallenrechtschwierig.SVVonbSesonderemInrteressesindFixpunkteundpSeriodischePunkte.* EineTumfangreicrheTheoriebSefatsichmitAbbildungenderFVormfRQ: RKܞ2n @!Kܞ2n,wrobSeiKeinendlicherKyorpSerist.AllesolchenAbbildungenwerdendurchPolynomeSyubSerAAK߹bescrhrieben.COFVallsf@einelineareoderaneAbbildungist,AkXannmandasdynamiscrheVVerhaltenvonfavollstyandigbSeschreiben.IFVallsdiePolynomevonfaaus-scrhlielichMonomesindundK,=PW' msbm10F|{Ycmr82 Ԍist,istvielhyubSerFixpunkteundperiodiscrhePunktehbSekXannrt.[EinsolchesSystemkXannalsbSoolscheshNetzmitAND?OpSeratorenaufgefatwrerden.* UmfangreicrheMAnwendungensindinderInformatik,denBiowissenschaften,derVVerkrehrstechnik,denElekrizityatsnetzenundvielenanderenWissenscrhaftenzu nden. WirwrerdenauchspSezielledynamischeSystemestudieren,sogenannteseffquenzielledynamischeH>Systeme,bSeidenendieAbbildungfIdurcrheinebesondereKonstruktiongegebSenist. Anmeldungen꨹kyonnenabsofortgericrhtetwerdenanݍ%〹HerrnDr.Y.Sommerhyauser,Zi.Nr.,%〹FVrauS.Kaiser,Zi.Nr.430,%〹oSderanmicrhperEmail.b?Hgez.B.Prareigisڎff< B ': cmti10Date[K`y cmr10:UU29.April2004. ]+o cmr91*荠7o]2SEMINAR!SS04[o]h,- cmcsc10Inhal32tsverzeichnis* 1. Graphenrtheorie;v2* 1.1. ScrhlichteGraphen#2 1.2. GericrhteteGraphen{Digraphsl 5 1.3. CategoriesL 5 1.4. Moreongraphs1 6 2. FinitedynamicalsystemsE7 2.1. Finitedynamicalsystems"7 2.2. Cellularautomata$_9 2.3. Thestatespaceorphasegraph10 2.4. Realdynamicalsystems11 2.5. Thefunctionalgraph(13 2.6.13 3. Prolynomialsystemsx13_n:1.Graphentheorie*1.1.SchlichteGraphen.9De nition21.1.NDiee6MengeAeA٫=ffa;bgja;b٫2AgP(A)e6heitMenge*derungeffordneten35PaareXinA.De nitionz1.2.9EinZzGrffaph@*isteinTVripSel(V;E;n9)ZzbestehendausderMengeVderKnotenE(engl.,vrertex,,vertices),der,MengeEହderKantenE(engl.,edge)undderEnd-punktbildungd,{c: *EA!V1V:VFSyureineKanrtektG2 *E heiendieKnotenaundbmitn9(kg)UR=fa;bg1Endpunktevronk.3EineKanrtekundeinKnotenaheieninzident,2wennaweinEndpunktvronkist.kEineKantekheiteineSchlinge,wennn9(kg)c=fagweineeinelemenrtigenMengeist.oMEinGraphheitschlicht,nwennȹinjektivistundderGraphohne_Scrhlingenist.ZEinGraphheitendlich,wennernurendlichvieleKantenundKnotenbSesitzt.Bemerkungع1.3.Ein1endlicrherschlichterGraphwirdhyau gdurchseineAffdjazenzma-trix[dargestellt;z.B.B޳2Z36ffv1v2²v3gv4l,Qff~ ʍv1.036ff"T01p0v2.036ff"T01p1v3.036ff"T10p1v4.036ff"T01p0y=UR!u cmex100ǍURB38URBUR@ʍ T0P0-L1=uH0 T0P0-L1=uH1 T1P1-L0=uH1 T0P1-L1=uH0CUD1ǍCUDC38CUDCCUDA J荠7o]SEMINAR!SS04s3[o]wrobSei:vV-W=fv1;:::ʜ;v4gundEdargestelltistdurcrhdie1-eninderMatrix.`XU=(V;E;n9)undYB=(Vp20j;E20P;n920EinHomomor-phismus^f5:6X¹!YbSestehrt`>auszweiAbbildungenfV ':6Vm!Vp20j;fE :EM!E20mitmS?8ko2URE[n9(kg)=fa;bg=) 00p0v2.036ff"T00p0v3.036ff"T10p1v4.036ff"T00p0y=UR0ǍURB38URBUR@ʍ T0P0-L0=uH0 T0P0-L0=uH0 T1P1-L0=uH1 T0P1-L0=uH0CUD1ǍCUDC38CUDCCUDA5C፹wrobSei:vV-W=fv1;:::ʜ;v4gundEdargestelltistdurcrhdie1-eninderMatrix.7h(gn9fG)UR=(hg)fG;(2)%IdenrtityLaw:%8A62Ob}C91A2MorlڟC!ڙ(A;A)2]8B;C{26ݹObC5;2[8f~26ݹMorlڟC!ڙ(A;B);8g2%〹Mor;}C@<(C5;A)UR:31AgË=URgѹandJ1fG1A 36=f:s2Examples1.17.1.ThecategoryofsetsSet1)?*uD(c)=ѬFindastatecwhicrhisnotintheimageoffG,f(c209)UR6=c꨹forallstatesc20.)' (d)=ѬHorwmanystatescaretheresuchthatfG23(c)UR=c?!2.2.Cellular0automata.CellularFautomatawrereinventedbyJohnvonNeumannand9StanislarvUlaminordertosimulatecertainnaturalsystemsandthephenomenonofzself-reproSduction.fThemostpopularexampleofacellularautomatonistheso-called*"gGameofLife-l\CinrtroSducedbyConwayinthe70's.Thereferenceis:HJ.H.ConwayV,1970unpublished.OtherreferencesarethearticlesofM.Gardnerin1970-1972inScienrti cAmericanorY1@,andthebSooksY2.NotethatthisgameisnamedafterConrwayandGolaryY3ћ(Golay'sgamehasanunderlyinghexagonaltilingY4@). Thisgameisde nedas follorws. WVehaveanin nitetwo-dimensionalbSoardwhoseelementarysquaresarecalledcffells.fAcellcanbSelivingordead.fTheneighrbSorsofacellarede nedtobetheeighrt;cellssurroundingit.?ThereisaregulartimepSeriod.Art;eachtimestepthecellsareupSdatedinaparallelwray:S(1)%ifthenrumbSeroflivingneighrborsofacellisexactly2,thenthecellkreepsthe%samevXalue(livingordead);(2)%ifthenrumbSeroflivingneighrborsofacellisexactly3,thenthecellwilltakre%thevXaluelivingwhatevrerthepreviousvaluewras;(3)%if9thenrumbSer9oflivingneighrborsofacellisanryothernumbSer,9thenthecell%willtakrethevXaluedeffadwhateverthepreviousvXaluewas.SIn#otherwrordsacelldieseitherifitisisolateffdorinanovercrowdedenrvironment.=ItcomestolifeorsurvivresifthenumbSeroflivingneighbSorsisjustright.* InsteadKofconsideringanin nitebSoard,Wwrecanreplaceeachelementarysquarebyits southrwestcorner.Thecorner(insteadofthecell)willtakethevXalueslivingordeffad.xThebSoarditselfwillthrusbereplacedbrythesquarelatticeZ22.xWVewillusethisalternativrerepresentationintheformalde nitionbSelow.aff< 1@M.Gardner,Wheels,lifeandothermathematicalamusements,W.H.F*reemanandCompany*, 1983 l 2@E.R.Berlekqamp,J.H.Conway*,R.K.Guy*,Winningwaysforyourmathematicalplays,vol.2,AcademicAPress,\1982,andJ.L.Casti,Alternaterealities.MathematicalmoGdelsofnatureandman,JohnUUWiley&Sons,1989. 3@C.P*.vqanNieuwkasteele,K.A.Post,SomeinvestigationsontheConway-GolaygameLife,EUT-Rep.,UUEindhoven84-WSK-03(1984)282{296.(Zentralblatt582.92019.) 4@M..Garzon,JMoGdelsofmassiveparallelism.Analysisofcellularautomataandneuralnetworks,T*extsUUinTheoreticalComputerScience,Springer,1995. c\荠7o]10SEMINAR!SS04[o] TrypicalproblemsstudiedintheLifegameare:structuresthatprffopagate(thesocalledgliders),structuresthatgivrebirthtostructuresidenticaltothemselves(thisquestion=isclosetotheoriginalproblem),·patternsthatharve=apSeriodic=timeevrolution,crashes bSetrweenstructures,8existenceofcon gurationswithoutpredecessors(calledgarffdens35ofEden),computationsacrhievedbyevolvingpatterns...* WVebSeginwithaninrtuitivede nitionofacellularautomaton.Westartfromasetthat.canbSe niteorin nite(thissetisusuallyagrid).FVoreacrhelementainthissetwrearegivena nitenumbSerofelementsofthesetincludingtheelementaitselfthatarecalledtheneighbfforsofa.WVeharveamapfromthissettoasetofstates(usually nite):~this}mapiscalledacffon guration.~vThe}imagesofcon gurationscanbSeseenasobservables.BWVealsoharveanupSdatingfunctioncalledthelocalfunction(orlocalrule):toobtainthenewvXalueassignedtoanelemenrt,weneedtheelemenrtitself,and/VthevXaluesofallitsneighrbSors(weinsistthatthesetofneighbSorsofanelementconrtainsthiselement).cTheupSdateisdonein\pffarallel:@thenewvXaluesarecomputedsimrultaneouslyV.卍De nition2.3.~GAcffellularpautomatononasetF)isde nedasfollorws:3weare%givrenr@foreachelementaUR2F(alsor@calledacffell)a nitesubsetN@(a)ofFthat%conrtainsaandiscalledthesetofneighbfforsofthecella. WVearealsogiven%a]JsetofvXalueskg(usually nite).]Finallywrearegivenforeachap2Fa]JloffcalZ΍%mapfa Vfromkg2N"(a)9/tok(wherekg2N"(a)isthesetofmapsfromN@(a)tokg).A%cffon guration꨹isanelemenrtofkg2Fvl,i.e.,amapfromFntokg.%〹TheloScalmapsfa!induceaglobffalvmapfefromthesetofcon gurationstoitself%asfollorws.LetcbSeacon guration.WVede nethecon gurationfG(c)by:̍}vforeacrhbaUR2FS;fG(c)(a):=faϹ(cjN"(a)9)%wherecjN"(a)$3istherestrictionofctothesetN@(a).%〹Thew*time evolutionofthecellularautomaton,wHstartingfromaninitialcon gu-%rationc,istheorbitofcunderfG,i.e.,thesequenceofcon gurations̍}Ac;fG(c);f(f(c))UR=f 2(c):::ʜ;f tɹ(c);:::z2.3.Thestatespaceorphasegraph.De nitionP2.4.#LetKmfƹ:XJ!XaandfG(b)Thenfhasperiodicpointsofanyorffder35mforallnUR>m35inthefollowingSarkrovskiiorder35ofN:3UR>5>7:::ʜ23UR>25UR>27:::22nR3UR>22n5>22n7:::ʜ223V>222>2>1: 2荠7o]12SEMINAR!SS04[o] WVemQonlyshorwthefollowingCorollarywhichisamuchweakerversionofthisTheo-rem.Folgerung2.12.Lffet\xf麹:R!Rbffeacontinuousfunctionandletfwhaveaperiodicpffoint35oforder3.Thenf{4hasperiodicpointsofanyordern. Prffoof.#RLet4fa;b;cgbSeaperiodicorbitoffG. WVemaryassumethata_1bSeaninteger.(Ifnv=3wearedone.(TVoshowthatfXhasapSeriodicpSoinrtofperiodnwrewillconstructanestedsequence=FyAnUR:::uDURA2VA1A0=I1ofclosedinrtervXalswiththefollowingpropSerties:M(1)%fG(Ak#)UR=Ak61궹forko=1;:::n2;(2)%fG2kk(Ak#)UR=I1forko=1;:::;n2;(3)%fG2n1˹(An1̹)UR=I0;(4)%fG2nO(AnP)UR=I1.Firstwreshowthat,ifsuchasequenceofintervXalsexists,thenf hasapSeriodicpointofk[pSeriodn.l SinceAn ز0bI1,k|Propertry(4)impliesthatAn ز0bfG2nO(AnP),k|sothatfG2n [hasap xedpSoinrtinAnP,}whichjustmeansthatfgohasapSeriodicppointppinAn suchthatfG2nO(p)UR=p.ItremainstoshorwthatnisthepSeriodofp.* ThenPropSertry(2)ofthesequenceimpliesthatfG2iٹ(p)*2I1 =[b;c]foralli*=0;:::ʜ;nf82'(withtheconrvention'thatfG20(x)UR=x),/and'fG2n1˹(p)2I0V=[a;b].ZFirst'wreshorw{Lthatpisnotequaltoeitherborc.|+SuppSosethatpK=c.Then{LfG(p)=a=2 I1.TheconditionsonthesequenceimplythatfG2n1˹(p)istheonlyiterateofpthatisnotinDI1,DhencenX=2.EButDthisconrtradictsthefactthatthepSeriodDofcis3.SopX6=c.NorwcsuppSosethatpUR=b.vAgain,ftheconlyiterateofpnotinI1gisthe(n1)st.SincefG22(p)=a64=2I1,thisɣimpliesthatnݹ=3.ButɣthisconrtradictsourassumptionthatnUR6=3.* NorwxobservethatfG2n1˹(p)2I0 f =[a;b],whicrhisdisjointfromtheintervXal(b;c).ThisZ@impliesthatfG2n1˹(p)UR6=p,ZesoZ@thatpcannotharveZ@pSeriodn1.[IfthepSeriodislessthancn1,dthenPropSertry(2)impliesthattheorbitofpisentirelycontainedin(b;c),butthisconrtradictsPropSerty(3).TheonlyotherpSossibilityisthatphaspSeriodn.* ItremainstoshorwthattheabSovesequenceofintervXalsexists. LetA0 !=aI1,asrequired./CSince.A0jffG(A0),.wrecan ndanintervXalA1jfA0޹suchthatfG(AlC)f=A0.Again,#since# A1uRNA0,wreobtainthatA1uRNfG(A1).#bAsbSefore,wre ndA2uRNA1suchthatGfG(A2)=A1.H}WVeGconrtinueinthismannertode neAid;i=0;:::n)2.H}TVoGde neAn1̹,notethatVፑx#5fG n1˹(An2̹)UR=fG(f n2(An2̹))UR=fG(I1):Since^I0ڲfG(I1),^wreknowthatI0ڲfG2n1˹(An2̹)._MHencethereisAn1zAn2gsucrhthatfG(An1̹)UR=I0.FinallyV,Y}sfG nO(An1̹)UR=fG(f n1˹(An1))UR=fG(I0); w荠7o]SEMINAR!SS04Ӷ13[o]and:I1VURfG(I0).Thrus,yasbSefore,thereisAnURAn1}sucrhthatfG(AnP)=I1,yasrequired.ThiscompletestheproSofofthetheorem.գ/ۍOH8PSfile="Fig4.ps" llx=35 lly=35 urx=557 ury=305 rhi=1417 2.5.Thefunctionalgraph.s2De nition2.13.LetpfQ:URXF!XbSea nitedynamicalsystem.oThenfid ʤ;f;fG22;:::ʜ;fG2m L;:::ʞgformsJamonoidundercompSositionasmrultiplication.KSincethereareonly nitelyma-nrymapsfromXܑtoX,thereareleastnumbSersr>andn,suchthatfG2n+iǡ=VfG2nr