GT-lec2-introduction-v10.ppt

1、图论及其应用Graph Theory and Its Applications,郭宇春 Dept. Comm. Eng., School of EIE, BJTU ,Lecture 2. Introduction,Birth of Graph theory Applications of Graph theory Developments in Graph theory,3,2020/7/21,Graph Theory with Applications_Y.GUO,Seven Bridges of Knigsberg Problem,Knigsberg (哥尼斯堡, now Kalining

2、rad) , 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.,4,2020/7/21,Graph Theory with Applications_Y.GUO,Leonhard Euler,Leonhar

3、d 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 plac

4、es.) Can you see why?,Picture only what is essential to the problem.,5,2020/7/21,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 i

5、n Mathematics,father of graph theory,6,2020/7/21,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,2020/7/21,Graph Theory with Applications_Y.GUO,Todays Bridges of Knigsb

6、erg,Bridge 1,8,2020/7/21,Graph Theory with Applications_Y.GUO,Todays Bridges of Knigsberg,Bridge 2,9,2020/7/21,Graph Theory with Applications_Y.GUO,Todays Bridges of Knigsberg,Bridge 3,10,2020/7/21,Graph Theory with Applications_Y.GUO,Todays Bridges of Knigsberg,Bridge 4,11,2020/7/21,Graph Theory wi

7、th Applications_Y.GUO,Todays Bridges of Knigsberg,Bridge 5,12,2020/7/21,Graph Theory with Applications_Y.GUO,Todays Bridges of Knigsberg,Bridge 6,13,2020/7/21,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

8、 Nature. First theoretic book Hnig,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.”,14,2020/7/21,Graph Theor

9、y 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.

10、 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 gener

11、alization 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.,15,2020/7/21,Gra

12、ph 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 differe

13、nt 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 co

14、mmunity. 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

15、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

16、, the extremal graph theory.,16,2020/7/21,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

17、 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,17,2020/7/21,Graph Theory with Applications_Y.GUO,Subareas of Graph theory,Algebraic graph theory Geometric graph theory Extr

18、emal graph theory Metric graph theory Probabilistic graph theory Topological graph theory Spectrum graph theory Hyper-graph theory ,18,2020/7/21,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

19、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,19,2020/7/21

20、,Graph Theory with Applications_Y.GUO,Internet: ip-level,(William R. Cheswick),20,2020/7/21,Graph Theory with Applications_Y.GUO,www,(K. C. Claffy),21,2020/7/21,Graph Theory with Applications_Y.GUO,Telecomm Networks,(Stephen G. Eick),22,2020/7/21,Graph Theory with Applications_Y.GUO,VLSI Circuits,23

21、,2020/7/21,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,24,2020/7/21,Graph Theory with Applications_Y.

22、GUO,Developments in Graph theory,The introduction of probabilistic methods in graph theory, specially in the study of Paul Erds and Alfred Rnyi of the asymptotic probability of graph connectivity is at the origin of yet another branch, known as random graph theory (1960).,Paul Erds (1913-1996) Olive

23、r 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 i

24、s usually indispensable to a human life. - The Man Who Loved Only Numbers (Paul Hoffman, 1998),25,2020/7/21,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 years old Main contribut

25、ions 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 collabora

26、tors could claim an Erds number of 1 their collaborators have Erds number at most 2, and so on.,26,2020/7/21,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 wha