GT-lec2-introduction-v10.ppt

,*,*,Graph Theory with Applications_Y.GUO,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,图论及其应用,Graph Theory and Its Applications,郭宇春,Dept.Comm.Eng.,School of EIE,BJTU,ychguo,Lecture 2,.Introduction,Birth of Graph theory,Applications of Graph theory,Developments in Graph theory,Seven Bridges of Knigsberg,Problem,Knigsberg,(,哥尼斯堡,now Kaliningrad),Germany,seven bridges over the,Pregel,river,18th century,The residents of,Knigsberg,wondered,if it was possible to take a walking tour of the town that crossed each of the seven bridges over the,Pregel,river exactly once.,7/7/2026,3,Graph Theory with Applications_Y.GUO,Leonhard,Euler,Leonhard Euler,solved this,Seven,Bridges of,Knigsberg,and published his research in,1736,.This paper is regarded as the first paper in the history of,graph theory,as a subject.,Eulers Answer:There is no tour that uses each edge exactly once.(Even if we allow the walk to start and finish in different places.),Can you see why?,C,D,B,A,A,B,C,D,Picture only what is essential to the problem.,7/7/2026,4,Graph Theory with Applications_Y.GUO,Leonhard,Euler,(1707-1783),Born April 15,1707 in Basel,Switzerland,University of Basel in 1720 at age 14,1723 completed Masters degree in Philosophy,1726 completed Masters degree in Mathematics,father of graph theory,7/7/2026,5,Graph Theory with Applications_Y.GUO,Todays,Bridges of,Knigsberg,A map of,Knigsberg,(Kaliningrad,as it is now called)after its rebuilding after its destruction in World War II,7/7/2026,6,Graph Theory with Applications_Y.GUO,Todays,Bridges of,Knigsberg,Bridge 1,7/7/2026,7,Graph Theory with Applications_Y.GUO,Todays,Bridges of,Knigsberg,Bridge 2,7/7/2026,8,Graph Theory with Applications_Y.GUO,Todays,Bridges of,Knigsberg,Bridge 3,7/7/2026,9,Graph Theory with Applications_Y.GUO,Todays,Bridges of,Knigsberg,Bridge 4,7/7/2026,10,Graph Theory with Applications_Y.GUO,Todays,Bridges of,Knigsberg,Bridge 5,7/7/2026,11,Graph Theory with Applications_Y.GUO,Todays,Bridges of,Knigsberg,Bridge 6,7/7/2026,12,Graph Theory with Applications_Y.GUO,Birth of Graph theory,The term of,graph,has been introduced by,Sylvester,in a paper published in 1878 in,Nature,.,First theoretic book,H,nig,D,.,Theorie,der,Endliche,und,Unendliche,Graphen,Leipzig,Akademishe,Verlagsgesellshaft,1936,What is,graph theory,?,“Graph theory is the study of mathematical objects(graphs)that are made of dots that may or may not be connected by lines.”,7/7/2026,13,Graph Theory with Applications_Y.GUO,History&application,More than one century after Eulers paper on the bridges of,Knigsberg,and while,Listing,introduced topology,Cayley,were led by the study of particular analytical forms arising from,differential calculus,to study a particular class of graphs,the,trees,.This study had many implications in theoretical,chemistry,.,The involved techniques mainly concerned the enumeration of graphs having particular properties.,Enumerative graph theory,then rose from the results of,Cayley,and the fundamental results published by,Plya,between 1935 and 1937 and the generalization of these by,De,Bruijn,in 1959.,Cayley,linked his results on,trees,with the contemporary studies of chemical composition.,The fusion of the ideas coming from mathematics with those coming from chemistry is at the origin of a part of the standard terminology of graph theory.,7/7/2026,14,Graph Theory with Applications_Y.GUO,History&application,One of the most famous and productive problem of graph theory is the,four color problem,:,Is it true than any map drawn in the plane may,habe,its regions colored with four colors,in such a way that two regions having a common border get different color?.,This problem remained unsolved for more than one century and the proof given by,Kenneth,Appel,and,Wolfgang,Haken,in 1976(determination of 1936 types of configurations which study is sufficient and checking of the properties of these configurations by computer)did not convince all the community.A simpler proof considering far less configurations has been given twenty years later by,Robertson,Seymour,Sanders,and,Thomas,.,The study and the generalization of this problem by,Tait,Heawood,Ramsey,and,Hadwiger,has in particular led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus.,Taits,reformulation generated a new class of problems,the,factorization problems,particularly studied by,Petersen,and,Knig,.The works of Ramsey on colorations and more specially the results,otained,by,Turn,in 1941 is at the origin of another branch of graph theory,the,extremal,graph theory,.,7/7/2026,15,Graph Theory with Applications_Y.GUO,History&application,Another important factor of common development of graph theory and topology came from the use of the techniques of modern algebra.The first example of such a use comes from the work of the physician,Gustav Kirchhoff,who published in,1845,his,Kirchhoffs circuit laws,for calculating the,voltage,and,current,in,electric circuits,.,1950s,1960s,boost in Graph theory research,7/7/2026,16,Graph Theory with Applications_Y.GUO,Subareas,of Graph theory,Algebraic graph theory,Geometric graph theory,Extremal,graph theory,Metric graph theory,Probabilistic graph theory,Topological graph theory,Spectrum graph theory,Hyper-graph theory,7/7/2026,17,Graph Theory with Applications_Y.GUO,Why we are here?,We need this theory for our research on communication and networking and,A,network,is a set of,nodes,interconnected via,links,Examples,:,Internet:,Nodes,routers,Links,optical fibers,WWW:,Nodes,document files,Links,hyperlinks,Scientific Citation Network:,Nodes,papers,Links,citation,Social Networks:,Nodes,individuals,Links,relations,Nodes,and,Links,can be anything depending on the context,7/7/2026,18,Graph Theory with Applications_Y.GUO,Internet:,ip,-level,(William R.Cheswick),7/7/2026,19,Graph Theory with Applications_Y.GUO,www,(K.C.,Claffy,),7/7/2026,20,Graph Theory with Applications_Y.GUO,Telecomm Networks,(Stephen G.,Eick,),7/7/2026,21,Graph Theory with Applications_Y.GUO,VLSI Circuits,7/7/2026,22,Graph Theory with Applications_Y.GUO,Simple Network,vs,Complex Network,Simple,Network,Complex,Network,Lots of networks in reality,Non-trivial topological properties,Scale-Free Network,Power-law exponents between 2 and 3,Network Theory/Science,7/7/2026,23,Graph Theory with Applications_Y.GUO,Developments in Graph theory,The introduction of probabilistic methods in graph theory,specially in the study of,Paul,Erd,s,and,Alfred,R,nyi,of the asymptotic probability of graph connectivity is at the origin of yet another branch,known as,random graph theory,(1960).,Paul,Erd,s,(1913-1996),Oliver Sacks:,A mathematical genius of the first order,Paul,Erds,was totally obsessed with his subject-he thought and wrote mathematics for nineteen hours a day until the day he died.,He traveled constantly,living out of a plastic bag,and had no interest in food,sex,companionship,art,-all that is usually indispensable to a human life.-,The Man Who Loved Only Numbers(Paul Hoffman,1998),7/7/2026,24,Graph Theory with Applications_Y.GUO,Erds,Number,Erds,Number,Erds,published,1,600 papers,with,500 coauthors,in his life time,Published,2 papers per month,from 20,to 83,year,s,old,Main contributions,in modern mathematics:Ramsey theory,graph theory,Diophantine analysis,additive number theory and prime number theory,Because of his prolific output,friends created the,Erds,number,as a humorous tribute,Erds,alone was assigned the,Erds,number of 0(for being himself,his immediate collaborators could claim an,Erds,number of 1,their collaborators have,Erds,number at most 2,and so on.,7/7/2026,25,Graph Theory with Applications_Y.GUO,Erds,Number,Some have estimated that 90 percent of the worlds active mathematicians have an,Erds,number smaller than 8(not surprising in light of the small world phenomenon).,The,Erds,number was most likely first defined by Casper,Goffman,an analyst whose own,Erds,number is 1.,Goffman,published his observations about,Erds,prolific collaboration in a 1969 article entitled And what is your,Erds,number?,7/7/2026,26,Graph Theory with Applications_Y.GUO,Erds,Number,the Fields award owners had,Erds,number not larger than 5(and only Cohen and,Grothendieck,were with,Erds,number 5),the,Nevanlinna,award owners,Erdos,had,Erds,number not larger than 3(and only Valiant,Erds,number was 3),the Wolf mathematics award owners had,Erds,numbers not larger than 6,，,(and only V.I.Arnold,Erds,number was 6 and,Kolmogorovs,was 5),the Steele lifetime achievements award owners had,Erds,number not larger than 4.,People in other areas:,Bill Gates,Erds,number is 4 with the path,Erds,-,Pavol,Hell-Xiao Tie Deng-,Christos,H.Papadimitriou-William H.(Bill)Gates.,Einstein:2.,7/7/2026,27,Graph Theory with Applications_Y.GUO,Erds,Number,Erds,had a(,scale-free,),small-world network,of mathematical research collaboration,Science collaboration network,Author-node,Paper coauthored-link,7/7/2026,28,Graph Theory with Applications_Y.GUO,