Thuật toán Algorithms (Phần 47)

Chia sẻ: Tran Anh Phuong | Ngày: | Loại File: PDF | Số trang:10

0
39
lượt xem
3

Thuật toán Algorithms (Phần 47)

Mô tả tài liệu

Tham khảo tài liệu 'thuật toán algorithms (phần 47)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0)

Lưu

Nội dung Text: Thuật toán Algorithms (Phần 47)

1. 453 Exercises 1. Find all the matchings with five edges for the given sample bipartite graph. 2. Use the algorithm given in the text to find maximum matchings for random bipartite graphs with 50 vertices and 100 edges. About how many edges are in the matchings? 3. Construct a bipartite graph with six nodes and eight edges which has a three-edge matching, or prove that none exists. 4. Suppose that vertices in a bipartite graph represent jobs and people and that each person is to be assigned to two jobs. Will reduction to network flow give an algorithm for this problem? Prove your answer. 5. Modify the network flow program of Chapter 33 to take advantage of the special structure of the O-l networks which arise for bipartite matching. 6. Write an efficient program for determining whether an assignment for the marriage problem is stable. 7. Is it possible for two men to get their last choice in the stable marriage algorithm? Prove your answer. 8. Construct a set of preference lists for N = 4 for the stable marriage problem where everyone gets their second choice, or prove that no such set exists. 9. Give a stable configuration for the stable marriage problem for the case where the preference lists for men and women are all the same: in ascend- ing order. 10. Run the stable marriage program for N = 50, using random permutations for preference lists. About how many proposals are made during the execution of the algorithm?
2. 454 SOURCES for Graph Algorithms There are several textbooks on graph algorithms, but the reader should be forewarned that there is a great deal to be learned about graphs, that they still are not fully understood, and that they are traditionally studied from a mathematical (as opposed to an algorithmic) standpoint. Thus, many references have more rigorous and deeper coverage of much more difficult topics than our treatment here. Many of the topics that we’ve treated here are covered in the book by Even, for example, our network flow example in Chapter 33. Another source for further material is the book by Papadimitriou and Steiglitz. Though most of that book is about much more advanced topics (for example, there is a full treatment of matching in general graphs), it has up-to-date coverage of many of the algorithms that we’ve discussed, including pointers to further reference material. The application of depth-first search to solve graph connectivity and other problems is the work of R. E. Tarjan, whose original paper merits further study. The many variants on algorithms for the union-find problem of Chapter 30 are ably categorized and compared by van Leeuwen and Tarjan. The algorithms for shortest paths and minimum spanning trees in dense graphs in Chapter 31 are quite old, but the original papers by Dijkstra, Prim, and Kruskal still make interesting reading. Our treatment of the stable marriage problem in Chapter 34 is based on the entertaining account given by Knuth. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer- ishe Muthemutik, 1 (1959). S. Even, Graph Algorithms, Computer Science Press, Rockville, MD, 1980. D. E. Knuth, Marriages stables, Les Presses de L’Universite de Montreal, Montreal, 1976. J. R. Kruskal Jr., “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings AMS, 7, 1 (1956). C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982. R. C. Prim, “Shortest connection networks and some generalizations,” Bell System Technical Journal, 36 (1957). R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, 1, 2 (1972). J. van Leeuwen and R. E. Tarjan, “Worst-case analysis of set-union algo- rithms,” Journal of the ACM, to appear.