文档介绍：COMPUTING SCIENCE
GRAPH THEORY IN PRACTICE: PART I
Brian Hayes
A reprint from
American Scientist
the magazine of Sigma Xi, the Scientific Research Society
Volume 88, Number 1
January–February, 2000
pages 9–13
This reprint is provided for personal and mercial use. For any other use, please send a
request to Permissions, American Scientist, . Box 13975, Research Triangle Park, NC, 27709,
., or by electronic mail to ******@. © 2000 Brian Hayes.
COMPUTING SCIENCE
GRAPH THEORY IN PRACTICE: PART I
Brian Hayes
hat is the diameter of the World Wide line joining the two vertices at its end points. Thus
Web? The answer is not 7,927 miles, the graph defined abstractly above looks like this:
Weven though the Web truly is World a
Wide. According to Albert-László Barabási, Reka
Albert and Hawoong Jeong of Notre Dame Uni- b c
versity, the diameter of the Web is 19. Most of the time, a picture is worth at least a
The diameter in question is not a geometric dis- thousand sets, and yet there are reasons for retain-
tance; the es from the branch of math- ing the more formal definition. When you look at
ematics called graph theory. On the Web, you get a graph drawing, it’s hard not to focus on the
from place to place by clicking on hypertext links, arrangement of the dots and lines, but in graph
and so it makes sense to define distance by count- theory