graph algorithms that any team is better than any other for instancein the six-team league where everyone plays three gamessuppose we have the following resultsa beat and cb beat and fc beat dd beat ee beat af beat and then we can prove that is better than fbecause beat bwho in turnbeat similarlywe can prove that is better than because beat and beat given list of game scores and two teams and yeither find proof (if one existsthat is better than yor indicate that no proof of this form can be found the input is collection of currencies and their exchange rates is there sequence of exchanges that makes money instantlyfor instanceif the currencies are xyand and the exchange rate is equals ys equals zsand equals zsthen zs will buy xswhich in turn will buy yswhich in turn will buy zs we have thus made profit of percent student needs to take certain number of courses to graduateand these courses have prerequisites that must be followed assume that all courses are offered every semester and that the student can take an unlimited number of courses given list of courses and their prerequisitescompute schedule that requires the minimum number of semesters the object of the kevin bacon game is to link movie actor to kevin bacon via shared movie roles the minimum number of links is an actor' bacon number for instancetom hanks has bacon number of he was in apollo with kevin bacon sally fields has bacon number of because she was in forrest gump with tom hankswho was in apollo with kevin bacon almost all well-known actors have bacon number of or assume that you have comprehensive list of actorswith roles, and do the followinga explain how to find an actor' bacon number explain how to find the actor with the highest bacon number explain how to find the minimum number of links between two arbitrary actors the clique problem can be stated as followsgiven an undirected graphg (ve)and an integerkdoes contain complete subgraph of at least verticesthe vertex cover problem can be stated as followsgiven an undirected graphg (ve)and an integerkdoes contain subset such that | < and every edge in has vertex in show that the clique problem is polynomially reducible to vertex cover assume that the hamiltonian cycle problem is np-complete for undirected graphs prove that the hamiltonian cycle problem is np-complete for directed graphs prove that the unweighted simple longest-path problem is np-complete for directed graphs the baseball card collector problem is as followsgiven packets pm each of which contains subset of the year' baseball cardsand an integerkis it possible to collect all the baseball cards by choosing < packetsshow that the baseball card collector problem is np-complete for instancesee the internet movie database filesactor list gz and actresses list gz at ftp://ftp fu-berlin de/pub/misc/movies/database