《明朝的对外关系》下载

Chapter11.GraphsandTrees11.1Graphs:Introduction11.2PathsandCircuits11.3MatrixRepresentationsofGraphs11.5Trees11.6SpanningTrees1Chapter11.GraphsandTrees1111.1Graphs:Introduction211.1Graphs:Introduction2DefinitionAgraph

Gconsistsoftwofinitesets:asetV(G)ofverticesandasetE(G)ofedges,whereeachedgeisassociatedwithasetconsistingofeitheroneortwoverticescalleditsendpoints.Thecorrespondencefromedgestoendpointsiscalledtheedge-endpointfunction.

Anedgewithjustoneendpointiscalledaloop.Twodistinctedgeswiththesamesetofendpointsaresaidtobeparallel.3Definition3Definition(continued)Anedgeissaidtoconnectitsendpoints.Twoverticesthatareconnectedbyanedgearecalledadjacent.Avertexthatisanendpointofaloopissaidbeadjacenttoitself.Anedgeissaidtobe

incident

oneachofitsendpoints,andtwoedgesincidentonthesameendpointarecalledadjacent.4Definition(continued)4Definition(continued)Avertexonwhichnoedgesareincidentiscalledisolated.Agraphwithnoverticesiscalledempty.Andonewithatleastonevertexiscalled

nonempty.5Definition(continued)5Example11.1.1Forthegraphpicturedbelow.a.Writethevertexsetandtheedgeset,andgiveatableshowingtheedge-endpointfunction.vertexset={v1,v2,v3,v4,v5,v6}edgeset={e1,e2,e3,e4,e5,e6,e7}6Example11.1.1Forthegraphpedge-endpointfunction:e1{v1,v2}e2{v1,v3}e3{v1,v3}e4{v2,v3}e5{v5,v6}e6{v5}e7{v6}7edge-endpointfunction:7b.Find…Edgesthatareincidentonv1:e1,e2,e3Verticesthatareadjacenttov1:v2,v3Edgesthatareadjacenttoe1:e2,e3,e4Allloops:e6,e78b.Find…EdgesthatareincideAllparalleledges:e2ande3Allverticesthatareadjacenttothemselves:v5,v6Allisolatedvertices.v49Allparalleledges:9Example11.1.2Considerthegraphspecifiedasfollows:vertexset={v1,v2,v3.v4}edgeset={e1,e2,e3,e4}edge-endpointfunction:

e1{v1,v2}

e2{v2,v4}

e3{v2,v4}

e4{v3}Drawthegraph.10Example11.1.2ConsiderthegrExample11.1.3Considerthetwodrawingsbelow.Labelverticesandedgesinsuchawaythatbothdrawingrepresentthesamegraph.11Example11.1.311DefinitionAdirectedgraph,ordigraph,consiststwofinitesets:asetV(G)ofverticesandasetE(G)ofdirectededges,whereeachedgeisassociatedwithanorderedpairofverticescalleditsendpoints.Ifedgeeisassociatedwiththepair(v,w)ofvertices,theneissaidtobethe(directed)edgefromvtow.12Definition12Example11.1.4Computer,telephone,electricpower,gaspipeline,andairtransportsystemscanallrepresentedbygraphs.Questionsthatariseinthedesignofsuchsystemsinvolvechoosingconnectingedgestominimizecost,optimizeacertaintypeofservice,andsoforth.Examplesofgraphs13Example11.1.4Computer,teleAtypicalcommunicationsystemisshownatthemiddleofPage654.AlsoseetheExample11.1.514AtypicalcommunicationsySpecialGraphsDefinitionAsimplegraphisagraphthatdoesnothaveanyloopsorparalleledges.Inasimplegraph,anedgewithend-pointsvandwisdenoted{v,

w}15SpecialGraphsDefinition15Example11.1.7

Drawallsimplegraphswiththefourvertices{u,v,w,x}andtwoedges,oneofwhichis{u,v}16Example11.1.716DefinitionAcompletegraph

onnvertices,denotedKn,isasimplegraphwithnverticesv1,v2,…,vn

whosesetofedgescontainsexactlyoneedgeforeachpairofdistinctvertices.Example11.1.8DrawKn,n=2,3,4,5.17DefinitionExample11.1.8171818DefinitionAcompletebipartitegraphon(m,n)vertices,denotedKm,n,isasimplegraphwithmverticesv1,v2,…,vm

