tailieunhanh - Thuật toán Algorithms (Phần 45)

Tham khảo tài liệu 'thuật toán algorithms (phần 45)', 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ả | 33. Network Flow Weighted directed graphs are useful models for several types of applications involving commodities flowing through an interconnected network. Consider for example a network of oil pipes of varying sizes interconnected in complex ways with switches controlling the direction of flow at junctions. Suppose further that the network has a single source say an oil field and a single destination say a large refinery to which all of the pipes ultimately connect. What switch settings will maximize the amount of oil flowing from source to destination Complex interactions involving material flow at junctions make this problem called the network flow problem a nontrivial problem to solve. This same general setup can be used to describe traffic flowing along highways materials flowing through factories etc. Many different versions of the problem have been studied corresponding to many different practical situations where it has been applied. There is clearly strong motivation to find an efficient algorithm for these problems. This type of problem lies at the interface between computer science and the field of operations research. Operations researchers are generally concerned with mathematical modeling of complex systems for the purpose of preferably optimal decision-making. Network flow is a typical example of an operations research problem we ll briefly touch upon some others in Chapters 37-40. As we ll see the modeling can lead to complex mathematical equations that require computers for solution. For example the classical solution to the network flow problem given below is closely related to the graph algorithms that we have been examining. But this problem is one which is still actively being studied unlike many of the problems that we ve looked at the best solution has not yet been found and good new algorithms are still being discovered. 433 434 CHAPTER 33 The Network Flow Problem Consider the following rather idealized drawing of a small network of oil .