1.3. A Note on Graphs

Many of the problems studied in this course are graph problems, because almost anything can be modelled as a graph problem. For some of these problems, it is important whether the underlying graph is directed or undirected; for others, it is irrelevant beyond the fact that, in a directed graph, the two edges \((v,w)\) and \((w,v)\) are separate entities while they are the same in an undirected graph. For problems that can be defined for both directed and undirected graph, I will simply use the term "graph", without specifying whether it is directed or undirected. You should check in these cases that the problem definition and the developed algorithms are indeed sound both if the graph is undirected and if it is directed. When it is important whether the graph is directed or undirected, I state this explicitly.