Discrete Mathematics for Computer Science

4M6 CHAPTER 6 Graph Theory

Information Links on the Web

The pages accessible from a Web browser can be represented by a graph in which the

vertices are the pages and there are directed edges between pages that are linked. A query

will determine the importance of a page by incorporating information about the importance

or relevance of the information in pages pointed to and from the page being examined.

When you make a Web query, the pages associated with a given page are as important as

the page itself. The final listing of pages of interest for a query are determined by searching

the graph that represents the linkages of a page. Additional mathematical techniques are

used to discern the final selection of pages to present to the user. Optimization techniques

involving linear algebra and probability are used to rank pages that are found by the search

procedure.

Exercises

1. In each of the following graphs:
   6

2 3 a c x

Y

14 e d U V W

D, D2 D3

(a) Determine the indegree of each vertex.

(b) Determine the outdegree of each vertex.

(c) Find a directed cycle of length four or greater, if any exists.

(d) Find a directed path of length four or greater, if any exists.

(e) Find a directed circuit of length at least six.

2. Let D be a directed graph with an outdegree of each vertex of at least one. Prove that
   D contains a directed cycle. Show that the same result holds if the hypothesis is that
   each node has an indegree of at least one.


3. Prove that any directed acyclic graph contains at least one vertex with an indegree of
   zero. Use this result to devise a different algorithm to do a topological sort.


4. Verify that the following graph D is a dag. Perform a topological sort on the vertices
   of the graph.

2 3

1 4

6 5

D