andnedgesw1,w2,…,wnthatsatisfiesthefollowingproperties:1.Thereisanedgefromeachvitoeachwj2.Thereisnoedgefromeachvitoanyvk3.Thereisnoedgefromeachwjtoanywl19Definition19Example11.1.9

DrawK3,2andK3,3.20Example11.1.920DefinitionAgraphHissaidtobeasubgraphofagraphGif,andonlyif,everyvertexinHisalsoavertexinG,everyedgeinHisalsoanedgeinG,andeveryedgeinHhasthesameend-pointsasinG.21Definition21Example11.1.10ListallnonemptysubgraphsofthegraphGwithvertexset{v1,v2},edgeset{e1,e2,e3},wheretheendpointsofe1arev1andv2,theendpointofe2arev1andv2,ande3isaloopatv1.22Example11.1.10222323DegreeDefinitionLetGbeagraphandvavertexofG.Thedegree

ofv,denoteddeg(v),equalsthenumberofedgesthatareincidentonv,withanedgethatisaloopcountedtwice.ThetotaldegreeofGisthesumofthedegreesofalltheverticesofG.24DegreeDefinition24Example11.1.11FindthedegreeofeachvertexofthegraphGbelow.ThenfindthetotaldegreeofG.Solution.deg(v1)=0deg(v2)=2deg(v3)=425Example11.1.11Solution.Theorem11.1.1Iftheverticesof

agraphGarev1,v2,…,vn,wherenisapositiveinteger,thenthetotaldegreeofG

=deg(v1)+deg(v2)+…+deg(vn)=2·(theNo.ofedgesofG)Corollary11.1.1ThetotaldegreeofagraphGiseven.26Theorem11.1.1IftheverticesExample11.1.12Drawagraphwiththespecifiedpropertiesorshowthatnosuchgraphexists.a.Graphwithfourverticesofdegrees1,1,2,and3.Solution.Nosuchgraphispossible.Sincethetotaldegreeofagraphiseven.Butagraphwithfourverticesofdegrees1,1,2,and3wouldhaveatotaldegreeof7,whichisodd.27Example11.1.12Solution.27b.Graphwithfourverticesofdegrees1,1,3,and3.Solution.28b.Graphwithfourverticesc.Simplegraphwithfourverticesofdegrees1,1,3,and3.Solution.Nosuchgraphexists.Supposenot.Thatis,thereisasimplegraphwithfourverticesofdegrees1,1,3,and3…29c.SimplegraphwithfourvertExample11.1.13Isitpossibleinagroupofninepeopleforeachtobefriendswithexactlyfiveothers?Proposition11.1.3Inanygraphthereareanevennumberofverticesofodddegree.30Example11.1.13IsitpossiblSolution.No.Suchagraphwouldhavethreeverticesofodddegree,whichisimpossible.Example11.1.14Isthereagraphwithtenverticesofdegrees1,1,2,2,2,3,4,4,4,and6?31Solution.No.SuchagraphwouQuestions:665:1,5,8,9,

12,15,16,19,22,24a,25a,28.Assignments:

665:4,21,23.32Questions:665:1,5,11.2PathsandCircuitsDefinitionLetv,wbeverticesinagraphG.Awalk

fromvtowisafinitealternatingsequenceofadjacentverticesandedgesofGwith

theformv0e1v1e2v2…vn-1envnwherethev’srepresentvertices,thee’srepresentedges,v0=v,vn=w,andforalli=1,2,…,n,vi-1andviaretheendpointsofei.Thetrivialwalkfromvtovconsistsofthesinglevertex.(tobecontinued)3311.2PathsandCircuitsDefinDefinition(continued)Apath

fromvtowisawalkfromvtowthatdoesn’tcontainarepeatededge.Thusapathfromvtowisawalkoftheformv=v0e1v1e2v2…vn-1envn=wwherealltheeiaredistinct(thatis,ei≠ek

foranyi≠k).Asimplepath

fromvtowisapathdoesnotcontainarepeatedvertex.(tobecontinued)34Definition(continued)34Definition(continued)Aclosedwalk

isawalkthatstartsandendsatthesamevertex.Acircuit

isaclosedwalkthatdoesnotcontainarepeatededge.Asimplecircuit

