Previous    Next

### Exercises

• 19.1 Find a large digraph somewhere online—perhaps a transaction graph in some online system, or a digraph defined by links on Web pages.

• 19.2 Find a large DAG somewhere online—perhaps one defined by class-definition dependencies in a large software system, or by directory links in a large file system.

Make a table like Screenshot, but exclude from the counts graphs and digraphs with self-loops.

How many digraphs are there that contain V vertices and E edges?

19.5 How many digraphs correspond to each undirected graph that contains V vertices and E edges?

19.6 How many digits do we need to express the number of digraphs that have V vertices as a base-10 number?

19.7 Draw the nonisomorphic digraphs that contain three vertices.

••• 19.8 How many different digraphs are there with V vertices and E edges if we consider two digraphs to be different only if they are not isomorphic?

19.9 Compute an upper bound on the percentage of 10-vertex digraphs that could ever be examined by any computer, under the assumptions described in the text and the additional ones that the universe has less than 1080 electrons and that the age of the universe will be less than 1020 years.

 Previous    Next