图论及其应用 Graph Theory and Its Applications

郭宇春 Dept. Comm. Eng., School of EIE, BJTU ychguo@bjtu.edu.cn

Lecture 2. Introduction

1. Birth of Graph theory 2. Applications of Graph theory 3. Developments in Graph theory

Seven Bridges of K?nigsberg Problem

K?nigsberg (哥尼斯堡, now Kaliningrad) , Germany seven bridges over the Pregel river

18th century The residents of K?nigsberg 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.

2010-112010-11-12 Graph Theory with Applications_Y.GUO 3

Leonhard Euler

Leonhard Euler solved this Seven Bridges of K?nigsberg and A published his research in 1736. This paper is regarded as the first paper in the history of Picture only what graph theory as a is essential to the subject.

problem. C

B

D

Euler’s 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?

2010-112010-11-12 Graph Theory with Applications_Y.GUO

C

A

B

D

4

Leonhard Euler (1707-1783) (1707Born April 15, 1707 in Basel, Switzerland University of Basel in 1720 at age 14 1723 completed Master’ Master’s degree in Philosophy 1726 completed Master’ Master’s degree in Mathematics

father of graph theory

2010-112010-11-12 Graph Theory with Applications_Y.GUO 5

Today’s Bridges of K?nigsberg

A map of K?nigsberg (Kaliningrad, as it is now called) after its rebuilding after its destruction in World War II

2010-112010-11-12

Graph Theory with Applications_Y.GUO

6

Today’s Bridges of K?nigsberg

Bridge 1

2010-112010-11-12

Graph Theory with Applications_Y.GUO

7

Today’s Bridges of K?nigsberg

Bridge 2

2010-112010-11-12

Graph Theory with Applications_Y.GUO

8

Today’s Bridges of K?nigsberg

Bridge 3

2010-112010-11-12

Graph Theory with Applications_Y.GUO

9

Today’s Bridges of K?nigsberg

Bridge 4

2010-112010-11-12

Graph Theory with Applications_Y.GUO

10

Today’s Bridges of K?nigsberg

Bridge 5

2010-112010-11-12

Graph Theory with Applications_Y.GUO

11

Today’s Bridges of K?nigsberg

Bridge 6

2010-112010-11-12

Graph Theory with Applications_Y.GUO

12

Birth of Graph theory

The term of graph has been introduced by Sylvester in a paper published in 1878 in Nature. Nature. First theoretic book

H?nig,D. Theorie der Endliche und Unendliche Graphen, Graphen, Leipzig, Akademishe Verlagsgesellshaft, 1936

What is graph theory? theory?

“Graph theory is the study of mathematical objects (graphs) that are made of dots that may or may not be connected by lines.”

2010-112010-11-12 Graph Theory with Applications_Y.GUO 13

History & application

More than one century after Euler's paper on the bridges of K?nigsberg 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 chemistry. trees. 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 Pólya 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.

2010-112010-11-12

Graph Theory with Applications_Y.GUO

14

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 problem: 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 Robertson, Seymour, Thomas. Thomas. The study and the generalization of this problem by Tait, Tait, Heawood, Heawood, Ramsey and Hadwiger has in particular led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus. Tait's reformulation generated a new class of problems, the factorization problems, particularly studied by problems, Petersen and K?nig. The works of Ramsey on colorations and K?nig. more specially the results otained by Turán in 1941 is at the origin of another branch of graph theory, the extremal graph theory. theory.

2010-112010-11-12 Graph Theory with Applications_Y.GUO 15

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 Kirchhoff, Kirchhoff's circuit laws for calculating the voltage and current in electric circuits. circuits. 1950s,1960s, boost in Graph theory research

2010-112010-11-12

Graph Theory with Applications_Y.GUO

16

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 HyperHyper-graph theory ……

2010-112010-11-12

Graph Theory with Applications_Y.GUO

17

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

2010-112010-11-12 Graph Theory with Applications_Y.GUO 18

Internet: ip-level ip(William R. Cheswick)

2010-112010-11-12

Graph Theory with Applications_Y.GUO

19

www

(K. C. Claffy)

2010-112010-11-12

Graph Theory with Applications_Y.GUO

20

Telecomm Networks

(Stephen G. Eick)

2010-112010-11-12

Graph Theory with Applications_Y.GUO

21

VLSI Circuits

2010-112010-11-12

Graph Theory with Applications_Y.GUO

22

Simple Network vs Complex Network

Lots of networks in reality NonNon-trivial topological properties

ScaleScale-Free Network PowerPower-law exponents between 2 and 3

Simple Network

Complex Network

Network Theory/Science

2010-112010-11-12

Graph Theory with Applications_Y.GUO

23

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 Erd? Ré 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) Erd? (1913Oliver Sacks: "A mathematical genius of the first order, order, Paul Erd?s 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)

2010-112010-11-12

Graph Theory with Applications_Y.GUO

24

Erd?s Number

Erd?s Number

Erd?s published >1,600 papers with > 500 coauthors in his life time

Published 2 papers per month from 20 to 83 years old Main contributions in modern mathematics: Ramsey theory, graph theory, Diophantine analysis, additive number theory and prime number theory, …

Erd?s alone was assigned the Erd?s number of 0 (for being himself

his immediate collaborators could claim an Erd?s number of 1

their collaborators have Erd?s number at most 2, and so on.

Because of his prolific output, friends created the Erd?s number as a humorous tribute

2010-112010-11-12 Graph Theory with Applications_Y.GUO 25

Erd?s Number

Some have estimated that 90 percent of the world's active mathematicians have an Erd?s number smaller than 8 (not surprising in light of the small world phenomenon). The Erd?s number was most likely first defined by Casper Goffman, an analyst whose own Erd?s number is 1. Goffman published his observations about Erd?s' prolific collaboration in a 1969 article entitled "And what is your Erd?s number?"

2010-112010-11-12 Graph Theory with Applications_Y.GUO 26

Erd?s Number

the Fields award owners had Erd?s number not larger than 5 (and only Cohen and Grothendieck were with Erd?s number 5) the Nevanlinna award owners Erdos had Erd?s number not larger than 3 (and only Valiant’ Erd?s number was 3) the Wolf mathematics award owners had Erd?s numbers not larger than 6，(and only V.I. Arnold’ Erd?s number 6， was 6 and Kolmogorov’s was 5) the Steele lifetime achievements award owners had Erd?s number not larger than 4. People in other areas:

Bill Gates’ Erd?s number is 4 with the path Erd?s --Pavol Hell---Pavol Hell-Xiao Tie Deng--Christos H. Papadimitriou--William H. (Bill) Gates. Deng--Christos Papadimitriou--William Einstein: 2.

2010-112010-11-12

Graph Theory with Applications_Y.GUO

27

Erd?s Number

Erd?s had a (scale-free small-world network scale-free) smallof mathematical research collaboration Science collaboration network

Author - node Paper coauthored - link

2010-112010-11-12

Graph Theory with Applications_Y.GUO

28