isacircuitthatdoesnothaveanyotherrepeatedvertexexceptthefirstandlast.35Definition(continued)AciExample11.2.1a.Inthegraphbelow,thenotatione1e2e4e3refersunambiguouslytothewalkv1e1v2e2v3e4v3e3v2.Ontheotherhand,thenotatione1isambiguousifusedtorefertoawalk.Itcouldmeaneitherv1e1v2orv2e1v1.36Example11.2.136b.Inthegraphabove,thenotationv2v3isambiguousifusedtorefertoawalk.Itcouldmeanv2e2v3orv2e3v3.Inthegraphbelow,thenotationv1v2v2v3refersunambiguouslytothewalkv1e1v2e2

v2e3v3.37b.Inthegraphabove,theExample11.2.2Inthegraphbelow,determinewhichofthefollowingwalksarepaths,simplepaths,circuits,andsimplecircuits:a.

v1e1v2e3v3e4v3e5v4b.

e1e3e5e5e6c.

v2v3v4v5v3v6v2d.

v2v3v4v5v6v2

e.

v2v3v4v5v6v3v2

f.

v1pathwalkcircuitsimplecircuitclosedwalktrivalwalk38Example11.2.2InthegraphConnectednessDefinitionLetGbeagraph.TwoverticesvandwofGareconnectedif,andonlyif,thereisawalkfromvtow.AgraphGiscalledconnectedif,andonlyif,foranytwoverticesofGtheyareconnected.39ConnectednessDefinition39Example11.2.3Whichofthegraphsbelowisconnected?40Example11.2.340Lemma11.2.1

LetGbeagraph.

a.IfGisconnected,thenanytwodistinctverticesofGcanbeconnectedbyasimplepath.b.IfvandwareverticesofacircuitinGandoneedgeisremovedfromthecircuit,thentherestillexistsapathfromvtow.c.IfGisconnectedandcontainsanon-trivialcircuit,thenanedgeofthecircuitcanberemovedwithoutdisconnectingG.41Lemma11.2.1LetGbeagraph.DefinitionAgraphHisaconnectedcomponentofagraphGif,andonlyif,HissubgraphofG;Hisconnected;andnoconnectedsubgraphofGhasHasasubgraphandcontainsverticesoredgesthatarenotinH.42Definition42Example11.2.4FindallconnectedcomponentsofthegraphGbelow.43Example11.2.4FindallconnEulerCircuitsDefinitionLetGbeagraph.AnEulercircuitforGisacircuitthatcontainseveryvertexandeveryedgeofG.Theorem11.2.2IfagraphhasEulercircuit,theneveryvertexofthegraphhasevendegree.IfsomevertexofagraphhasodddegreethenthegraphhasnoEulercircuit.44EulerCircuitsDefinitionLetExample11.2.5ShowthatthegraphbelowdosenothaveanEulercircuit.45Example11.2.5ShowthatthegTheorem11.2.3Ifeveryvertexofanonemptygraphhasevendegreeandifthegraphisconnected,thenthegraphhasanEulercircuit.Proof.SupposethatGisanynonemptyconnectedgraphandthateveryvertexofGhasevendegree.IfGconsistsofasinglevertexv,thetrivialwalkfromvtovisanEulercircuit.Otherwise,constructacircuitCbythefollowing46Theorem11.2.3IfeveryverteStep2:Pickanysequenceofadjacentverticesandedges,startingandendingatvandneverrepeatinganedge.CalltheresultingcircuitC.Step3:CheckwhetherCcontainseveryedgeandvertexofG.Ifso,CisanEulercircuit,andwearefinished.Ifnot,performthefollowingsteps.Step1:PickanyvertexvofGatwhichtostart.47Step2:PickanysequenceofaStep3c:PickanysequenceofadjacentverticesandedgesofG’,startingandendingatwandneverrepeatinganedge.CalltheresultingcircuitC’.Step3a:RemovealledgesofCfromGandalsoanyverticesthatbecomeisolatedwhentheedgesofCareremoved.CalltheresultingsubgraphG’.Step3b:PickanyvertexwcommontobothCandG’.48Step3c:PickanysequenceofStep3d:PatchCandC’togethertocreateanewcircuitC’’asfollows:startatvandfollowCallthewaytothew.ThenfollowC’allthewaybacktow.Afterthat,continuealongtheuntraveledportionofCtoreturnv.SincethegraphGisfinite,executionofthestepsoutlinedinthealgorithmmusteventuallyterminate.AtthatpointanEulercircuitforGwillhavebeenconstructed.Step3e:LetC=C’’andgobacktoStep3.49Step3d:PatchCandC’togethExample11.2.6UseTheorem11.2.3tocheckthatthegraphbelowhasanEulercircuit.ThenusethealgorithmfromtheproofoftheTheoremtofindanEulercircuitforthegraph.50Example11.2.6UseTheorem1Solution.

