1 Introduction to graph theory 1.1 Application example Dam B Dam A Dam C F2 F3 F4 F1 Dam D F5 F8 F7 F6 Figure 1: Irrigation scheme example Consider the graph in Figure 1, which represents a simple irrigation scheme containing dams, farms (the Fi) and pipes. The edges show in which direction water can be pumped. 1. Give the set-theoretic definition of the graph. 2. Suppose the pumping scheme is very reliable and that all farmers are allocated a fair share of water, which farm would you most prefer to live on? Why? 3. Under the same assumptions, which farm would you least prefer to live on? 4. Suppose the pumping system is very unreliable. Which farm would you most prefer to live on? Which would you least like to live on? Explain. 5. Which are the two most critical links in the scheme? 6. Is this graph strongly connected? Is it weakly connected? 7. Are there any bridges? 8. Is it a DAG? Is it a tree?