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?

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

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

Screenshot 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?

Screenshot 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.



   
Comments