(1)abcda(2)dehjid51Solution.(2)dehjid51(3)=(1)+(2)abcdehjida(4)=(1)+(2)hfegh52(3)=(1)+(2)abcdehjida(4)=(1)(5)=(3)+(4)abcdehfeghjida53(5)=(3)+(4)abcdehfeghjida53Definition

LetGbeagraphandletvandwbetwodistinctverticesofG.AnEulerpathfromvtowisasequenceofadjacentedgesandverticesthatstartsatv,endsatw,passesthrougheveryvertexofGatleastonce,andtraverseseveryedgeofGexactlyonce.Theorem11.2.4AgraphGhasanEulercircuitif,andonlyif,GisconnectedandeveryvertexofGhasevendegree.54DefinitionTheorem11.2.4AgrCorollary11.2.5

LetGbeagraphandletvandwbetwodistinctverticesofG.ThereisanEulerpathfromvtowif,andonlyif,Gisconnected,vandwhaveodddegree,and

everyothervertexofGhasevendegree.55Corollary11.2.555Example11.2.7ThefloorplanshownatthebottomonPage676isforahousethatisopenforpublicviewing.IsitpossibletofindapaththatstartsinroomA,endsinroomB,andpassesthrougheveryinteriordoorwayofthehouseexactlyonce?Ifso,findthepath.56Example11.2.7565757HamiltonCircuitsDefinitionLetGbeagraph.AnHamiltoncircuitforGisasimplecircuitthatcontainseveryvertexofG.58HamiltonCircuitsDefinition58Proposition11.2.6LetGbeagraphwithatleasttwovertices.IfGhasaHamiltoncircuitthenGhasasubgraphHwiththefollowingproperties:1.

HcontainseveryvertexofG;2.

Hisconnected;3.

Hhasthesamenumberofedgesasvertices;4.EveryvertexofHhasdegree2.59Proposition11.2.659Example11.2.8ProvethatthegraphGbelowdoesnothaveaHamiltoncircuit.60Example11.2.860Example11.2.9Imaginethatthedrawingbelowisamapshowingfourcitiesandthedistanceinkilometersbetweenthem.Supposethatasalespersonmusttraveltoeachcityexactlyonce,startingandendinginCityv1.Whichroutefromcitytocitywillminimizethetotaldistancethatmustbetraveled?61Example11.2.961Questions:Page679–683:1,4,6a,9a,12,14,19.Assignments:

Page679–683:9bc,15*,18*.62Questions:Page679–683:1,4,11.3MatrixRepresentationsofGraphsMatricesanddirectedgraphsDefinitionLetGbeadirectedgraphwithorderedverticesv1,v2,…,vn.TheadjacencymatrixofGisthematrixA=(aij)overthesetofnonnegativeintegerssuchthataij=No.ofarrowsfromvitovjforalli,j=1,2,…,n.6311.3MatrixRepresentationsExample11.3.2Thetwodirectedgraphsbelowdifferonlyinorderingoftheirvertices.Findtheiradjacencymatrices.64Example11.3.2ThetwodirecteExample11.3.3LetDrawadirectedgraphhavingAasitsadjacencymatrix.65Example11.3.3LetDrawadirMatricesand(undirected)graphsDefinitionLetGbea(undirected)graphwithorderedverticesv1,v2,…,vn.TheadjacencymatrixofGisthematrixA=(aij)overthesetofnonnegativeintegerssuchthataij=No.ofedgesconnectingviandvj

foralli,j=1,2,…,n.66Matricesand(undirected)grapExample11.3.4Findtheiradjacencymatrixforthegraphbelow.67Example11.3.467CountingWalksofLengthNDefinitionA

walkinagraphconsistsofanalternatingsequenceofverticesandedges.Ifrepeatededgesarecountedeachtimetheyoccur.Thenthenumberofedgesinthesequenceiscalledthelengthofthewalk.68CountingWalksofLengthNDefiTheorem11.3.2IfGisagraphwithv1,v2,…,vnandAistheadjacencymatrixofG,thenforeachpositiveintegerm,Theaij-thentryofAm=No.ofwalksoflengthmfromvitovjforalli,j=1,2,…,n.69Theorem11.3.269Assignments:

Page695–6972(a),3(a),4(a),5(a).70Assignments:Page695–6972(a)11.5TreesDefinitionAgraphissaidtobe

circuit-freeif,andonlyif,ithasnonontrivialcircuits.Agraphiscalleda

