资源描述：
《networks and graphs》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、Chapter6NetworksandgraphsHownetworkscangrowaccordingtodi erentrules:butintheendtherichgetricher.1Thewordnetworkcoversawealthofdi erentmeanings,fromsubterraneanfungalinterconnectionsstudiedinbiologytohumaninteractionsstudiedbysocialscientists.Ourmaininterestsrangefromthephysical
2、structureofcom-puternetworkstothelogicalstructureoftheWeb,butallnetworkssharesomeessentialconceptsandproperties,andgraphtheoryisthestandardmathe-maticaltoolforstudyingthemall.Sowestartbylookingatgraphsinsomedetail.Wehavealreadyseenthatagraphisamathematicalobjectconsistingofaset
3、ofnodesandasetofarcsconnectingpairsofnodestogether.Thearcs(andconsequentlythegraph)canbedirectedornot.Graphically,nodesarerepresentedwithdotsandarcsarerepresentedeitherwitharrowsifthegraphisdirectedorwithlinesegmentsifthegraphisundirected.Figure6.1(a)showsanundirectedgraph.Sinc
4、eincomputermemorythestoryvaries,weshallusewhicheveristhemostconvenientrepresentation.Themainparametersofagrapharethenumberofnodesnandthenumberofarcsm.Therecannotbemorearcsthantherearepairsofnodes.Further-more,ifthegraphisstronglyconnected,thatisifeverynodecanbereachedfromanyoth
5、ernode,thenthearcscannotbetoofew.Inthiscasewehave:n 1mn(n 1)=2inanundirectedgraph(ifthelowerboundm=n 1ismetthegraphisatree,seeChapter3);and2(n 1)mn(n 1)inadirectedgraph.Inanycase,thenumberofarcsspansfromalinearfunctionofn(sparsegraph)toaquadraticfunctionofn(densegraph).Note
6、thatdensegraphsdonotreallyarisewhenmodelingrealphenomenaofverylargesize.Ifthenumberofnodeskeepsincreasing,itisnotthecasethatthenumberofconnectionstoanodemayalsoincreasebeyondagivenbound,whatevertheseconnectionsmayrepresent.Inparticular,ifthestructureofthe1Thischapteristhemostma
7、thematicalinnatureandhasbeenincludedtoallowadeeperunderstandingofthefollowingchapters.Readerswithaseriousallergytomathematicsmayjumptothenextchapterdirectly.Itgoeswithoutsaying,however,thattheywillmisssomethinginteresting.99©2012byTaylor&FrancisGroup,LLC100MathematicalandAlgori
8、thmicFoundationsoftheInternet121263635454FIGURE6.1:(a)
