资料课件讲义英文版课件4 1-2

CHAPTER4,RelationsAndDigraphs关系与有向图,4.1ProductSetsandPartitions笛卡尔积与划分,Productsets（笛卡尔积）Anorderedpair有序对(a,b)isalistingoftheobjectsaandbinaprescribedorder,withaappearingfirstandbappearingsecond.Thusanorderedpairismerelyasequenceoflength2.Theorderedpairs(a1,b1)and(a2,b2)areequalifandonlyifa1=a2andb1=b2.,IfAandBaretwononemptysets,wedefinetheproductsetorCartesianproductABasthesetofallorderedpairs(a,b)withaAandbB.ThusAB=(a,b)|aAandbB.Example1LetA=1,2,3andB=r,s;thenAB=(1,r),(1,s),(2,r),(2,s),(3,r),(3,s).,Theorem1Foranytwofinite,nonemptysetsAandB,|AB|=|A|B|.Example3IfA=B=R,thesetofallrealnumbers,thenRR,alsodenotedbyR2,isthesetofallpointsintheplane.Theorderedpair(a,b)givesthecoordinatesofapointintheplane.,Example4：Amarketingresearchfirmclassifiesapersonaccordingtothefollowingtwocriteria:Gender:male(m);female(f)Highestlevelofeducationcompleted:elementaryschool(e);highschool(h);college(c);graduateschool(g).,LetS=m,fandL=e,h,c,g.TheproductsetSLcontainsallthecategoriesintowhichthepopulationisclassified.Thustheclassification(f,g)representsafemalewhohascompletedgraduateschool.Thereareeightcategoriesinthisclassificationscheme.,WenowdefinetheCartesianproductofthreeormorenonemptysetsbygeneralizingtheearlierdefinitionoftheCartesianProductoftwosets：TheCartesianproductA1A2AmofthenonemptysetsA1,A2,AmistheSetofallorderedm-tuples(a1,a2,am),whereaiAi,i=1,2,m.ThusA1A2Am=(a1,a2,am)|aiA1,i=1,2,m.,Partitions划分,Apartitionorquotientset(商集)ofanonemptysetAisacollectionPofnonemptysubsetsofAsuchthat1.EachelementofAbelongstooneofthesetsinP.2.IfA1andA2aredistinctelementsofP,thenA1A2=.,Partitions,ThesetsinParecalledtheblocks(块)orcells(单元)ofthepartition.Figure4.1showsapartitionP=A1,A2,A3,A4,A5,A6,A7ofAintosevenblocks.,Figure4.1,Example6LetA=a,b,c,d,e,f,g,h.ConsiderthefollowingsubsetsofA:A1=a,b,c,d,A2=a,c,e,f,g,h,A3=a,c,e,g,A4=b,d,A5=f,h.ThenA1,A2isnotapartitionsinceA1A2.Also,A1,A5isnotapartitionsinceeA1andeA5.ThecollectionP=A3,A4,A5isapartitionofA.,Example7LetZ=setofallintegersA1=setofallevenintegers,andA2=setofalloddintegersThenA1,A2isapartitionofZ.SincethemembersofapartitionofsetAaresubsetsofA,weseethatthepartitionisasubsetofP(A),thepowersetofA.Thatis,partitionscanbeconsideredasparticularkindsofsubsetsofP(A).,4.2RelationsandDigraphs,LetAandBbenonemptysets，arelationRfromAtoBisasubsetofAB.IfRABand(a,b)R,wesaythataisrelatedtobbyR,andwealsowriteaRb.IfaisnotrelatedtobbyR,wewriteab.Frequently,AandBareequal.Inthiscase,weoftensaythatRAAisarelationonA,insteadofarelationfromAtoA.,Relationsareextremelyimportantinmathematicsanditsapplications.Itisnotanexaggeration(夸大)tosaythat90%ofwhatwillbediscussedintheremainderofthisbookwillconcernsometypeofobjectthatmaybeconsideredarelation.Wenowgiveanumberofexamples.,Example1LetA=1,2,3andB=r,s.ThenR=(1,r),(2,s),(3,r)isarelationfromAtoB.Example2LetAandBbesetsofrealnumbers.WedefinethefollowingrelationR(equals)fromAtoB:aRbifandonlyifa=b.,Example3LetA=1,2,3,4,5.DefinethefollowingrelationR(lessthan)onA:aRbifandonlyifa1.Thus,inthiscase,R(x)=.Ifx=-2,thenx2/4=1,soxcanonlyberelatedto0.ThusR(-2)=0.Similarly,R(2)=0.Finally,if-2x2andxRy,thenwemusthave,asweseebysolvingtheequationx2/4+y2/9=1,sothatR(x)=.Thus,forexample,R(1)=.ThefollowingtheoremshowsthebehavioroftheR-relativesetswithregardtobasicsetoperations.,Theorem1LetRbearelationfromAtoB,andletA1andA2besubsetsofA.Then,Proof,Thestrategyofthisproofisonewehaveseenmanytimesinearliersections:Applyarelevantdefinitiontoagenericobject.NoticethatTheorem1(c)doesnotclaimequalityofsets.SeeExercise20forconditionsunderwhichthetwosetsareequal.Inthefollowingexample,wewillseethatequalitydoesnotalwayshold.,Example:LetA=Z,Rbe“”，A1=0,1,2,andA2=9,13.ThenR(A1)consistsofallintegersnsuchthat0n.ThusR(A1)=0,1,2.Similarly,R(A2)=9,10,11,soR(A1)R(A2)=9,10,11,.Ontheotherhand,A1A2=,soR(A1A2)=.ThisshowsthatthecontainmentinTheorem1(c)isnotalwaysanequality.,Example:LetA=1,2,3andB=x,y,z,w,p,q,andconsidertherelationR=(1,x),(1,z),(2,w),(2,p),(2,q),(3,y).LetA1=1,2andA2=2,3.ThenRA1)=x,z,w,p,qandR(A2)=w,p,q,y.ThusRA1)R(A2)=B.SinceA1A2=A,weseethatR(A1A2)=R(A)=B,asstatedinTheorem1(b).Also,R(A1)R(A2)=w,p,q=R(2)=R(A1A2),sointhiscaseequalitydoesholdforthecontainmentinTheorem1(c).,ItisausefulandeasilyseenfactthatthesetsR(a),forainA,completelydeterminearelationR.Westatethisfactpreciselyinthefollowingtheorem.Theorem2LetRandSberelationsfromAtoB.IfR(a)=S(a)forallainA,thenR=S.ProofIfaRb,thenbR(a).Therefore,bS(a)andaSb.Acompletelysimilarargumentshowsthat,ifaSb,thenaRb.ThusR=S.,TheMatrixofaRelation关系矩阵,Wecanrepresentarelationbetweentwofinitesetswithamatrixasfollows.IfA=a1,a2,amandB=b1,b2,bnarefinitesetscontainingmandnelements,respectively,andRisarelationfromAtoB,werepresentRbythemnmatrixMR=mij,whichisdefinedby,ThematrixMRiscalledthematrixofR.OftenMRprovidesaneasywaytocheckwhetherRhasagivenproperty.Example:LetRbetherelationdefinedinExample1.ThenthematrixofRis,Conversely,givensetsAandBwith|A|=mand|B|=n,anmnmatrixwhoseentriesarezerosandonesdeterminesarelation,asisillustratedinthefollowingexample.Example:Considerthematrix,SinceMis34,weletA=a1,a2,a3andB=b1,b2,b3,b4.Then(ai,bj)Rifandonlyifmij=1.ThusR=(a1,b1),(a1,b4),(a2,b2),(a2,b3),(a3,b1),(a3,b3).,TheDigraphofaRelation关系的有向图,IfAisafinitesetandRisarelationonA,wecanalsorepresentRpictoriallyasfollows.DrawasmallcircleforeachelementofAandlabelthecirclewiththecorrespondingelementofA.Thesecirclesarecalledvertices.Drawanarrow,calledanedge,fromvertexaitovertexajifandonlyifaiRaj.TheresultingpictorialrepresentationofRiscalledadirectedgraphordigraphofR.,IfRisarelationonA,theedgesinthedigraphofRcorrespondexactlytothepairsinR,andtheverticescorrespondexactlytotheelementsofthesetA.Sometimes,whenwewanttoemphasizethegeometricnatureofsomepropertyofR,wemayrefertothepairsofRthemselvesasedgesandtheelementsofAasvertices.,ThenthedigraphofRisasshowninFigure4.4.,Example:LetA=1,2,3,4R=(1,1),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1).,1,4,2,3,Figure4.4,Acollectionofverticeswithedgesbetweensomeoftheverticesdeterminesarelationinnaturalmanner.,Example:FindtherelationdeterminedbyFigure4.5.SolutionSinceaiRajifthereisanedgefromaitoaj,wehaveR=(1,1),(1,3),(2,3),(3,2),(3,3),4,3).,2,1,3,4,Figure4.5,Inthisbook,digraphsarenothingbutgeometricalrepresentationsofrelations,andanystatementmadeaboutadigraphisactuallyastatementaboutthecorrespondingrelation.Thisisespeciallyimportantfortheoremsandtheirproofs.Insomecases,itiseasierorclearertostatearesultingraphicalterms,butaproofwillalwaysrefertotheunderlyingrelation.Thereadershouldbeawarethatsomeauthorsallowmoregeneralobjectsasdigraphs;forexample,bypermittingseveraledgesinthesamedirectionbetweenthesamevertices.,Animportantconceptforrelationsisinspiredbythevisualformofdigraphs.IfRisarelationonasetAandaA,thenthein-degreeofa(relativetotherelationR)isthenumberofbAsuchthat(b,a)R.Theout-degreeofaisthenumberofbAsuchthat(a,b)R.Whatthismeans,intermsofthedigraphofR,isthatthein-degreeofavertexofthenumberofedgesterminatingatthevertex.Theoutdegreeofavertexisthenumberofedgesleavingthevertex.Notethattheout-degreeofais|R(a)|.,Example:ConsiderthedigraphofFigure4.4.Vertex1hasin-degree3andout-degree2.AlsoconsiderthedigraphshowninFigure4.5.Vertex3