文档介绍：COMPUTING SCIENCE
GRAPH THEORY IN PRACTICE: PART II
Brian Hayes
A reprint from
American Scientist
the magazine of Sigma Xi, the Scientific Research Society
Volume 88, Number 2
March–April, 2000
pages 104–109
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 ******@. Entire contents © 2000 Brian Hayes.
COMPUTING SCIENCE
GRAPH THEORY IN PRACTICE: PART II
Brian Hayes
art I of this article, in the January–February number of edges is n(n–1)/2, or roughly n2/2. (I
Pissue, discussed some very large structures consider here only “simple” graphs, as opposed to
that can usefully be looked upon as mathe- multigraphs, where more than one edge can join a
matical graphs. In this context a graph is a set of pair of vertices.) In large real-world graphs, the
vertices (which are usually represented as dots) number of edges is generally closer to n than to
and a set of edges (lines between the dots). One n2/2. For example, the Hollywood graph has 13
large object that can be described in this way is million edges connecting its 225,000 vertices. That
the World Wide Web; its 800 million pages are sounds like a lot, but it falls far short of the 25 bil-
the vertices of a graph, and links from o