Your company needs a new website. There will be many
pages with links between them. The public is itching to view
your website so you want to publish each page as soon as
it is ready.
Caveat: You don’t want any broken links.
Q. What order do you create the pages in?
Let W = fw ;w1;w 2w ;3 ;4 ;w5g b6 th7 set of webpages.
▯ page w 1inks to pages fw ;2 ;w3;w 6, 7
▯ pages w 3nd w li4k to page w , 8
▯ pages w 2nd w li7k to page w an5
▯ page w 6inks to pages w a2d w . 4
Q. In order that there are no broken links, in which order should
the pages be written?
1 Q. How can we think of this problem as a graph?
Draw the graph.
Q. In this case there is an acceptable ordering. If there were no
acceptable ordering, what property would the graph have?
2 Q. What do you notice about w and 5
w 8 5 6
These types of vertices are called sinks. 4 1
Q. What do you notice about w ? 1
These types of vertices are called sources.
Q. Which type of vertices (webpages) should be written ﬁrst?
Q. If webpages w and w are written ﬁrst, imagine deleting them
from the graph. What do you notice about w ;w ;w 4nd w2? 3 7