tree

if,andonlyif,itiscircuit-freeandconnected.7111.5TreesDefinition71DefinitionAtrivialtreeisagraphthatconsistsofasinglevertex,andanemptytreeisatreethatdosenothaveanyverticesoredges.Agraphiscalleda

forestif,andonlyif,itiscircuit-free.72Definition72Example11.5.1Whichgraphsbelowaretreesorarenottrees?73Example11.5.1737474CharacterizingTreesLemma11.5.1Anytreethathasmorethanonevertexhasatleastonevertexofdegree1.Proof.

v1

v2

v3

v4

vn

75CharacterizingTreesLemma11.DefinitionLetTbeatree.Avertexofdegree1inTiscalledaterminalvertex(oraleaf

).Andavertexofdegreegreaterthan1inTiscalledaninternalvertex(orabranchvertex).76Definition76Example11.5.5Findallterminalverticesandallinternalverticesinthetreebelow.77Example11.5.577Theorem11.5.2Foranypositiveintegern,anytreewithnverticeshasn

1edges.Proof.MathematicalInductionandLemma11.5.1.78Theorem11.5.2Proof.MathematiExample11.5.6AgraphGhastenverticesandtwelveedges,Isitatree?Solution.No.Sinceanytreewithtenverticeshasnineedges,nottwelve.79Example11.5.6Solution.79Lemma11.5.3

IfGisanyconnectedgraph,CisanynontrivialcircuitinG,andoneoftheedgesofCisremovedfromG,thenthegraphthatremainsisconnected.Proof.

80Lemma11.5.3IfGisanyconneTheorem11.5.4Foranypositiveintegern,ifGisaconnectedgraphwithnverticesandn-1edges,thenGisatree.Proof.LetnbeapositiveintegerandsupposeGisaparticularbutarbitrarychosengraphthatisconnectedandhasnverticesandn-1edges.SupposeGisnotcircuit-free.Thatis,supposeGhasanontrivalcircuitC.81Theorem11.5.4ForanypositBylemma,anedgeofCcanberemovedfromGtoobtainagraphG’thatisconnected.IfG’hasanontrivialcircuit,

thenrepeat

thisprocess:removeanedgeofthecircuitfromG’toformanewconnectedgraph.

ContinuerepeatingtheprocessofremovingedgesfromcircuitsuntileventuallyagraphG’’isobtainedthatisconnectedandiscircuit-free.82Bylemma,anedgeofCcanBydefinition,G’’isatree.SincenoverticeswereremovedfromGtoformG’’,G’’hasnverticesjustasGdoes.Thus,G’’hasn-1edges.ButthesuppositionthatGhasanontrivalcircuitimpliesthatatleastoneedgeofGisremovedtoformG’’.HenceG’’hasnomorethan

(n-1)-1=n-2edges,whichcontradictsitshavingn-1edges.Sothesuppositionisfalse.HenceGiscircuit-free,andthereforeGisatree.83Bydefinition,G’’isatrExample11.5.8Giveanexampleofagraphwithfiveverticesand4edgesthatisnotatree.Solution.84Example11.5.8GiveanexampleQuestions:722:17,

22,25,27.Assignments:

722:15,16,18,19.85Questions:722:17,211.6SpanningTreesProposition

1.Everyconnectedgraphhasaspanningtree.

2.Anytwospanningtreeforagraphhavethesamenumberofedges.DefinitionAspanningtreeforagraphisa

subgraphofGthatcontainseveryvertexofGandisatree.8611.6SpanningTreesPropositiExample11.6.2Findingallspanningtreesforthefollowinggraph.87Example11.6.2Findingallspa8888DefinitionAweightedgraphisagraphforwhicheachedgehasanassociatedrealnumberweight.Thesumoftheweightsofalltheedgesisthetotalweightofthegraph.IfGisaweightedgraphandeisanedgeofG,thenw(e)denotestheweightofeandw(G)denotesthetotalweightofG.89Definition89DefinitionAminimumspanningtree(MST)foraweightedgraphisaspanningtreethathastheleastpossibletotalweightcomparedtoallotherspanningtreesforthegraph.90Definition90Kruskal’sAlgorithmInput:G[aweightedgraphwithnvertices]AlgorithmBody:[BuildasubgraphTofGtoconsistofalltheverticesofGwithedgesaddedinorderofincreasingweight.Ateachstage,letmbethenumberofedgeofT]Step1.InitializeTtohavealltheverticesofGandnoedges.91Kruskal’sAlgorithm91Step2.LetEbethesetofalledgesofG,andletm:=0.[pre-condition:Gisconnected.]Step3.while(m<n-1)3-1.Find

anedgeeinEofleastweight.3-2.Delete

efromE.3-3.ifadditionofetotheedgesetofTdoesnotproduceacircuit,then

add

etotheedgesetofTandsetm:=m+1

endwhile92Step2.LetEbethesetofal[post-condition:TisaminimumspanningTreeforG]Output:T93[post-condition:TisaExample11.6.4UsingKruskal’salgorithmstofindtheminimumspanningtreeofthefollowinggraph.94Example11.6.4UsingKruskal’sKruskal’sAlgorithm95Kruskal’sAlgorithm9596969797Solution.WhenKruskal’salgorithmisapplied,edgesareaddedinthefollowingorder:{d,f},{a,c},{b,c},{c,d},{d,e}.Andtheminimumspanningtreeiswhichweightis15.98Solution.WhenKruskal’salgorPrim’sAlgorithmInput:G[aweightedgraphwithnvertices]AlgorithmBody:[BuildasubgraphTofGbystartinganyvertexvofGandattachingedges(withtheirendpoints)onebyonetoanas-yet-unconnectedvertexofT,eachtimechoosinganadjacentedgeofleast]Step1.PickavertexvofGandletTbethegraphwithonevertex,v,andnoedges.99Prim’sAlgorithm99Step2.LetVbethesetofallverticesofGexceptv.[pre-condition:Gisconnected.]Step3.for

i:=1ton-13-1.FindanedgeeinGsuchthat:

(1)econnectsTtooneoftheverticesinV,(2)ehastheleastweightofalledgesconnectingTtoavertexinV.LetwbetheendpointsofethatisinV.3-2.Add

eandwtotheedgeandvertexsetsofT,anddelete

wfromV.

next

i100Step2.LetVbethesetofal[post-condition:TisaminimumspanningTreeforG]Output:T101[post-condition:TExample11.6.4UsingPrim’salgorithmsstartingatvertexatofindtheminimumspanningtreeofthefollowinggraph.102Example11.6.4UsingPrim’salPrim’sAlgorithm103Prim’sAlgorithm103104104Solution.WhenPrim’salgorithmisappliedstartingata,edgesareaddedinthefollowingorder:{a,c},{b,c},{d,c},{d,f},{d,e}.Andtheminimumspanningtreeiswhichweightis15.105Solution.WhenPrim’salgorithQuestions:733:1,3,27.Assignments:

733:5,7.106Questions:733:1,3,TheLastChapter:GroupsandFieldsunderstandthedefinitionsofgroup,abeliangroup,subgroup,cyclicgroup,generator,andorderofanelement;determinewhetheragivensetandbinaryoperationformagroupofabeliangroup;107TheLastChapter:GroupsandFdeterminewhetheragivengroupHisasubgroupofagivengroupG;findtheorderoftheelementofagivengroup;understandthedefinitionofafield.108determinewhetheragivengrouG.1DefinitionandexamplesDefinitionG.1.1

Agroup(G,

)isanonemptysetGtogetherwithabinaryoperationonG,suchthat:forallg,h

G,g

h

G;forallg,h,k

G,(g

h)k=g(h

k)G,thatisisassociative;Tobecontinued109G.1DefinitionandexamplesDeContinued

thereisanelemente

G,suchthatforallg

G,

g

e=e

g=g,thatisGhasanidentity;forallg

G,thereisg1

G,suchthatg

g1

=e=g1

g,thatisghasaninverseelement.110Continued110ExampleG.1.2Recalltheequivalencerelation

onZ:xy

x

y(mod6)Theequivalenceclassesforthisrelationarethesets[0]6,[1]6,[2]6,[3]6,[4]6,[5]6.InthiswaythesetofequivalenceclassesisidentifiedwiththesetZ6={0,1,2,3,4,5}.WemaydefineabinaryoperationonZ6asfollows:x

y=z

z

x+y(mod6)Provethat(Z6,)isagroup.111ExampleG.1.2RecalltheequivExampleG.1.3LetBbethesetofall0-1stringsoflengthn.Defineanbinaryoperation

onBasfollows:Leta=a1a2…anandb=b1b2…bnwithai=0or1,andbi=0or1,i=1,2,…,n.Definea

b=c1c2…cn,whereProvethat(B,)isagroup.

112ExampleG.1.3LetBbethesetExampleG.1.